CENTER FOR ALGORITHMIC SYSTEMS
MSc Programme ``Algorithmic Systems"
2003-2004
Course: Algorithmic Modelling and Complexity (AMC)
Lecturer(s):
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
- 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
Prerequisites
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).
Text
No textbook is required. The
scribe-notes document the course.
Course Work
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.)
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.
`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':
- this
year's course on `algorithmic modeling and complexity'.
`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.
Final exam
The final exam will be `open notes'.
- Final exam (tentamen): Tuesday November 4, 9.00 - 12.00 (in: BBL-...).
Grading
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