CMU 15-451 (Algorithms), Spring 2010

Instructor: Manuel Blum

TAs: Dafna Shahaf, Or Sheffet, Sam Tetruashvili, Andrey Vadim Grinshpun, Tilak Sharma

General info

• Lectures: Tue/Thu 12-1:20, Wean 7500.
• Recitations:
  • E: Wed 10:30 (DH 1217) - Or Sheffet
  • A: Wed 11:30 (DH 1217) - Tilak Sharma
  • B: Wed 1:30 (DH 1217) - Dafna Shahaf
  • C: Wed 2:30 (DH 1217) - Andrey Vadim Grinshpun
  • D: Wed 3:30 (DH 1217) - Sam Tetruashvili
• Office Hours:
  • Or Sheffet, osheffet@cs.cmu.edu:
    Tuesday 16:00-17:00 at GHC 7004. Students can email me if they want to meet at a different time.
  • Tilak Sharma, tilaks@andrew.cmu.edu:
    Monday 4:30-5:30 at GHC 7th floor lounge. Students can email me if they want to meet at a different time.
  • Andrey Vadim Grinshpun, agrinshp@andrew.cmu.edu:
    Monday 2:30-3:30 at WH 6th floor couches or WH 6215, depending on availability.
  • Sam Tetruashvili, samt@cmu.edu:
    Wednesday 4:30-6:00 at GHC 7th floor lounge
  • Dafna Shahaf, dshahaf+451@cs.cmu.edu:
    Friday 4:00-5:00 at GHC 7th floor lounge
• Course information
• Course policy (pdf)
• 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: TBA

Practice Exams

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

Exams

• Midterm.
• Midterm Solution.

Minis

• Mini 1 (due Tuesday Jan 19, 11:59pm) Solutions
• Mini 2 (due Tuesday Feb 2, 11:59pm) Solutions (q1, q3) Solutions (q2)
• Mini 3 (due Thu Feb 18, 11:59pm) Solutions
• Mini 4 (due Thu Mar 4, 11:59pm) Solutions
• Mini 5 (due Thu Apr 1, 11:59pm) Solutions
• Mini 6 (due Thu Apr 29, 11:59pm) Solutions

Homeworks

• Homework 1 (due Thursday Jan 28, 12:00pm in class) Solutions
• Homework 2 (signup sheet) Solutions
• Homework 3 (due Thursday Feb 25, 12:00pm in class) (NOTE: change to Q2 part 2, we now only require an asymptotic lower bound) Solutions
• Homework 4 (due Thursday Mar 25, 12:00pm in class) Solutions
• Homework 5 (signup sheet) Solutions
• Homework 6 (optional! due Monday May 3rd noon) Solutions

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

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