- 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

- Or Sheffet, osheffet@cs.cmu.edu:
- 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:
- 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: TBA

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

- 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

- 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

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

01/13: (recitation) Warmup problems.

- 01/14:Asymptotic analysis, solving recurrences.

- 01/19:Probabilistic analysis, Randomized Quicksort.

01/20: (recitation) Upper Bounds on Randomized Quicksort.

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

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

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

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

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

- 02/02:Amortized Analysis

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

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

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

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

- 02/16:Universal and Perfect Hashing.

02/17: (recitation) Hashing and DP review.

- 02/18:Dynamic Programming.

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

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

- 03/02: review.

- 03/04: Midterm
- 03/16:Graph Algorithms III: Union-find.

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

- 03/18:Fun with BFS and DFS.

- 03/23:Network Flows and Matchings I.

03/24: (recitation) Examples of problems that can be solved using network flow.

- 03/25:Network Flows II: Edmonds-Karp 1, Edmonds-Karp 2, Min-cost max flow.

- 03/30:Linear Programming.

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

- 04/01:NP-completeness I.

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

- 04/08:NP-completeness II.

- 04/13:Approximation Algorithms.

- 04/20:Online Algorithms.

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

- 04/22:Number theoretic algorithms I.

Number theoretic algorithms II.

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

- 04/29:Intro to machine learning theory.

04/28: (recitation) FFT, review.