CS 7800: Advanced Algorithms

Fall 2022

Course Schedule

Reading Code: KT = Kleinberg-Tardos; E = Erickson; W = Kevin Wayne's Notes; R = Tim Roughgarden's Notes; A = Sepehr Assadi's Notes

Date	Topic	Reading	Notes
Fri 09/09/22	Lecture 1: Introduction Course Welcome Stable Matching [slides]	KT 1.1	HW1 Out [pdf] [src]
Tue 09/13/22	Lecture 2: Greedy Algorithms I Interval Scheduling Minimizing Lateness [slides]	KT 4.1-4.2
Fri 09/16/22	Lecture 3: Greedy Algorithms II Minimum Spanning Tree [slides]	KT 4.5-4.6 E 7	HW1 Due HW2 Out [pdf] [src]
Tue 09/20/22	Lecture 4: Dynamic Programming I Weighted Interval Scheduling Log Cutting [slides]	KT 6.1-6.3
Fri 09/23/22	Lecture 5: Dynamic Programming II Knapsack Shortest Paths [slides]	KT 6.4 KT 6.8-6.9
Tue 09/27/22	Lecture 6: Network Flow I Ford-Fulkerson Duality [slides]	KT 7.1-7.2
Fri 09/30/22	Lecture 7: Network Flow II Choosing Good Paths [slides]	KT 7.3 E 10.6	HW2 Due HW3 Out [pdf] [src]
Tue 10/04/22	Lecture 8: Applications of Network Flow Maximum Bipartite Matching Image Segmentation [slides]	KT 7.5 KT 7.10
Fri 10/07/22	Lecture 9: Generalizing Network Flow Minimum Cost Perfect Matching [slides]	KT 7.13
Tue 10/11/22	Lecture 10: Linear Programming I Basic Concepts Simplex [slides]	W I, II
Fri 10/14/22	Lecture 11: Linear Programming II Duality Ellipsoid [slides]	W III	HW3 Due HW4 Out [pdf] [src]
Tue 10/18/22	Lecture 12: Intractability I (Guest Lecture: Lydia Zakynthinou) NP-Completeness First Reductions [slides]	KT 8.1-8.8
Fri 10/21/22	Lecture 13: Intractability II (Guest Lecture: Lydia Zakynthinou) More Reductions PSPACE-Completeness [slides]	KT 9.*
Tue 10/25/22	Lecture 14: Approximation I Knapsack Maximum Coverage [slides]	R I
Fri 10/28/22	Lecture 15: Approximation II Set Cover Vertex Cover [slides]	R II	HW4 Due
Tue 11/01/22	Midterm Exam (In Class)
Fri 11/04/22	Lecture 16: Randomization I Randomness in Algorithms Discrete Probability [slides]	E 1.1-1.5	HW5 Out [pdf] [src]
Tue 11/08/22	Lecture 17: Randomization II Balls and Bins String Matching [slides]	KT 13.9-13.10 E 7.1-7.3
Fri 11/11/22	No Class (Veteran's Day)
Tue 11/15/22	Lecture 18: Randomized III Hash Tables Randomized Hash Families [slides]	E 5.1-5.6
Fri 11/18/22	Lecture 19: Randomized IV Universal Hash Families [slides]	E 5.7	HW5 Due
Tue 11/22/22	No Class (Pre-Thanksgiving)
Fri 11/25/22	No Class (Thanksgiving)
Tue 11/29/22	Lecture 20: Streaming I Reservoir Sampling [slides]	A 1.1-1.3	HW6 Out [pdf] [src]
Fri 12/02/22	Lecture 21: Streaming II Distinct Elements [slides]	A 2.1-3
Tue 12/06/22	Lecture 22: Data Compression Huffman Codes [slides]	KT 4.8
Fri 12/09/22	Lecture 23: No-Regret Learning Jon's Favorite Algorithm [slides]	R I	HW6 Due
Tue 12/13/22	Cookies and Companionship 1:30-3:00pm in ISEC 623		Final Out (Gradescope)