A Course in Graduate Algorithms

Lecture Notes and Videos

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

Last updated: for CSCI 5454, Fall 2021.

This page contains lecture notes and videos for a rigorous, proof-based second course in algorithms. It is intended to also be accessible (with hard work) to students whose skills are a bit rusty or who 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.

Currently, this page contains materials for about 3/4 of the one-semester course; I hope to add materials for the rest in future iterations.

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

Note: the course continues with online no-regret learning, zero-sum games, and linear programming applications. Videos and notes may be added at a future date.