Advanced Algorithms

• Lecturer:
  Prof. Dr. Susanne Albers
• Module: IN2360, TUMonline
• Area:
  3+2 SWS in the area Computer Science III (Theoretical Computer Science)
• Time and Location:
  Tuesday, 12:00–14:00, 8120.EG.001, Lecture Hall in the Galileo
  Thursday, 12:00–14:00, 8120.EG.001, Lecture Hall in the Galileo
• Exercises: 
  Tuesday, 14:00–16:00, in 02.04.011 
  Thursday, 14:00–16:00, in 01.07.023 
  Tutorials: Tobias Forner 
  Further information will follow on Moodle.
• Audience:
  Graduate students of computer science
  Students with computer science as minor
• ECTS: 6 points
• Prerequisites:
  1st and 2nd year courses
• Exam:
  On-site exam

Content

The modul covers fundamental and classical results in the area of advanced algorithms. Specifically, the course focuses on basic algorithm design and analysis principles. It addresses greedy approaches, divide and conquer, dynamic programming, randomization and amortization. These techniques are applied to develop solutions to cornerstone algorithmic problems.

Divide and Conquer: Introduction: deterministic Quicksort. Geometric divide and conquer: closest pair problem; line segment intersection; Voronoi diagrams. Fast Fourier Transform (FFT).

Randomized Algorithms: Las Vegas and Monte Carlo algorithms. Randomized Quicksort. Randomized primality test with applications to public-key cryptosystems. Verifying matrix multiplication.

Data Structures: Treaps – randomized search trees. Suffix trees.

Amortized Analysis: Dynamic tables. Fibonacci heaps.

Greedy Algorithms: Introduction. Interval scheduling. Scheduling to minimize lateness. Shortest paths in a graph.

Dynamic Programming: Introduction: weighted interval scheduling. Matrix-chain multiplication. Construction of optimal search trees. Segmented least squares. Subset sums and knapsacks.

Graph Algorithms: Computation of minimum cuts. Maximum-flow problem. 

Further Topics: Median Computation. The probabilistic method. 

Literature

• Th. Cormen, C. Leiserson, R. Rivest and C. Stein. Introduction to Algorithms. Third Edition, MIT Press, 2009.
• J. Kleinberg and E. Tardos. Algorithm Design. Pearson. Addison Wesley, 2006.
• M. Mitzenmacher and E. Upfal. Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis. Second Edition, Cambridge University Press, 2017.
• Th. Ottmann und P. Widmayer. Algorithmen und Datenstrukturen. 6. Auflage, Springer Verlag, 2017.