Date	Topics	Readings
Jan 21: Lecture 1	Introduction	Section 1.1
Jan 26: Lecture 2	Stable Matching Problem Demo GS algorithm	Section 1.2 Sample quiz Solutions of Sample quiz
Jan 28: Lecture 3	Basics of algorithm analysis	Sections 2.1, 2.2, 2.3
Feb 2: Lecture 4	Basics of algorithm analysis	Sections 2.4 Sample quiz Solutions of Sample quiz
Feb 4: Lecture 5	Graphs Quiz 1	Sections 2.4, 3.1 (definition of a graph and examples)
Feb 9: Lecture 6	BFS and DFS Demo on DFS	Sections 3.2, 3.3 Assignment 1
Feb 11: Lecture 7	Testing Bipartiteness; Connectivity in Directed Graphs	Sections 3.4, 3.5 Sample quiz Solutions of Sample quiz Sample quiz
Feb 16: Lecture 8	Topological ordering; Solutions of quizzes	Section 3.6
Feb 18: Lecture 9	Greedy algorithms: Interval scheduling; Interval Partitioning; Minimize Lateness (problem definition) Quiz 2	Sections 4.1, 4.2 (problem definition)
Feb 23: Lecture 10	Greedy algorithms: Minimize Lateness HW1 DUE	Section 4.2
Feb 25: Lecture 11	Greedy algorithms: Dijkstra's algorithm	Section 4.4 Sample quiz HW2: Exercises 3.3, 3.12, 4.3, 4.15
Mar 2: Lecture 12	Greedy algorithms: The Minimum Spanning Tree Problem, Kruskal's, Reverse-Delete, and Prim's algorithms. Application: Clustering	Section 4.5
Mar 4: Lecture 13	Quiz 3
Mar 9: NO CLASS	Spring Break!
Mar 11: NO CLASS	Spring Break!
Mar 16: Lecture 14	Review for Midterm exam Sample Midterm HW2 DUE
Mar 18: Lecture 15	Midterm Exam Syllabus for the Exam The exam is closed book. Limited notes are permitted: one sheet of notes (8.5 x 11 inches, 1 side only). No copying is allowed, i.e., no photocopying of anything and no copying of someone else's notes. The sheet must have the student's name on it and must be turned in with the exam.
Mar 23: Lecture 16	Huffman Codes	Section 4.8
Mar 25: Lecture 17	Divide-and-Conquer 1	Sections 5.1,5.3 Sample quiz Solutions of Sample quiz
Mar 30: Lecture 18	Divide-and-Conquer 2	Section 5.4
Apr 1: Lecture 19	Dynamic Programming 1 Quiz 4	Section 6.1
Apr 6: Lecture 20	Dynamic Programming 2	Sections 6.2, 6.4 Sample quiz
Apr 8: Lecture 21	Solutions of Sample Quiz; Solutions of Midterm Exam
Apr 13: Lecture 22	Dynamic Programming 3	Section 6.6
Apr 15: Lecture 23	Network flow I Demo Ford-Fulkerson algorithm Quiz 5	Assignment 3 Sections 7.1, 7.2
Apr 20: Lecture 24	Network flow III: applications (bipartite matching only)	Sections 7.5
Apr 22: Lecture 25	Polynomial-time reductions	Section 8.1
Apr 27: Lecture 26	ASSIGNMENT 3 DUE! NP and Computational Intractability
Apr 29: Lecture 27	NP-completeness Quiz 6
May 4: Lecture 28	Review
May 6: 1:30-4:15pm	Final Exam