On completion of the course the student should have the following learning outcomes defined in terms of knowledge, skills and general competence:
Knowledge
The student knows:
- the central definitions of the paradigms for coping with computational intractability, such as FPT algorithms, kernels, approximation algorithms, exact exponential time algorithms, and polynomial time algorithms for restricted input classes.
- the basic algorithm design techniques within each of the paradigms.
- restricted input classes, such as trees, chordal graphs, and graphs of bounded treewidth, and the structural characterizations of these classes.
- the definition of randomized algorithms.
Skills
The student is able to:
- analyze the performance of a proposed algorithm within the different paradigms for coping with computational intractability
- design new algorithms for concrete problems within each of the considered algorithm design paradigms using the covered algorithm design techniques.
- apply structural insights about restricted input classes to design more efficient algorithms for these classes.
- Design randomized algorithms and analyze their performance in terms of the expected running time, the probability that the running time exceeds a set threshold, the expected quality of an output solution, and the probability that the quality is better or worse than a set threshold.
General competence
The student:
- can analyze and develop algorithms for computationally intractable problems.