CS 314: Algorithms
Spring 2010

Here is this semester's tentative schedule; we will update it as the semester progresses. The listed sections refer to the course textbook by Kleinberg and Tardos; all notes come from Jeff Erickson's algorithms notes.

Date	Topic	Reading	Lecture Notes	Problem session (if any)
Jan 11	Syllabus, big-O review	Any discrete math book	Lecture 1
Jan 13	Induction	Any discrete math book	Lecture 2
Jan 15	Recurrences	Recurrences	Lecture 3
Jan 18	No class - MLK day
Jan 20	Heaps (and pseudocode)	Section 2.5	Lecture 4
Jan 22	Intro to graphs	Chapter 3.1 Graph notes	Lecture 5
Jan 25	Breadth First Search	Chapter 3.2 Graph notes	Lecture 6
Jan 27	Depth First Search	Chapter 3.3, 3.4 Graph notes	Lecture 7
Jan 29	Divide and Conquer: Subset Sum	Divide and Conquer Notes, Sec. 2.2	Lecture 8
Feb 1	Divide and Conquer: Counting inversions	Chapter 5.2-5.3 of book	Lecture 9
Feb 3	Divide and Conquer: Closest Pair of Points	Chapter 5.4 of book	Lecture 10
Feb 5	Divide and Conquer: Multiplication	Lecture Notes on Recursion, Sections 1.7 and 1.8	Lecture 11
Feb 8	Greedy Algorithms: Interval Scheduling	Chapter 4.1 of book Lecture Notes on Greedy Algorithms, Section 4.2	Lecture 12
Feb 10	Greedy Algorithms: Processor Scheduling	Chapter 4.2 of book	Lecture 13
Feb 12	Greedy Algorithms: Huffman codes	Lecture Notes on Greedy Algorithms, Section 4.4	Lecture 14
Feb 15	Greedy Algorithms: Huffman codes Shortest Paths	Lecture Notes on Greedy Algorithms, Section 4.4	Lecture 15
Feb 17	Greedy Algorithms: Shortest Paths	Chapter 4.4 of book	Lecture 16
Feb 19	Greedy Algorithms: Minimum Spanning Trees	Chapter 4.5 of book	Lecture 17
Feb 22	Union-Find	Union Find notes Chapter 4.6 of text	Lecture 18
Feb 24	Dynamic Programming: Intro	Chapter 6.1 of book Dynamic Programming Notes, Sec. 3.1-3.4	Lecture 19
Feb 26	Dynamic Programming: Edit Distance	Sec. 3.5 of Dynamic Programming Notes	Lecture 20
March 1	DP: Longest Increasing Subsequence	Sec. 3.9.2 of Dynamic Programming Notes	Lecture 21
March 3	DP: Independent Set	Sec. 3.7 of Dynamic Programming Notes	Lecture 22
March 5	DP: Subset Sum The Halting Problem	Sec. 3.9.1 of Dynamic Programming Notes	Lecture 23
March 15	Problem Session Day			Worksheet
March 17	Review Session in class
March 19	Midterm
March 22	Recap of midterm P versus NP	NP-Hardness Notes, Sec. 1-3 Chapter 8 of book	Lecture 24
March 24	Satisfiability and Reductions	NP-Hardness Notes, Sec. 4-5 Chpater 8 of book	Lecture 25
March 26	More reductions	NP-Hardness Notes Chpater 8 of book	Lecture 26
March 29	Graph reductions	NP-Hardness Notes Chapter 8 of book	Lecture 27
March 31	Work day on reductions	NP-Hardness Notes Chpater 8 of book		Worksheet
April 2	No class	Off for Good Friday
April 5	No class	Off for Easter Monday
April 7	Approximation: Minimizing makespan	Approximation Notes Chapter 11.1 of book	Lecture 28
April 9	Approximation: Vertex Cover	Approximation Notes	Lecture 29
April 12	Approximation: TSP	Approximation Notes	Lecture 30
April 14	Network Flow: Part 1	Chapter 7 of text Max Flow Notes	Lecture 31
April 16	Network Flow: Part 2	Chapter 7 of text Max Flow Algorithms	Lecture 32
April 19	Network Flow Applications	Chapter 7 of text	Lecture 33
April 21	Circulations	Chapter 7 of text	Lecture 34
April 23	More Network Flow applications	Chapter 7 of text	Lecture 35