CENTER FOR ALGORITHMIC SYSTEMS
MSc Programme ``Algorithmic Systems"
Course: Algorithmic Modelling and Complexity (AMC)
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.
- Lecture hours:
- Tuesday 11.00 - 13.00, in: BBL-420.
- Thursday 09.00 - 11.00, in: BBL-420.
- From week 40 onward also: Tuesday 9.00 - 11.00 (in: BBL-430).
- First meeting: Tuesday September 2, 11.00 - 13.00 (in: BBL-420).
- Office hours: by appoinment.
- Final exam (tentamen): Tuesday November 4, 9.00 - 12.00 (in: BBL-160).
- Here is the weekschedule.
- Search tools and links
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.
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.)
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.
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':
year's course on `algorithmic modeling and complexity'.
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.
The final exam will be `open notes'.
- Final exam (tentamen): Tuesday November 4, 9.00 - 12.00 (in: BBL-...).
Participation and attendence will count for 10%. The scribe-task, research
assignment and final exam will each count for 30%.
Last modified: June 2003