CS7800: Advanced Algorithms

Syllabus

Schedule

Assignments

Notes:

• Readings in bold are directly relevant to the lecture and are mandatory. You are expected to do the reading before class so that you will be ready to participate.
• Readings not in bold are for {background, to refresh your memory, for fun}. I strongly encourage you to at least skim them.
• This schedule will be updated regularly as the course goes on. Check back here frequently!

#	Date	Topic	Reading
1	F 9/8	Course Overview, Stable Matching	---
2	T 9/12	Greedy Algorithms: Interval Scheduling, Minimizing Lateness	KT 4.1-4.3 KT 1-3
3	F 9/15	Greedy Algorithms: Shortest Paths, Minimum Spanning Trees	KT 4.4-4.6
4	T 9/19	Divide-and-Conquer Algorithms: Counting Inversions, Selection, Closest Pair	KT 5.1-5.4 Optional: Erickson 1.7
5	F 9/22	Divide-and-Conquer: Integer Multiplication and FFT	KT 5.5-5.6
6	T 9/26	Dynamic Programming: Weighted Interval Scheduling	KT 6.1-6.2
7	F 9/29	Dynamic Programming: Finish Basic Techniques	KT 6.3-6.5 Optional: Erickson 5
8	T 10/3	Dynamic Programing: Edit Distance / Alignments, Shortest Paths	KT 6.6-6.10 Optional: Erickson 6.1
9	F 10/6	Network Flow: Basic Concepts, Duality, Ford-Fulkerson Algorithm	KT 7.1-7.2
10	T 10/10	Network Flow: Choosing Good Paths	KT 7.3-7.4
11	F 10/13	Network Flow: Applications, Wrap-Up	KT 7.5-7.6 KT 7.7-7.13
-	T 10/17	No Class---FOCS	---
12	F 10/20	Midterm	---
13	T 10/24	Intractability: NP-completeness and reductions	KT 8.1-8.5 Optional: Erickson 30.1-30.9
14	F 10/27	Intractability: More hard problems	KT 8.7-8.8 Optional: Erickson 30.10-30.11
-	T 10/31	No Class---Flight Delay :(	---
15	F 11/3	Finish NP-Completeness Introduce Randomized Algorithms	Erickson 13.1-13.3
16	T 11/7	Randomized Algorithms: String Matching and Contention Resolution	KT 13.1 Optional: Review KT 13.12
17	F 11/10	Randomized Algorithms: Global Min-Cut and Expectation	KT 13.2-13.5
18	T 11/14	Randomized Algorithms: Dictionaries, Hashing, Load Balancing	KT 13.6, 13.10
19	F 11/17	Finish Randomized Algorithms Start Linear Programming	---
-	F 11/24	No Class---Thanksgiving	---
-	T 11/28	No Class---Jon in Berkeley	---
20	F 12/1	Linear Programming: Basic Concepts, Simplex Algorithm	Kevin Wayne's Notes I Optional: Erickson 26, 27
21	T 12/5	Linear Programming: Applications, Duality	Kevin Wayne's Notes II
22	F 12/8	Online Learning, Course Wrap-Up	---
23	W 12/13	Final Exam: 1:00-4:30 in 110 WVH	---