Uni-Logo
Algorithms and Complexity
 


Algorithm Theory
Winter Term 2021 / 2022
Fabian Kuhn

 


Recordings and Slides


Topic Recordings Slides

Week 1 (18.10. – 22.10.):
Chapter 1: Divide and Conquer
Part I: Introduction & Time Analysis
Part II: Comparing Orders & Closest Pair of Points

Week 2 (25.10. – 29.10.): Part III: Operations on Polynomials, Karatsuba Alg.
Part IV: Fast Polynomial Multiplication 1
Part V: Fast Polynomial Multiplication 2

Week 3 (01.11. – 05.11.): Chapter 2: Greedy Algorithms
Part I: Interval Scheduling & Partitioning
Part II: Traveling Salesperson Problem (TSP)
Part III: Exchange Arguments
Part IV: The Greedy Algorithm for Matroids

Week 4 (08.11. – 12.11.): Chapter 3: Dynamic Programming
Part I: Weighted Interval Scheduling
Part II: Matrix Chain Multiplication
Part III: The Knapsack Problem

Week 5 (15.11. – 19.11.): Chapter 4: Amortized Analysis
Part I: Basics & Accounting Method
Part II: Potential Function Method
Chapter 5: Data Structures
Part I: Union-Find: Basic Implementation
Part II: Union-Find: Disjoint-Set Forests

Week 6 (22.11. – 26.11.): Part III: Priority Queues, Warm-Up
Part IV: Fibonacci Heaps, Algorithm Description
Part V: Fibonacci Heaps, Amortized Analysis

Week 7 (29.11. – 03.11.): Chapter 6: Graph Algorithms
Part I: Maximum Flow: Ford Fulkerson Algorithm
Part II: Basic Ford Fulkerson Analysis
Part III: Fast Ford Fulkerson Implementations

Week 8 (06.12. – 10.12.): Part IV: Simple Maximum Flow Applications
Part V: Baseball Elimination
Part VI: Circulation
Part VII: Matrix Rounding

Week 9 (13.12. – 17.12.): Part VIII: Bipartite Maximum Matching
Part IX: Maximum Matching in General Graphs
Chapter 7: Randomized Algorithms
Part I: Contention Resolution

Week 10 (20.12. – 07.01.):
(holiday break 23.12.–6.1.)
Part II: Primality Testing
Part III: Randomized Quicksort: Expected Time
Part IV: Rand. Quicksort: High Probability Bound

Week 11 (10.01. – 14.01.): Part V: Basic Randomized Minimum Cut Algorithm
Part VI: Implementing Edge Contractions
Part VII: Fast Randomized Minimum Cut Algorithm
Part VIII: Cut Counting and Edge Sampling

Week 12 (17.01. – 21.01.): Chapter 8: Approximation Algorithms
Part I: Greedy Load Balancing
Part II: The Metric TSP Problem
Part III: Minimum Set Cover
Part IV: Knapsack Approximation Scheme

Week 13 (24.01. – 28.01.): Chapter 9: Online Algorithms
Part I: Deterministic Paging
Part II: Randomized Paging

Week 14 (31.01. – 04.02.):
(recording of live lecture in February 2020, will not be part of the exam)
Chapter 10: Parallel Algorithms
Part I: Parallel Algorithms 1
Part II: Parallel Algorithms 2