Advanced Algorithms

Course Information

Syllabus: Link

Lectures: Tuesday and Thursday, 9:30 - 10:45am in MCS B37

Office Hours: Monday 2:00 - 3:30, Thursday 11:00 - 12:30, and by appointment in CDS 1026

Teaching Fellow: Pooria Farahani

Discussion Sections: Wednesday 10:10am - 11:00 and 11:15am - 12:05 in CDS 801.

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 or final project (25%). Note that final projects replace the final exam, but need to be discussed with me early, with a proposal submitted by 10/24. They should be in groups of 1-3 people.

Overview

This course surveys a collection of beautiful ideas in algorithms. From the curse of dimensionality to spectral graph theory to the price of anarchy, we will focus on understanding the important conceptual contributions of the field of algorithms over the last 50 years.

Homework

Related Textbooks and Materials

Related Courses

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: 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 1, Tuesday 9/2: Admin, Course Survey, Concentration Bounds

Lecture 2, Thursday 9/4: Streaming and Sketching

Lecture 3, Tuesday 9/9: High Dimensional Geometry and the Curse (and Blessing) of Dimensionality

Lecture 4, Thursday 9/11: Low Rank Approximation

Lecture 5, Tuesday 9/16: Overflow, Quiz 1, and Work Session

Part 2: NP-Hard problems

What to do when you need to solve an NP-Hard problem.

Lecture 6, Thursday 9/18: Intro to Approximation Algorithms.

Lecture 7, Tuesday 9/23: The Relax-and-Round Framework

Lecture 8, Thursday 9/25: Convex Geometry and Unrelated Parallel Machines

Lecture 9, Tuesday 9/30: Max Cut and Semidefinite Programming

Lecture 10, Thursday 10/2: Overflow, Quiz 2, and Work Session

Part 3: 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

Lecture 12, Thursday 10/9: Online Bipartite Matching and Primal-Dual Analysis

No Class on Tuesday 10/14: BU is on a Monday schedule

Thursday 10/16: In-class midterm

Part 4: Average Case Analysis and Algorithms with Predictions

Another approach to NP-hard problems is to step away from worst case analysis. We explore how hard problems can be easy on average and how machine learning and worst-case analysis can work together.

Lecture 13, Tuesday 10/21: Average Case Analysis

Lecture 14, Thursday 10/23: Algorithms with Predictions

Part 5: Selfish Agents and Game Theory

What to do when you can't impose a solution because the agents behave selfishly, or you're trying to maximize your utility in a multi-player game.

Lecture 15, Tuesday 10/28: Zero Sum Games, Min-Max Theorem

Lecture 16, Thursday 10/30: Nash Equilibria and the Price of Anarchy

Lecture 17, Tuesday 11/4: Modeling Uncertainty

Lecture 18, Thursday 11/6: Overflow, Quiz 3, and Work Session

Part 6: Coding Theory

What to do when data might be lost or corrupted.

Lecture 19, Thursday 11/11: Intro to Coding Theory

Lecture 20, Tuesday 11/13: Reed-Solomon Codes

Part 7: Random Walks and Spectral Graph Theory

Understanding graphs with linear algebra.

Lecture 21, Tuesday 11/18: Random Walks

Lecture 22, Thursday 11/20: The Laplacian and Sparsest Cut

Lecture 23, Tuesday 11/25: Cheeger's Inequality and Clustering

No Class on Thursday 11/27: Fall Break

Lecture 24, Tuesday 12/2: Overflow, Quiz 4, Course Summary

Part 8: The End

Lecture 25, Thursday 12/4: TBD by class vote (or project presentations depending on the number of groups)

Lecture 26, Tuesday 12/9: Project presentations