CENTER FOR ALGORITHMIC SYSTEMS
MSc Programme ``Algorithmic Systems"
2004-2005
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
vehicle routing, network modeling, linear programming, logic modeling,
and effective approaches using randomization.
Class schedule
- Lecture hours:
- Tuesday 9.00-10.45, in: BBL 505.
- Thursday 13.15-15.00, in: BBL 505.
- From week xx onward also: Tuesday 11.00-12.45, in BBL 505.
- First meeting: Thursday September 2, 13.15-15.00 (in: BBL 505).
- Office hours: by appoinment.
- Final exam (tentamen): TBA.
- Here is the weekschedule (preliminary).
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
The course is organized slightly differently from last year.
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.
`Research'-assignment
Students in couples of two must prepare one lecture on a topic in
algorithmic modeling and complexity, typically based on new research material.
After the first lecture of the course, one can submit a proposal for a topic
within two days (which will not necessarily be assigned). The topics will be
assigned by the third lecture. The presentation should be prepared on
transparencies or in PPT, there will be about 80 minutes available per
presentation (including a coffee break). From week 43 onward, presentations
will be scheduled in Tuesday slots.
`Scribe'-tasks (tentatively)
Each student must write the lecture notes for the part of the presentation
that he/she is to give on his assigned topic. The notes must give the details
of the presentation(s) in a compact but complete manner. A preliminary complete
version must be handed over to the instructor at least two weeks before the
presentation takes place. The instructor will comment on the preliminary
version. The notes are to be written in English, using the format defined by
the LaTeX-template. The details depend on the number of participants and will
be announced later.
Final exam
The final exam will be `open notes'.
- Final exam (tentamen): TBA (in: BBL-...).
Grading
Participation, attendence, and homework together will count for 20%. The
research assignment (presentation) and the scribe task will count for 50% in
total. The final exam will count for 30%.
Recommended reading
Search tools
Other links
Last modified: September 2, 2004
