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**

- Videos - hash tables
- Notes: read Prof. Clauset's notes

**Lecture 10: Streaming Algorithms**

- Videos - streaming
- Notes: read Prof. Jeff Erickson's notes (through Section 6.4)

**Lecture 11: Random Walks on Graphs**

**Lecture 12: Johnson-Lindenstrauss Transform**

**Lecture 13: Singular Value Decomposition**

- Videos - SVD
- Notes: read Blum, Hopcroft, Kannan (Ch. 3.1 up through 3.5)

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.