Schedule: 15-451 Spring 2006

Class	Month	Day	DW	Topic	Due	Reading
1	Jan	17	Tu	Introduction		Handout
2	Jan	19	Th	Asymptotocs, Recurrences		Handout, 2.1-2.2,5.2
3	Jan	24	Tu	Probabilistic Analysis, Quicksort	Mini 1 due	Handout, 13.3,13.12
4	Jan	26	Th	Selection		Handout, 13.5
5	Jan	31	Tu	Sorting Lower Bounds	HW 1 due	Handout, 2.4
6	Feb	2	Th	Balanced Trees		Handout
7	Feb	7	Tu	Amortized Analysis	Mini 2 due	Handout
8	Feb	9	Th	Splay Trees		Handout
9	Feb	14	Tu	Radix Sort & Tries	HW 2 due (sign up)	Handout
10	Feb	16	Th	Hashing, universal and perfect		13.6
11	Feb	21	Tu	Dynamic Programming I &QUIZ	Mini 3 due	6.1-6.7
12	Feb	23	Th	Dynamic Programming II		6.1-6.7
13	Feb	28	Tu	Graph Algorithms I	HW 3 due	6.8-6.10
14	Mar	2	Th	Graph Algorithms II:		Handout
15	Mar	7	Tu	Graph Algorithms III:	Mini 4 due	Handout
16	Mar	9	Th	Midterm
	Mar	14	Tu	Spring Break
	Mar	16	Th	Spring Break
17	Mar	21	Tu	Network Flows & Matchings I		7.1-7.3 and 7.5-7.6
18	Mar	23	Th	Network Flows & Matchings II	HW 4 due (sign up)	7.7-7.11
19	Mar	28	Tu	Computational Geometry I	Mini 5 due	13.7 and 5.4
20	Mar	30	Th	Computational Geometry II		Handout
21	Apr	4	Tu	FFT and applications	HW 5 due	5.6
22	Apr	6	Th	Competitive Algorithms I		Handout
23	Apr	11	Tu	Competitive Algorithms II & QUIZ	Mini 6 due	Handout
24	Apr	13	Th	Linear Programming I		tba
25	Apr	18	Tu	Linear Programming II	HW 6 due (sign up)	tba
	Apr	20	Th	Spring Carnival
26	Apr	25	Tu	NP-Completeness I		tba
27	Apr	27	Th	NP-Completeness II		tba
28	May	2	Tu	Approximation Algorithms I	HW 7 due	tba
29	May	4	Th	Approximation Algorithms II		tba
30	May	??		Final	When Where?