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

• Lectures: Monday/Wednesday 2:30pm-3:50pm, 2147.
• Recitation: Thursday 1:00pm-2:00pm, 2052.
• Course information
• Course Policy
• Schedule
• Objectives and Learning Outcomes

Minis

• Mini 1. Due 23 January via email to instructor.
• Mini 2. Due 6 February via email to instructor.
• Mini 3. Due 20 February via email to instructor.
• Mini 4. Due 26 March via email to instructor.
• Mini 5. Due 18 April via email to instructor.

Homeworks

• Homework 1 Due (beginning of class) 30 January.
• Homework 2. Oral Presentations 12-15 February.
• Homework 3. Due (beginning of class) 27 February.
• Homework 4. Oral Presentations 18-20 March. (Appointment Schedule)
• Homework 5. Due (beginning of class) 2 April.
• Homework 6 Oral Presentations 12-15 April. (Appointment Schedule)
• Homework 7 . Due (beginning of class) 25 April.

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.
    
TBA: Final Exam