Höhere Algorithmik

What it is about

You will learn fundamental techniques for the development and analysis of efficient algorithms (e.g., Divide-and-Conquer, dynamic programming, randomization, Greedy methods, amortized analysis) and apply them to central problems such as sorting, graph problems, string and sequence algorithms, as well as data structures. In the end you will be able to understand, analyze, and use classical algorithmic procedures to solve fundamental tasks.

What you will be able to do

• Familiarity with Divide-and-Conquer techniques (e.g., Quicksort, FFT, geometric problems)
• Application and analysis of dynamic programming (e.g., matrix chain, edit distance, sequence alignment)
• Understanding of randomization in algorithms (Las Vegas/Monte Carlo, primality tests, RSA)
• Knowledge of central data structures (treaps, hashing, suffix trees, Fibonacci heaps)
• Mastery of Greedy strategies and suitable model problems (interval scheduling, shortest paths)
• Application of amortized analysis to dynamic tables and heaps
• Foundations of flow and cut problems in graphs
• Insight into advanced complexity aspects (e.g., PSPACE) and selected topics (e.g., stable marriage, local search)

What the module consists of

• VorlesungDelivery of the content in lectures and through presentations
• ÜbungWork on problem sheets and review; individual feedback through corrections

Teaching method

• Vortrag/PräsentationIntroduction and systematic presentation of the topics
• Übungsblätter und ÜbungsveranstaltungDeepening through independent problem solving and discussion; feedback through corrections
• TafelarbeitSupplementary explanation and derivation during the lecture