CS 7800: Advanced Algorithms

Fall 2025

Course Schedule

This schedule will be updated continuously throughout the term.

Date Topic Reading Notes
Fri
09/05/25
Class 1: Introduction
  • Course Overview
  • Stable Matching
[slides after]
HW1 Out
[pdf] [tex]
Tue
09/09/25
Class 2: Greedy Algorithms I
  • Interval Scheduling
  • Minimizing Lateness
[slides before] [slides after]
KT 4.1–4.2
Fri
09/12/25
Class 3: Greedy Algorithms II
  • Minimum Spanning Tree
  • Duality
[slides before] [slides after]
KT 4.5-4.6
E 7
HW1 Due

HW2 Out
[pdf] [tex]
Tue
09/16/25
Class 4: Dynamic Programming I
  • Fibonacci Numbers
  • Weighted Interval Scheduling
[slides before] [slides after]
KT 6.1-6.2
Fri
09/19/25
Class 5: Dynamic Programming II
  • Segmented Least Squares
[slides before] [slides after]
KT 6.3-6.4
Tue
09/23/25
Class 6: Dynamic Programming III
  • Knapsack
  • Shortest Paths
[slides before] [slides after]
KT 6.4, 6.8-6.9
Fri
09/26/25
Class 7: Network Flow I
  • Ford-Fulkerson
  • Duality
[slides before] [slides after]
KT 7.1-7.2 HW2 Due

HW3 Out
[pdf] [tex]
Tue
09/30/25
Class 8: Network Flow II
  • Choosing Good Paths
[slides before] [slides after]
E 10.6
Fri
10/03/25
Class 9: Linear Programming I
  • Basic Concepts
[slides after]
W I HW3 Due
Tue
10/07/25
Class 10: Exam I
Fri
10/10/22
Class 11: Linear Programming II
  • Duality
  • Minmax Theorem
[slides before] [slides after]
W II, III
Tue
10/14/25
Class 12: Linear Programming III
  • Algorithms: Simplex and Ellipsoid
  • Start Reductions
[slides after]
Fri
10/17/25
Class 13: Applications of Network Flow
  • Maximum Matching
  • Image Segmentation
[slides before] [slides after]
KT 7.5, 7.10 HW4 Out
[pdf] [tex]
Tue
10/21/25
Class 14: Intractability I
  • NP-Completeness
[slides before] [slides after]
KT 8.1-8.5
Fri
10/24/25
Class 15: Intractability II
  • Knapsack
  • Hamiltonian Cycle
[slides after]
Tue
10/28/25
NO CLASS (Jon Traveling)
Fri
10/31/25
Class 16: Approximation I
  • Greedy Approximation
  • Knapsack, Max Coverage
[slides before] [slides after]
HW4 Due

HW5 Out
[pdf] [tex]
Tue
11/04/25
Class 17: Approximation II
  • LP-Based Approximation
  • Vertex Cover, Set Cover
[slides before] [slides after]
Fri
11/07/25
Class 18: Convex Optimization
  • Convex Analysis Basics
  • Gradient Descent
[slides before] [slides after]
Tue
11/11/25
No Class (Veteran's Day)
HW5 Due
Fri
11/14/25
Class 19: Exam II
Tue
11/18/25
Class 20: Randomized Algorithms I
  • TBD
[slides before] [slides after]
HW6 Out
[pdf] [tex]
Fri
11/21/25
Class 21: Randomized Algorithms II
  • TBD
[slides before] [slides after]
Tue
11/25/25
Class 22: Randomized Algorithms III
  • TBD
[slides before] [slides after]
Fri
11/28/25
No Class (Thanksgiving)
Tue
12/02/25
Class 23: Randomized Algorithms IV
  • TBD
[slides before] [slides after]
Fri
12/05/25
Class 24: Randomized Algorithms V
  • TBD
[slides before] [slides after]
HW6 Due
Tue
12/09/25
Class 25: No Regret Learning
  • Jon's Favorite Algorithm
[slides before] [slides after]
Fri
12/12/25
Class 26: Exam III