Description: 

This course provides an overview of the different subject areas within algorithms, including a sampling of material on exact, approximation, geometric, and randomized algorithms and on advanced data structures. As such, the course is the basis of the corresponding master-level courses. The course covers improvements on classical algorithms as well as ways to approach NP-hard problems. These approaches range from understanding "good" algorithms to solve the problem exactly to efficient algorithms that solve the problem approximately, and also to randomized approaches which perform well in expectation. Along the way we will see some interesting data structures that can be leveraged.

Learning Objectives:

By the end of this course participants should have a broad overview of advanced topics concerning algorithms (i.e., regarding exact, approximate, geometric, and randomized computations) as well as some advanced data structures. They should be able to analyze and design algorithms of each type and understand the appropriate use of the data structures.

Evaluation:

Grades will be determined by an oral exam at the end of the semester. A bonus of 0,3 points will be awarded to the students who obtain at least 50% of the points on the exercises. 

Literature:

• Introduction to Algorithms (3rd Edition).
  Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford.  MIT Press and McGraw-Hill 2009 [1990].
• Parameterized Algorithms. 
  Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk and Saket Saurabh.  Springer International Publishing 2015. 
  https://www.mimuw.edu.pl/~malcin/book/parameterized-algorithms.pdf
• Exact Exponential Algorithms.
  Fedor V. Fomin and Dieter Kratsch. Springer-Verlag Berlin Heidelberg 2010.
  http://www.ii.uib.no/~fomin/BookEA/BookEA.pdf
• Computational Geometry: Algorithms and Applications (3rd edition).
  Mark de Berg, Otfried Cheong, Marc van Kreveld, Mark Overmars. Springer-Verlag, 2008.
  Web site with pseudocode for all algorithms
  
• The Design of Approximation Algorithms
  David P. Williamson, David B. Shmoys. Cambridge University Press, 2011.
  Kostenlose Online-Version
  
• Approximation Algorithms
  Vijay V. Vazirani. Springer, 2003.