HOME cs.uu.nl


MSc Programme ``Algorithmic Systems" 2003-2004

Course: Algorithmic Modelling and Complexity (AMC)


Course overview

Systems and programs are designed for many purposes and in many ways, but it's algorithms that make things work. Good algorithm design requires understanding and modelling an application, and subsequently studying and analyzing the computational features of the design. In this course we study a number of advanced techniques for efficient algorithm design using cases in network modelling, vehicle routing, integer linear programming, protocol design and model checking. The required basics from the theory of NP-completeness will be re-appraised as well.

This year's course will have the same structure as last year's but its contents will be almost entirely different.

Class schedule


BSc in computer science or equivalent. If you have not completed most of your three-year BSc program, see your MSc-program advisor: you may not be admissable to this course. Specific background required: datastructures (UU-course datastructuren), beginning algorithms (UU-course Algoritmiek), ideas of linear programming (possibly UU-course Optimalisering or UU-course Discrete optimalisering).


No textbook is required. The scribe-notes document the course.

Course Work

  1. Lectures

    Twice a week (plus student presentations once a week after week 38). Attendence is recorded. (The course will be taught in English unless all participating students are fluent in Dutch.)

  2. Homework/Studies

    With every lecture one or two (homework) questions will be given, which must be reported on `next time'. These homework questions will not be graded.

  3. `Scribe'-tasks

    Each student must write the notes of approximately two of the lectures (details depend on the number of participants). The notes must give the details of the lecture in a compact but complete manner, and possibly extend the material slightly. The draft notes must be handed in within one week, the complete and final version within one week after this (in collaboration with the lecturer). The notes will be posted as course notes immediately, in ps, pdf and/or html and also the (LaTeX) source. The notes are to be written in English, using the format defined by the template.

    Example of a `scribed course':

  4. `Research'-assignment

    Each student must prepare a presentation on a topic in algorithmic modeling and complexity, typically based on one or two recent papers. After the first lecture, one can submit a proposal within two days (which will not necessarily be assigned). The topics will be assigned by the third lecture. The presentations should be prepared on transparencies or in PPT, there will be 20-25 minutes available per presentation. From week .. onward, presentations will be scheduled in the ..day slots.

  5. Final exam

    The final exam will be `open notes'.


Participation and attendence will count for 10%. The scribe-task, research assignment and final exam will each count for 30%.

Recommended reading

Search tools

Other links

Last modified: June 2003