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
Lecture 2: Depth-First-Search, Topological Sort
Lecture 3: Shortest Paths
Lecture 4: Dynamic Programming
Lecture 5: Max Flow and Min Cut
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
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.