Algorithms and Complexity, 7.5 hp

The overall goal of the course is to provide the students with tools to help them develop efficient algorithms for new problems. The first step is to formulate and analyze the computational problem. The next step is to select and modify data structures and techniques in order to formulate an algorithm. Once the algorithm is analyzed for correctness and efficiency, it can be implemented.

The course deals with the concepts complexity on a deeper level than previous courses, with respect to time as well as space. It presents techniques to evaluate the complexities for a given algorithm. The students learn about asymptotic functions and the complexity classes P, NP and NP-complete.

The choice of appropriate data structures is essential for the design of efficient algorithms. The course introduces complex data structures, such as heaps and graphs, as well as operations on them.

A few standard design techniques, including greedy algorithms, dynamic programming and divide-and-conquer, are presented.