CSE 5401 Advanced Algorithms, Fall 2025

Tuesday/Thursday, Seigle 301 10-11:30 am
Instructor: Brendan Juba
Teaching assistants: Kris Nilsson, Charles Troutman, Yimu Liu, Haixin Zhou
3 credits

Course goals and content

This course provides an overview of techniques for the design and analysis of algorithms for the kinds of problems that you are likely to encounter at the graduate level. The contrast with undergraduate algorithms is as follows: whereas at the undergraduate level we focused on the standard paradigms for obtaining optimal worst-case solutions to problems, such solutions are intractable for nearly all of the problems we will consider. We will draw on techniques from continuous optimization, linear algebra, and probability to develop a collection of approaches that yield fast algorithms for approximate solutions for a wide variety of problems. We will also consider a variety of problem settings, including on-line and streaming settings. As in undergraduate algorithms, our goal is still to understand why the methods work and how to quantify their efficiency.

Because algorithms and their analysis can be subtle, trying to understand their behavior based solely on informal arguments (sometimes called "hand-waving") is fraught with peril. The safest way to avoid being wrong is to pursue rigorous correctness and efficiency arguments (i.e. proofs). We will strive for mathematically rigorous argument, both in class and on your assignments. An important part of learning about algorithms is learning how to argue rigorously about their behavior; this will enable you to understand precisely why they work, and therefore in what ways the algorithms can or cannot be extended or modified to solve variations of the original task or meet other criteria. After successfully completing this class, you should be able to understand and rigorously analyze a wide variety of algorithms encountered in graduate study.

Prerequisites

Formally, this class requires CSE 3407, Analysis of Algorithms as well as basic linear algebra. We will briefly review the main paradigms of worst-case optimal polynomial-time algorithms, greedy and dynamic programming, as well as the theory of intractability from CSE 3407, but we expect some prior familiarity with these topics. We will recall the main results of linear algebra (e.g., eigenvectors/eigenvalues) and tools from probability (tail inequalities) but we will utilize these extensively. We also expect that you can make arguments in support of algorithmic correctness and complexity.

Informally, CSE 5401 demands "mathematical maturity" -- the ability to read, understand, and produce rigorous mathematical arguments (i.e. proofs). We will use basic logical techniques such as induction, proof by contradiction, and proof by cases extensively, as well as tools from probability, linear algebra, optimization, and combinatorics. You will practice communicating your ideas in the form of proofs through your classroom interactions and homework assignments.

Textbooks

There is no required textbook for the course, but the following references may be helpful.

Breakdown of final grade

The breakdown of your final grade will be as follows:

Any curving of exams to adjust for observed difficulty is at the sole discretion of the instructors. We do not anticipate curving homework grades, and we will not drop exam scores.

Course schedule, lecture notes, and assignments

Lecture no.Topic DatesHomework
Lec. 1 Greedy Algorithms (review)
Minimum Spanning Tree

8/26
Lec. 2 Dynamic Programming and PTAS
Knapsack
Williamson and Shmoys, Section 3.1
notes
8/28 Assigned:  Homework 1
Lec. 3 Intractability (NP completeness review)
notes
9/2
Lec. 4 Hashing and the power of two choices
Mitzenmacher & Upfal second edition
Chapter 15, sections 15.1-15.3 (pairwise independence)
Section 17.1 (power of two choices)
notes
9/4 Due:  Homework 1
Assigned:  Homework 2
Lec. 5 Multiplicative weights
Blum, Hopcroft, and Kannan, Section 5.10.6
(The problem is called "experts learning" there.)
notes
9/9
Lec. 6 Markov chains
Mitzenmacher & Upfal, Chapter 7
notes
9/11 Due:  Homework 2
Assigned:  Homework 3
Lec. 7 Games
Blum, Hopcroft, and Kannan, Section 5.11
(Near the end of "Boosting".)
notes
9/16
Lec. 8 Sparse cuts and conductance
An alternative to Cheeger's inequality: Blum, Hopcroft, and Kannan directly bound the mixing time in terms of the conductance in Section 4.4
notes
9/18 Due:  Homework 3
Assigned:  Homework 4
Lec. 9 Gradient descent
Blum, Hopcroft, Kannan, Section 10.5
(only covers the first part of lecture)
notes
9/23
Lec. 10 Streaming algorithms
Blum, Hopcroft, Kannan Sections 6.2.1 and 6.2.3
notes
9/18 Due:  Homework 4
Lec. 11 Equivalence of counting and sampling
Mitzenmacher and Upfal Section 11.3
(presented in terms of counting independent sets)
notes
9/30
Exam 1 Midterm Exam 1
(in class)
10/2
Lec. 12 Solving convex programs with separation oracles using Ellipsoid
Blum, Hopcroft, Kannan, Section 10.6.1
The separation oracle framework is also discussed in Williamson and Shmoys, Section 4.3
notes
10/9 Assigned:  Homework 5
Lec. 13 Coupling for sampling colorings
Mitzenmacher and Upfal, Section 12.2 (Example: section 12.2.2) and 12.5 (Theorem 12.7)
notes
10/14
Lec. 14 Linear Program Duality
Williamson and Shmoys, Appendix A
notes
10/16 Due:  Homework 5
Assigned:  Homework 6
Lec. 15 Dimensionality reduction
Blum, Hopcroft, and Kannan, Section 2.7
(Gaussian version)
notes
10/21
Lec. 16 Semidefinite programming
Williamson and Shmoys, Section 6.1
(also see Chapter 6 Chapter Notes for discussion of the algorithms for solving semidefinite programs)
Blum, Hopcroft, and Kannan, Section 10.8
notes
10/23 Due:  Homework 6
Assigned:  Homework 7
Lec. 17 Primal-dual algorithms
Williamson and Shmoys Sections 7.1-7.2
notes
10/28
Lec. 18 Path coupling for counting independent sets
Mitzenmacher and Upfal, Section 12.6
notes
10/30 Due:  Homework 7
Assigned:  Homework 8
Lec. 19 On-line algorithms via primal-dual
notes
11/4
Lec. 20 Randomized rounding of semidefinite programs
Williamson and Shmoys, Sections 6.2 and 6.3
(also briefly described in Blum, Hopcroft, and Kannan, Section 10.8)
notes
11/6 Due:  Homework 8
Assigned:  Homework 9
Lec. 21 Smoothed analysis of k-means
The k-means objective and Lloyd's algorithm are discussed in Blum, Hopcroft, and Kannan Section 7.2 (but not the smoothed analysis)
notes
11/11
Lec. 22 Primal-dual algorithm for Steiner Forest
Williamson and Shmoys, Section 7.4
notes
11/13 Due:  Homework 9
Lec. 23 Randomized rounding for coloring
Williamson and Shmoys Section 6.5
notes
11/18
Exam 2 Midterm Exam 2
(in class)
11/20 Assigned:  Homework 10
Lec. 24 Locality-sensitive hashing
notes
12/2
Lec. 25 Course summary
notes
12/4 Due:  Homework 10