SCHEDULE

Week	Date	Lecture Topic	Reading	Work Out	Work Due
1	Jan 08	Big-O, Omega, and Theta, Experimental measurement of algorithms	Chapter 0	PS 1
	Jan 10	Modular Arithmetic Algorithms through GCD	Chapter 1.1 and 1.2
2	Jan 15	Modular Division, Primality	Chapter 1.3
	Jan 17	Cryptography	Chapter 1.4	PS 2	PS 1
3	Jan 21	Martin Luther King Holiday
	Jan 22	Divide and Conquer, Multiplication, Recurrence relations, Mergesort, Medians	Chapter 2.1-2.4
	Jan 24	FFT, PS 2	Chapter 2.6
4	Jan 29	Completion of FFT, PS 3	Chapter 2.6	PS 3	PS 2
	Jan 31	Decomposition of Graphs, Depth First Seach	Chapter 3.1, 3.2, 3.3
5	Feb 05	Directed Graph Search and Strongly Connected Components.	Chapter 3.3, 3.4
	Feb 07	Paths, Distances, BFS, Lengths, Dijkstra's Algorithm	Chapter 4.1 – 4.4	PS 4	PS 3
6	Feb 12	Negative Edges, Bellman-Ford, Paths in DAGs	Chapter 4.6, 4.7
	Feb 14	Review of Chapter 4	Chapter 4
7	Feb 18	President's Day Holiday
	Feb 19	Minimum spanning trees, Cut property, Kruskal's Algorithm	Chapter 5.1	PS 5	PS 4
	Feb 21	Disjoint sets, Prim's Algorithm	Chapter 5.1
8	Feb 26	Huffman Encoding, Horn Formulas, Set Cover	Chapter 5.2 – 5.4
	Feb 28	Review for exam	Chapter 0-4		PS 5
9	Mar 04	Midterm Exam
	Mar 06	Exam results, PS 6		PS 6
	Mar 11	Semester Break
	Mar 13	Semester Break
10	Mar 18	Dags and Dynamic Programming, Longest Increasing Subsequence, Edit Distance	Chapter 6.1, 6.2, 6.3
	Mar 20	Knapsack, Shortest Reliable Path	Chapter 6.4
11	Mar 25	All Shortest Paths, Traveling Salesman	Chapter 6.6	PS 7	PS 6
	Mar 27	Dynamic Programming – Boxes	Chapter 6
12	Apr 01	Linear Programming and Reductions	Chapter 7
	Apr 03	Linear Programming and Reductions	Chapter 7
13	Apr 08	Linear Programming and Reductions	Chapter 7	PS 8	PS 7
	Apr 10	Linear Programming and Reductions	Chapter 7
14	Apr 15	NP Complete Problems	Chapter 8
	Apr 17	NP Complete Problems	Chapter 8
15	Apr 22	Coping with NP Completeness	Chapter 9	PS 9	PS 8
	Apr 24	Quantum Algorithms	Chapter 10
16	Apr 29	Final Exam (9:30 a.m.)			PS 9
	May 02	Graduation