Responsible Instructor 

Instructor 

Contact Hours / Week x/x/x/x 
2/2/0/0

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 semidefinite 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 0321372913 Supplemental study material will be provided via Blackboard.

Assessment 
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.
