Algorithms for NP-Hard Problems

Combinatorial optimisation problems such as scheduling or optimally playing a board game are often NP-hard. Most of the algorithms in earlier courses run in polynomial time and cannot be directly used for solving NP-hard problems. In this course you will learn some new algorithms, and use these, but also concepts from earlier courses on algorithm design, to solve NP-hard problems.

The final grade is computed based on a weighted average of the grade for the programming assignments and the final written exam, as follows:

A = unrounded, unweighted arithmetic mean of assignment grades

E = unrounded exam grade

C = 0.2 * A + 0.8 * E

C is rounded to the nearest 0.1

A resit exam will be available, whereupon E = max(E_exam, E_resit).

For each assignment i, students who receive a grade between 4.0 and 5.9 may re-submit the assignment, whereupon A_i = min(6.0, max(A_i_original, A_i_resubmission)). Students who receive a grade on assignment i outside these bounds may not re-submit the assignment, i.e. if A_i < 4.0 or A_i > 5.9.

To pass the course in terms of grades, the student must satisfy the conjunction of these constraints:

A >= 5.0

E >= 5.0

C >= 5.8

Disclaimer: information may change depending on unforeseen circumstances or measures (see: TER Art 29, sub 4)