TU Delft
print this page print this page     
2016/2017 Electrical Engineering, Mathematics and Computer Science Master Computer Science
Advanced Algorithms
Responsible Instructor
Name E-mail
Prof.dr. C. Witteveen    C.Witteveen@tudelft.nl
Name E-mail
Prof.dr.ir. K.I. Aardal    K.I.Aardal@tudelft.nl
Dr. M.M. de Weerdt    M.M.deWeerdt@tudelft.nl
Contact Hours / Week x/x/x/x
Education Period
Start Education
Exam Period
Course Language
Expected prior knowledge
Basic courses in Algorithmics and Complexity Theory
Course Contents
Solving instances of intractable problems in reasonable time. Overview of approximation algorithms and approximation techniques. LP relaxations and semi-definite programming.
Study Goals
Knowledge of some advanced algorithmic techniques like kernelization techniques, general approximation techniques, and linear programming relaxation techniques.
Education Method
Lectures, homework exercises, and programming assignments.

The expected workload is
30% lectures (including preparation for the exams)
40% homework exercises
30% programming assignments
Literature and Study Materials
Parts of the course are derived from the textbook
J. Kleinberg and E. Tardos,
Algorithmic Design,
Pearson Education, 2006. ISBN 0-321-37291-3
Supplemental study material will be provided via Blackboard.
The final mark depends on the marks obtained for
(a) homework exercises (6 in total),
(b) programming assignments (2 in total) and
(c) the exam (3 parts).

The course contains 3 parts: Part 1, Part 2 and Part 3.

There are 2 homework exercises per part. These exercises are evaluated on a scale from 0 to 10 and the final mark for the homework exercises (HE) is the average of these results.
Homework exercises have to be completed individually.

There is a programming assignment to be completed at the end of Part 2 and one to be completed at the end of Part 3. Each assignment is graded on a scale from 0 to 10.
The final mark for the programming assignment (PA) is the average of the mark obtained for these two assignments.
Programming exercises can be completed by 2 students working together.

The final exam consists of three parts. Each part will be examined after the
four lectures about that part have been delivered and will be graded on a scale from 1 to 10. The final mark for the exam (EX) is the average of the marks for the parts.
For each part there is a resit. The result for a part after the resits is determined by the
maximum score obtained for the original exam and the resit.
Al the (partial) exams and their resits are closed book.

The final mark for the course is determined as follows:
- if each of the HE, PA and EX marks is above 5, the final mark is the average of these three marks.
- if at least one of HE, PA or EX is less than or equal to 5, the final mark is the minimum
of the results obtained for HE, PA or EX.