# 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.