- Lectures: Tue/Thu 12-1:20, DH 2210
- Recitations:
- A: Wed 10:30 (DH 2122) - Miguel Araujo [maraujo@cs]
- B: Wed 11:30 (WEH 4709) - Kevin Su [ksu@andrew]
- C: Wed 12:30 (WEH 4709) - Michael (rntz) Arntzenius [marntzen@andrew]
- D: Wed 2:30 (DH 2122) - Eugene Choi [dechoi@andrew]
- E: Wed 3:30 (DH 2105) - Yuzi Nakamura [ynakamur@cs]
- F: Wed 9:30 (DH 1117) - Kristy Gardner [ksgardne@cs]
- G: Wed 4:30 (GHC 4211) - Andrea Klein [andreakl@andrew]
- H: Wed 2:30 (PH A22) - Paul Davis [pauldavi@andrew]

- Ask/answer questions on Piazza
- Use autolab to submit your mini solutions (and check past grades). The powerpoint "tutorial" from class (pdf).
- Course information
- Course Survey done in Lecture #1

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

- Homework 1. Solutions.
- Homework 2. Solutions.
- Homework 3. Solutions.
- Homework 4. Solutions.
- Homework 5. Solutions.
- Homework 6. Solutions.
- Homework 7. Solutions. and practice test.

- 08/27:Intro &
Admin. Karatsuba/Strassen. [Ch 1,2,28.2/1.1,2.1,2.5]

08/28: (recitation) Asymptotic analysis, solving recurrences. [Ch 3,4/Ch 0,2.2]

- 08/29:Linear-time Selection
(randomized and deterministic); recursion trees. [Ch
9/Ch 2.4]

- 09/03:Concrete models and tight
upper/lower bounds. [Ch 8.1/Ch 2.3]
[Mini 1 due]

09/04: (recitation) Problems related to selection and concrete models.

- 09/05:Randomized global min-cut. [Ch 5,7/Virtual Chap - p.29, 140]
- 09/10:Amortized Analysis and a simple amortized dictionary data
structure. [Ch 17/-]
[Hwk 1 due]

09/11: (recitation) Problems related to randomized algorithms and amortization..

- 09/12:Union-find (with appendix on MSTs). [Ch 21/5.1.3,5.1.4]
- 09/17:Universal and Perfect Hashing. [Ch 11/Ch 1.5]
[Mini 2 due]

09/18: (recitation) Quiz preparation + probability refresher.

- 09/19:Quiz + Basic Graph Algorithms.
[Ch 22,23/Ch 3.1-3.3, 4, 5.1]

- 09/24: Streaming Algorithms
[Hwk 2 presentations]

09/25: (recitation) strong connected components from the 9/19 lecture.

- 09/26: Dynamic Programming I: knapsack, matrix product parenthesization. [Ch 15, 24.1, 25.1-25.2/Ch 6]

- 10/01: Dynamic programming II: graph algorithms, including shortest paths (Bellman-Ford) and
all-pairs SP (matrix, Floyd-Warshall)
[Mini 3 due]

10/02: (recitation)

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

- 10/08: Network Flows II: Edmonds-Karp 1, Edmonds-Karp 2, and blocking flows
[Hwk 3 due]

10/09: (recitation) Flows recap, using flows to solve problems - 10/10: Network Flows III: Push-relabel flow algorithms, and Min-Cost Max-Flow. (Example from class.)
- 10/15: Midterm.

10/16: (recitation) Flows to solve problems II - 10/17:Game Theory. [-/Ch 7.5]

- 10/22:Linear Programming I. [Ch 29/Ch 7.1,7.6]
[Hwk 4 presentations]

10/23: (recitation) LP and game theory examples.

- 10/24:Linear Programming II. [Ch 29/Ch 7.4]

- 10/29:NP-completeness I. [Ch 34/Ch 8]
[Mini 4 due]

10/30: (recitation) LPs and duality revision

- 10/31:NP-completeness II.

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

11/06: (recitation) Practice quiz solutions and NP-completeness

- 11/07:Quiz + Online Algorithms.

- 11/12:Machine Learning I.
[Mini 5 due]

11/13: (recitation) Go over quiz, some problems related to SAT and online algorithms

- 11/14:Machine Learning II.

- 11/19:Fast Fourier Transform (FFT). [Ch 30/Ch 2.6]
[Hwk 6 presentations]

11/20: (recitation) Flows and games, FFTs

- 11/21:String Matching Algorithms. [Ch 32/?]

- 11/26:Auctions, VCG, incentive-aware algorithms.

- 12/03:Market Equilibria.

12/04: (recitation) Suffix Trees and VCG - 12/05:Matchings in General Graphs.
[Hwk 7 due]

**Final exam: Friday December 13, 2013, 8:30-11:30am, McConomy.**