Algorithm Design, MSc CS
This course is an advanced course on algorithms which builds on top of an introductory course on algorithms and data structures. The course focuses on advanced techniques for identifying and solving computationally hard problems and on how to adapt such techniques to real-world scenarios.
This course introduces students to techniques for solving complex programming tasks arising in modern IT systems. The student taking this course will be able to quickly identify and solve a certain class of problems that can arise among the tasks that a skilled programmer must solve.
Focus in the course is on algorithm design and identification of computationally hard problems. The course contains both theoretical and analysis and implementation exercises.
Contents of lectures includes: Formulating an algorithmic problem, greedy algorithms, graph algorithms, divide and conquer, dynamic programming, network flow, reductions.
Intended learning outcomes
After the course, the student should be able to:
- Solve a wide range of real-life programming problems in a scalable way by employing algorithmic design techniques and tools.
- Identify and formulate precisely (if possible) the algorithmic problem underlying in a given programming task.
- Apply the following algorithmic techniques when solving a problem: Greedy, divide and conquer, dynamic programming, reduction to network flow.
- Look up suitable NP hardness results in a compendium, and perform simple reductions from such problems to establish NP hardness.
Ordinary examExam type:
A: Written exam on premises, external (7-trinsskala)
A33: Written exam on premises on paper with restrictions
4 hours written exam on premises with all written aids (course book, own notes, printouts of slides, etc.). No use of pocket calculator and electronic communication tools such as PC, laptop, tablet or e-reader with internet or other network connection or mobile phone. Only use of ballpoint pen is allowed for the final exam hand-in.