- Lectures: Tue/Thu 12-1:20, DH 2210
- Recitations:
- A: Wed 10:30 (BH 136A) - Patrick Xia [pjx@cs]
- B: Wed 11:30 (WEH 4709) - Fan Xiang [fxiang@andrew]
- C: Wed 12:30 (WEH 4709) - Andrew McKinnie [amckinni@andrew]
- D: Wed 2:30 (WEH 5421) - John Wright [jswright@cs]
- E: Wed 3:30 (DH 2105) - Dennis Meng [dmeng@andrew]
- F: Wed 9:30 (DH 1117) - Ankit Sharma [ankits@cs]
- G: Wed 4:30 (GHC 4211) - Carol Wang [carolwan@cs]

- Course information
- Final exam: the registrar has scheduled our final exam to be Dec 17 8:30am-11:30am (one of the 15-651 sections somehow lists an incorrect date).

- Mini 1. Due 11:59pm Sept 4.
- Mini 2. Due 11:59pm Sept 18.
- Mini 3. Due 11:59pm Oct 2.
- Mini 4. Due 11:59pm Oct 16.
- Mini 5. Due 11:59pm Nov 29.

- Homework 1. Solutions.
- Homework 2. Solutions.
- Homework 3.
Solutions.
Clarification: on problem 1, you
*can*use a 3rd stack to temporarily store elements being transferred between the two main stacks. - Homework 4. Solutions.
- Homework 5. Solutions.
- Homework 6. Solutions.
- Homework 7. Solutions.

- 08/28:Intro & Admin. Karatsuba/Strassen.

08/29: (recitation) Warmup problems.

- 08/30:Asymptotic analysis,
solving recurrences. [Ch 1-4/Ch 0,1.1,2.1-2.2]

- 09/04:Probabilistic
analysis, Randomized Quicksort. [Ch 5,7/-] [Mini 1 due]

09/05: (recitation) Problems related to randomized quicksort, insertion sort.

- 09/06:Linear-time Selection
(randomized and deterministic), sorting lower
bounds. [Ch 8.1,9/Ch 2.4]

- 09/11:Concrete models
and tight upper/lower bounds. [Hwk 1 due]

09/12: (recitation) Problems related to selection, tight upper/lower bounds.

- 09/13:Game Theory. [-/Ch 7.5]

- 09/18:Universal and
Perfect Hashing. [Ch 11/Ch 1.5] [Mini 2 due]

09/19: (recitation) Hashing and prep for quiz.

- 09/20:Amortized Analysis (part
1, part 2, part 3)
+ Quiz. [Ch 17/-]

- 09/25:Splay trees [Hwk 2
presentations]

09/26: (recitation) Tree rotations.

- 09/27:Augmenting search trees
[Ch 14]

- 10/02:Dynamic
Programming, incl shortest paths (Bellman-Ford) and
all-pairs SP (matrix,
Floyd-Warshall). [Ch 15, 24.1, 25.1-25.2/Ch 6] [Mini 3 due]

- 10/04:Graph Algorithms I:Depth First Search
Strongly-connected
components and
biconnected
components

- 10/09:Link/Cut Trees [Hwk 3 due]

10/10: (recitation) SCCs.

- 10/11:Network Flows and
Matchings I. [Ch 26/7.2-7.3]

- 10/16:Network Flows II:
Edmonds-Karp 1, Edmonds-Karp 2, Min-cost max flow. [Mini 4 due]

- 10/18: Midterm.

- 10/23:Matchings in general graphs. [Hwk 4 presentations]

10/24: (recitation) Flows and cuts.

- 10/25:Linear
Programming I. [Ch 29/Ch 7.1,7.6]

- 10/30:NP-completeness
I. [Ch 34/Ch 8]

10/31: (recitation) Linear programming and NP-completeness examples.

- 11/01:NP-completeness
II.

- 11/06:Approximation
Algorithms. [Ch 35/Ch 9.2] [Hwk 5 due]

11/07: (recitation) Go over practice quiz. NP-completeness examples. - 11/08:Linear Programming II. [Ch 29/Ch 7.4]

- 11/13:Online Algorithms+ Quiz.

11/14: (recitation) More on complexity classes. - 11/15:Machine Learning, online learning algorithms.

- 11/20:Two Algorithms for Closest Pair
[O(n) expected]
[O(n log n)]
[Hwk 6 presentations]

- 11/27:String Matching I.

- 11/29:Fast Fourier
Transform (FFT). [Ch 30/Ch 2.6] [Mini 5 due]

- 12/04:String Matching II, Suffix Trees
[TXT,PDF]

- 12/06:Shortest Common Superstring (not on test). [Hwk 7 due]