Efficient Algorithms and Problem Complexity, 7.5 Credits
About the course
Part one of the course studies central notions and results concerning efficient algorithmic techniques on the one hand and problem complexity on the other hand. Algorithmic techniques that are studied and analyzed with respect to efficiency are divide-and-conquer, greedy methods, and dynamic programming. When it comes to problem complexity, the course mainly discusses the classes P and NP, reduction and NP-completeness. The main focus of the course is on worst-case analyses of sequential algorithms using time as a measure of efficiency, but even average case efficiency and space requirements are considered.
Part two consists of a number of supplementary areas that the student may choose among. Areas offered may be subject to change. However, typical areas include the following.
- The analysis of concrete programs by means of profiling software.
- Efficient algorithms and problem complexity in the area Automata and Formal Languages.
- Efficient parallel and distributed algorithms, and corresponding complexity classes.
Level of Education: Advanced
Course Menu
