Algorithms 2025

• Aug 25: Median finding in linear time
  
  
• Sep 1-3: Fast Fourier Transform; Karger's algorithm for min-cut
  
  
• Sep 8-10: Karger-Stein algorithm; Ford-Fulkerson algorithm
  
  
•     Assignment 1
  
  
•     Notes on Max-Flow (by Kurt Mehlhorn)
  
  
  
• Sep 15-17: Ford-Fulkerson algorithm, Bipartite matchings, and Dinic's algorithm
  
  
• Sep 22-24: Preflow-Push algorithms
  
  
• Sep 29-Oct 1: Dijkstra's algorithm and Fibonacci heap
  
  
• Oct 6-8: Fibonacci heap and MST algorithms
  
  
• Oct 13: Union-Find data structure
  
  
•     Assignment 2
  
  
•    Oct 15: Exam 1
  
  
• Oct 22: Miller-Rabin primality testing algorithm
  
  
• Oct 27-29: Analysis of Miller-Rabin algorithm, Randomized quicksort, and Online Paging
  
  
• Nov 3-5: Analysis of Marker algorithm and Hashing
  
  
•     Assignment 3
  
  
• Nov 10-12: Linear programming
  
  
• Nov 17-19: Application of strong duality and Complexity Classes: P and NP
  
  
• Nov 24-26: Introduction to Approximation Algorithms
  
  
• Dec 1: FPTAS for Knapsack and Discussion
  
  
•     Assignment 4
  
  
•    Notes on Linear Programming:   LP
  
  
•    Hardness Reductions:   Hardness Reductions
  
  
•    Approximation Algorithms:   Introduction to Approximation Algorithms
  
  
•    Dec 3: Exam 2