- 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:
- Log in to https://webmail.andrew.cmu.edu using your andrew id.
- Click on "Folders"
- At the bottom, there is a box called "Subscribe to"
- Type in academic.cs.15-451 and click "Subscribe"
- Repeat for academic.cs.15-451.discuss
- 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

- 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].

- 01/13:Intro & Admin. Karatsuba/Strassen.

01/14: (recitation) Warmup problems.

- 01/15:Asymptotic analysis, solving recurrences.

- 01/20:Probabilistic analysis, Randomized Quicksort.

01/21: (recitation) Problems related to randomized quicksort.

- 01/22:Linear-time Selection
(randomized and deterministic).

- 01/27:Comparison-based lower
bounds for sorting.

01/28: (recitation) Problems related to selection recurrence, upper/lower bounds in concrete models.

- 01/29:Concrete models
and tight upper/lower bounds

- 02/03:Amortized Analysis

02/04: (recitation) Go over hwk1. Problems related to tight bounds and minimax optimality.

- 02/05:Search trees: B-trees
and treaps.

- 02/10:Digit-based
sorting/data-structures (radix sort, tries).

02/11: (recitation) B-tree and treap examples, treap analysis.

- 02/12:Universal and Perfect Hashing.

- 02/17:Dynamic Programming.

10/01: (recitation) Hashing and DP review.

- 02/19:Graph Algorithms I: DFS
and Topological Sorting, DP algs for
shortest paths (Bellman-Ford, Matrix, Floyd-Warshall).

- 02/24:Graph Algorithms II:
Dijkstra, Prim, Kruskal.

02/25: (recitation) Maximum bottleneck path, coupon-collector's problem.

- 02/26: review.

- 03/03: Midterm
- 03/05:Graph Algorithms III: Union-find.

- 03/17:Fun with BFS and DFS.

03/18: (recitation)2-coloring,BFS and DFS trees.

- 03/19:Network Flows and Matchings I.

- 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.

- 03/26:Linear Programming.

- 10/31:NP-completeness I.

04/01: (recitation) Examples of problems that can be solved using linear programming.

- 04/02:NP-completeness II.

04/08: (recitation) Examples of NP-completeness reductions: Integer Programming and 3-Coloring.

- 04/09:Approximation Algorithms.

- 04/14:Online Algorithms.

- 04/21:Number theoretic algorithms I.

Number theoretic algorithms II.

04/22: (recitation) More NP-completeness and number theory.

- 04/23:Fast Fourier Transform (FFT).

- 04/28:Intro to machine learning theory.

04/29: (recitation) FFT, review.