CMU 15-451 (Algorithms), Fall 2010

Instructor: Manuel Blum

TAs: Jeremiah Blocki, Anvesh Komuravelli, Sarah Loos, Eric Seo, Jon Chu

General info

TA Feedback!

Below you will find links for Teaching Assistant evaluation surveys. Your feedback is very important to us. Please take the time to complete the evaluation survey for your TA.
Remember: Evaluations need to be completed *before* December 10th.
  1. Jonathan Chu
  2. Eric Seo
  3. Sarah Loos
  4. Anvesh Komuravelli
  5. Jeremiah Blocki

Practice Exams




Minis can be typed in a .txt document and emailed to your TA.


Homeworks must be typeset or no credit will be given. LaTeX is recommended.

Homework Template

hw_template.tex (pdf)

Lecture notes [The first 10 lectures] [The next 10 lectures]

  1. 08/24:Intro & Admin. Karatsuba/Strassen.
    08/25:(recitation) Warmup Problems.
  2. 08/26:Asymptotic analysis, solving recurrences.
  3. 08/31:Probabilistic analysis, Randomized Quicksort.
    09/01:(recitation) Problems related to randomized quicksort.
  4. 09/02:Linear-time Selection (randomized and deterministic).
  5. 09/07:Comparison-based lower bounds for sorting.
    09/08:(recitation) Problems related to selection recurrence, upper/lower bounds in concrete models.
    09/08:(recitation) Inductive proof of the selection recurrence.
  6. 09/09:Concrete models and tight upper/lower bounds
  7. 09/14:Amortized Analysis
    09/15:(recitation) Problems related to tight bounds and minimax optimality..
    09/15:(recitation) Formal proof of the assumptions made in the problem.
    09/15:(recitation) Discussion on the Bounds on Randomized Algorithms.
    09/15:(recitation) Common problems from hw1
  8. 09/16:Search trees: B-trees and treaps.
  9. 09/21:Digit-based sorting/data-structures (radix sort, tries).
    09/22: (recitation) Potential Function's and Amortization
  10. 09/23:Universal and Perfect Hashing.
  11. 09/28:Dynamic Programming.
    09/29: (recitation) Homework problems from last year (#1 and #3)
  12. 09/30:Graph Algorithms I: DFS and Topological Sorting, DP algs for shortest paths (Bellman-Ford, Matrix, Floyd-Warshall).
  13. 10/05:Graph Algorithms II: Dijkstra, Prim, Kruskal.
    10/06:(recitation) Maximum bottleneck path, coupon-collector's problem..
  14. 10/07: Review.
  15. 10/12: Midterm
    10/13:(recitation) 2-coloring,BFS and DFS trees.
  16. 10/14:Graph Algorithms III: Union-find.
  17. 10/19:Fun with BFS and DFS.
    10/20:(recitation) Examples of problems that can be solved using network flow..
  18. 10/21:Network Flows and Matchings I.
  19. 10/26:Network Flows II: Edmonds-Karp 1, Edmonds-Karp 2, Min-cost max flow.
    10/27:(recitation) Examples of problems that can be solved using linear programming.
  20. 10/28:Linear Programming.
  21. 11/02:NP-completeness I.
    11/03:(recitation) Examples of NP-completeness reductions: Integer Programming and 3-Coloring.
  22. 11/04:NP-completeness II.
  23. 11/09:Approximation Algorithms.
    11/10:(recitation) NP-completeness reductions contd..
  24. 11/11:Online Algorithms.
  25. 11/16:Number theoretic algorithms I.
    11/17:(recitation) Number-theory and a little more complexity theory .
  26. 11/18:Number theoretic algorithms II.
  27. 11/23:Fast Fourier Transform (FFT).
  28. 11/30:Intro to machine learning theory.
    12/01:(recitation) FFT/Review .
  29. 12/02:Mechanism/protocol design, Cake Cutting