CS 530: Advanced Algorithms (Fall 2025)

Course Information

Instructor: Nathan Klein

Lectures: Tuesday and Thursday, 9:30 - 10:45am in CAS 326

Links: Syllabus, Piazza, Gradescope

Office Hours: Monday 2:00 - 3:30, Thursday 11:00 - 12:30, and by appointment in CDS 1026. Pooria will have office hours 2:30 - 3:30 in the yellow lounge on the 10th floor of CDS.

Teaching Fellow: Pooria Jalali Farahani

Discussion Sections: Wednesday 10:10am - 11:00 and 11:15am - 12:05 in COM 109.

Prerequisites: Strong undergraduate-level knowledge of algorithms, linear algebra, and probability. Motivated, mathematically mature undergraduate students who have excelled in CS 237 and CS 330 are also welcome.

Grading: Homework (35% with lowest score dropped), midterm (20%), participation and (basic informational) quizzes (20%), and a final exam (25%).

Overview

This course surveys a collection of beautiful ideas in algorithms. We will learn about topics like linear and semidefinite programming, the curse of dimensionality, and spectral graph theory, with the goal of understanding some of the most important conceptual contributions of the field of algorithms over the last 50 years.

Related Textbooks and Materials

Related Courses

Homework

Will be posted on Piazza. The first homework is due 9/10.

Course Schedule

This course is organized around problems computer scientists face in the real world, and explores theoretical tools that can help solve them.

Part 1: NP-Hard problems

What to do when you need to solve an NP-Hard problem. Approximation algorithms, linear and semidefinite programming, and average-case analysis.

Lecture 1, Tuesday 9/2: Course Survey, and Intro to Approximation Algorithms [Notes]After discussing the course setup and an overview of the topics we'll cover, I'll introduce approximation algorithms and survey the basic landscape of that field, defining approximation ratio, hardness of approximation, PTAS, and so on. We'll also show a 1.5 approximation for metric TSP.
Lecture 2, Thursday 9/4: Greedy and Dynamic Programming for Approximation [Notes]Greedy algorithms and dynamic programming are powerful techniques, making them cornerstones of undergraduate algorithms. No surprise, they can often be quite effective as approximation algorithms too. We will see a greedy 2 approximation for the knapsack problem and then a \(1+\epsilon\) dynamic programming approximation for it (an FPTAS).
Lecture 3, Tuesday 9/9: Intro to Linear Programs and the Relax-and-Round Framework [Notes]We will discuss how to model problems as linear programs (LPs), learn a bit about LPs, and then introduce the relax-and-round framework.
Lecture 4, Thursday 9/11: Convex Geometry and Unrelated Parallel Machines [Notes]We'll learn about properties of extreme point solutions to LPs and use it to give a 2-approximation for minimizing the makespan on unrelated parallel machines.
Lecture 5, Tuesday 9/16: Overflow, Quiz 1, and Work Session [Flashcards] [HTML]We will finish up the lecture from last time, have a quiz on the flashcards, and allow time for questions and some work on the homework.
Lecture 6, Thursday 9/18: Randomness, Max Cut, and Non-linear Constraints [Notes]We'll discuss a 1/2 approximation for Max Cut and then, on the road to a better approximation algorithm, discuss the intuition behind semidefinite programming.
Lecture 7, Tuesday 9/23: Max Cut and Semidefinite Programming [Notes]We'll show how the ellipsoid method and a beautiful rounding technique leads to a 0.878 approximation for max cut.
Lecture 8, Thursday 9/25: Concentration Bounds [Notes]A brief recap of important probabilistic tools and an introduction to concentration bounds and why they are useful.
Lecture 9, Tuesday 9/30: Average Case Analysis for Max Cut [Notes]We will use what we learned last time to show that in random graphs, the greedy algorithm is essentially optimal. We will also start discussing how to construct a certificate of near-optimality, and finish that proof in the next class.
Lecture 10, Thursday 10/2: Overflow, Quiz 2, and Work Session [Flashcards] [HTML]We'll finish up the last lecture and have a quiz.

Part 2: Online Algorithms

How to design and evaluate algorithms when your input is not known in advance.

Lecture 11, Tuesday 10/7: Online Algorithms, Competitive Ratios, and the Secretary Problem [Notes]How to design and evaluate algorithms when your data is not known up front, and a brief introduction to primal-dual analysis.
Lecture 12, Thursday 10/9: An Improved Algorithm for Online Bipartite Matching [Notes]We will talk about a simple version of the ranking algorithm and show how it leads to a better-than-1/2 competitive ratio for online bipartite matching.
No Class on, Tuesday 10/14: BU is on a Monday schedule
Lecture 13, Thursday 10/16: Algorithms with PredictionsHow worst-case online analysis and machine learning can work together.
Midterm, Tuesday 10/21: In-class midterm

Part 3: Data

What to do when there's too much data to store it all, how to deal with high dimensional data, and finding low space approximations to matrices.

Lecture 14, Thursday 10/23: Hashing
Lecture 15, Tuesday 10/28: Streaming Algorithms
Lecture 16, Thursday 10/30: High dimensional geometry and the curse of dimensionalityVolume of spheres, near-orthogonal points, JL
Lecture 17, Tuesday 11/4: Linear Algebra review
Lecture 18, Thursday 11/6: Low rank approximation and SVD
Lecture 19, Tuesday 11/11: Overflow, Quiz 3, and Work Session

Part 4: Spectral Graph Theory

Understanding graphs with linear algebra.

Lecture 20, Thursday 11/13: Spectral Graph Theory
Lecture 21, Tuesday 11/18: Cheeger and Clustering
Lecture 22, Thursday 11/20: Overflow, Quiz 4, and Work Session

Part 5: Additional Topics

We will get a glimpse of coding theory, where we learn how to handle situations when data may be lost or corrupted, and a brief introduction to Nash equilibria and game theory.

Lecture 23, Tuesday 11/25: Coding Theory
No Class on, Thursday 11/27: Fall Break
Lecture 24, Tuesday 12/2: Nash Equilibria
Lecture 25, Thursday 12/4: Price of Anarchy
Lecture 26, Tuesday 12/9: Overflow, Course Retrospective