Course Schedule

The schedule is approximate and subject to change. Textbook references are provided for each unit; optional references are in square brackets. The referenced texts are as follows:

CLRS — Cormen, Leiserson, Rivest, and Stein, Introduction to Algorithms, Third Edition, The MIT Press (2009).
P — Papadimitriou, Computational Complexity, Addison-Wesley Publishing Company, Inc. (1994).
K — Kozen, The Design and Analysis of Algorithms, Springer-Verlag (1992).
O — O'Donnell, Analysis of Boolean Functions, Cambridge University Press (2014).

Week	Topics	Text	Assignment	Quiz
8/31	Course Introduction	[P 1]
9/5 9/7	Labor Day Computational Models	[P 2.1 – 2.3, 2.6, 3.1, 3.2]
9/12 9/14	Computational Models		HW 1 due
9/19 9/21	Greedy Algorithms and Matroids	CLRS 15, 16	HW 2 due	Quiz 1
9/26 9/28	Amortized Analysis	CLRS 17	HW 3 due
10/3 10/5	Fibonacci Heaps	CLRS 19	HW 4 due	Quiz 2
10/10 10/12	Fibonacci Heaps Max Flow	CLRS 26 [K 16 – 18]	HW 5 due
10/17 10/19	Max Flow			Quiz 3
10/24 10/26	Parallel Computation	CLRS 27 [P 15.1 – 15.3] [K 28 – 31]	HW 6 due
10/31 11/2	Parrallel Computation		HW 7 due	Quiz 4
11/7 11/9	Boolean Functions	[O 1 – 3]	HW 8 due
11/14 11/16 11/17 (Thu) 11/19 (Sat)	Boolean Functions		HW 9 hardcopy due HW 9 softcopy due	Quiz 5
11/21 11/23 11/24	Boolean Functions Thanksgiving Holiday
11/28 11/30	The Complexity Class NP	CLRS 34 [P 7 – 9]	HW 10 Due	Quiz 6
12/5 12/7	The Complexity Class NP		HW 11 Due
12/12	Wrap-up and Review		HW 12 due
12/21	Final Exam	Wednesday, December 21, 1:00 – 3:00