CMU 15-451 (Algorithms), Spring 2009

Instructor: Manuel Blum

TAs: David Abraham, Pranjal Awasthi, Maxim Makatchev, Daniel Nuffer

General info

• Lectures: Tue/Thu 12-1:20, Wean 7500.
• Recitations:
  • A: Wed 11:30 (DH 1217) - Daniel Nuffer
  • B: Wed 2:30 (Wean 6423) - Pranjal Awasthi
  • C: Wed 3:30 (Wean 5302) - David Abraham
  • D: Wed 1:30 (Wean 5312) - Maxim Makatchev
• Course information
• Schedule
• The course bulletin boards are: academic.cs.15-451 (for announcements) and academic.cs.15-451.discuss (for general discussion). To sign up to these boards:
  1. Log in to https://webmail.andrew.cmu.edu using your andrew id.
  2. Click on "Folders"
  3. At the bottom, there is a box called "Subscribe to"
  4. Type in academic.cs.15-451 and click "Subscribe"
  5. Repeat for academic.cs.15-451.discuss
  6. Post to the discussion board by sending email to post+academic.cs.15-451.discuss@andrew.cmu.edu from your andrew account
• Final Exam: Friday, May 8, 5:30pm - 8:30pm

Practice Exams

• Practice Quiz 1.
• Practice Midterm.
• Practice Quiz 2.
• Practice Final Exam.

Exams

• Quiz 1 Solutions.
• Midterm Solutions.
• Quiz 2 Solutions.

Minis

• Mini 1. Solutions
• Mini 2. Solutions
• Mini 3. Solutions.
• Mini 4. Solutions.

Homeworks

• Homework 1 [ps, pdf]. Solutions [ps, pdf].
• Homework 2 [ps, pdf]. Solutions pdf
• Homework 3 [pdf]. Solutions pdf.
• Homework 4 [pdf]. Solutions pdf.
• Homework 5 [pdf]. Solutions [pdf].
• Homework 6 [pdf]. Solutions [pdf].

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

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