Course content

Principles of algorithm design: Decomposition, greedy algorithms, dynamic programming. Algorithm analysis. Probabilistic algorithms. Approximation. Selected applications to sets, graphs, arithmetic, and geometry.

Computability and complexity: Reductions. Complexity classes P (polynomial time), NP (non-deterministic polynomial time), and PSPACE (polynomial space). NP-complete problems. Undecidable problems.

Course literature

Kleinberg, Tardos; "Algorithm Design", Pearson Addison-Wesley.

Examination

The examination has four parts.

LAB1. Two programming lab assignments (pass/fail).
These can be done either individually or in pairs.
MAS1 and MAS2. Two home assignments (Mastery Tests), graded on an A-F scale.
The Mastery Tests must be done individually.
TEN1. Exam, graded on an A-F scale.
The exam is taken individually.

Details About Grading

Three of the tasks are graded: Mas1, Mas2 and Exam. The final course grade is the average value of these grades (rounded to the nearest grade) where E counts as 1 and A counts as 5.

Presenting a lab assignment by its bonus deadline results in 1 bonus point for the written exam. In addition, both of the lab assignments come with a set of theory questions, and presenting solutions to the theory questions by their bonus deadline (the bonus deadline for the theory questions is one or two weeks prior to the bonus deadline for presenting the lab) results in 1 additional bonus point for the exam. Thus you can in total get up to 4 bonus points for the exam.
Each Mastery Test consists of 4 problems. Basically, two problems correctly solved give you an E, three problems solved give you a C and four give you an A. They are presented by submitting a written report and by doing a short oral exam (15 min).
In the first written phase the grade on the exam can be at most C. If you get grade C on the exam or if you pass the exam and have gotten at least C on both MAS1 and MAS2 you can do a complimentary oral exam and raise the grade on the exam to B or A. On the complimentary exam you can also raise the grade on MAS1 and MAS2. The form of the exam is like this: You get 1, 2 or 3 problems to solve depending on which combination of MAS1, MAS2, or the exam that you want a higher grade on. You get one hour to think about the problems. Then you will present the solutions to the examiner.