CMU 15-451 (Algorithms), Spring 2012

CMUQ Instructor: Yonina Cooper

Pittsburgh Instructors: Gary Miller and Victor Adamchik

Website Design Adapted from Avrim Blum
Course Materials Developed by Avrim Blum

General info


Minis


Homeworks


Lectures
  1. 16/01: Intro & Admin. Karatsuba/Strassen. [ppt, pdf, Related Work]
  2. 18/01: Asymptotic analysis, solving recurrences. [ppt, pdf]
    19/01: Recitation 1
  3. 23/01: Probabilistic analysis, Randomized Quicksort.
  4. 25/01: Linear-time Selection (randomized and deterministic).
  5. 30/01: Comparison-based Lower Bounds for Sorting.
  6. 01/02: Concrete models and tight upper/lower bounds .
    01/03: Recitation 2
  7. 06/02: Radix Sort and Tries + QUIZ.
  8. 08/02: Amortized Analysis
  9. 13/02: Search trees: B-trees and treaps
  10. 15/02: Universal and Perfect Hashing.
  11. 20/02: Dynamic Programming.
  12. 22/02: Graph Algorithms I .
  13. 27/02: Graph Algorithms II .
  14. 29/02: Midterm
  15. 12/03: Graph Algorithms III.
  16. 14/03: Graph Algorithms BFS and DFS.
  17. 19/03: Network Flow I.
  18. 21/03: Network Flow II .
  19. 26/03: Linear Programming.
  20. 28/03: NP-completeness I.
  21. 02/04: NP-completeness II.
  22. 04/04: Approximation Algorithms.
  23. 09/04: Online Algorithms + QUIZ.
  24. 11/04: Number theoretic algorithms I.
  25. 16/04: Number theoretic algorithms II.
  26. 18/04: Fast Fourier Transform
  27. 23/04: Intro to game theory.
  28. 25/04: Fair division: fair and envy-free cake-cutting.
  29. TBA: Final Exam