A Course in Graduate Algorithms

Lecture Notes and Videos

Developed by Bo Waggoner for the University of Colorado, Boulder CSCI 5454: Design and Analysis of Algorithms.

Last updated: 2022.

Sample class: CSCI 5454, Fall 2022.

This page contains lecture notes and videos for a rigorous, proof-based second course in algorithms. It is intended to also be accessible (with work) to students who are a bit rusty or never took undergrad algorithms but have programming and mathematics backgrounds. The first module contains classical material usually encountered in undergrad, while the next two modules introduce more advanced topics.

The "lectures" are different lengths; some are usually covered in one day while others take two or three.

Notes and videos cover the same material, with the notes having a bit more detail (e.g. some proofs omitted from the videos).

Lecture 1: Intro, Word-RAM Model, Big-O

Module 1: Combinatorial and Graph Algorithms

Lecture 2: Depth-First-Search, Topological Sort

Lecture 3: Shortest Paths

Lecture 4: Dynamic Programming

Lecture 5: Max Flow and Min Cut

Module 2: Approximation, Online, and Randomized Algorithms

Lecture 6: Intro to Approximation Algorithms

Lecture 7: Intro to Online Algorithms

Lecture 8: Intro to Randomized Algorithms

Lecture 9: Hash Tables

Lecture 10: Streaming Algorithms

Module 3: Continuous, Linear, and Convex Methods

Lecture 11: Random Walks on Graphs

Lecture 12: Johnson-Lindenstrauss Transform

Lecture 13: Singular Value Decomposition

Lecture 14: Online No-Regret Learning

Lecture 15: Zero-Sum Games

Lecture 16: Linear Programming

Sample schedule for 15-week semester, two classes per week: