For the 2020 version of this class, click here.
Instructor: Bo Waggoner
TA: Charlie Carlson
Time: Tues/Thurs 11:00am - 12:15pm
Room: ECCR 150 (and recorded/streamed)
Course information and syllabus
This graduate-level course will survey a variety of approaches to designing and rigorously analyzing efficient algorithms. Topics include: combinatorial and graph algorithms; randomized, online, and approximation algorithms; and continuous convex or linear-algebra based methods.
The course does not have a required textbook. Readings will be posted or linked. We will start out with some readings from Algorithms by Dasgupta, Papadimitriou, and Vazirani (DPV), which can be found online for free.
Bespoke lecture notes (does not cover all topics, see schedule!):
Prof. Bo's office hours: Friday 11-noon, ECES 136
TA Charlie's office hours: Tuesday, Wednesday 12:30 - 1:30pm, ECAE 124
| 1 | Tue, Aug 27 | Intro: word RAM model, big-O, stable matching problem |
HW1 posted |
| Resources | Bo's lecture notes: course intro, word-RAM, big-O; notes on stable matching (only up through proof of Theorem 4 / middle of page 2); Kleinberg-Tardos slides | ||
| Module 1: Combinatorial and Graph Algorithms | |||
| 2 | Thu, Aug 29 | Depth-first search, directed acyclic graphs, topological sort |
|
| Reading | Course syllabus; Dasgupta, Papadimitriou, Vazirani (DPV) Chapter 3 |
||
| Resources | Bo's lecture notes: depth-first search and topological sort formalizing proofs from lecture; Slides from Kleinberg-Tardos Chapter 3; Erickson Chapter 5 Section 5.2, 5.4, 5.5, 5.6; and Chapter 6 up through 6.4 |
||
| 3 | Tue, Sep 3 | Breadth-first search, Dijkstra's, Bellman-Ford |
HW2 posted |
| Reading | DPV Chapter 4 |
||
| Resources | Erickson Chapter 8 (skip Section 8.5) ; CLRS Chapter 24 |
||
| 4 | Thu Sep 05 | Dynamic programming (1) |
HW 1 due |
| Reading | DPV Chapter 6.1, 6.2, 6.3 |
||
| Resources | |||
| 5 | Tue Sep 10 | Dynamic programming (2) |
|
| Reading | DPV Chapter 6.4, 6.6 |
||
| 6 | Thu Sep 12 | Flows and cuts |
HW 2 due |
| Reading | |||
| Resources | CLRS Chapter 26.1, 26.2; Bo's lecture notes: flows and cuts |
||
| 7 | Tue Sep 17 | Max flow continued; bipartite matching |
|
| Reading | Kleinberg-Tardos Network Flow 2 slides (only first four pages); Bo's lecture notes: flows and cuts |
||
| Resources | Erickson Chapter 10.1 - 10.4; optionally R. Kleinberg lecture notes (advanced bonus reading) |
||
| 8 | Thu Sep 19 | Finish matchings and recap Module 1 |
HW 3 due |
| Reading | Same as Tuesday |
||
| Module 2: Approximation, Online, and Randomized Algorithms | |||
| 9 | Tue Sep 24 | Intro to Approximation Algorithms |
|
| Reading | Kleinberg-Tardos slides on approx algs up through slide 16 (fourth page) |
||
| Resources | Bo's lecture notes: approximation algs; Jeff Erickson's approximation algs notes |
||
| 10 | Thu Sep 26 | Intro to Online Algorithms |
HW 4 due |
| Reading | Avrim Blum lecture notes (Section 22.4 optional) |
||
| Resources | |||
| 11 | Tue Oct 01 | Bin Packing; Intro to Randomized Algorithms |
Notify of midterm conflicts |
| Reading | Peter Cameron Probability book Chapter 1.1, 1.2, 1.3, and 1.10 (optionally, 1.4); review Bo's lecture notes: online algs |
||
| Resources | Bo's lecture notes: rough probability review, randomized algs |
||
| 12 | Thu Oct 03 | Randomized Algorithms, continued (Max-3SAT, Min-Wt Vertex Cover) |
HW5 due |
| Reading | Kleinberg-Tados slides through slide 30 (page 8); skip contention resolution, guessing cards, and coupon collector sections |
||
| Resources | Bo's lecture notes: rough probability review, randomized algs |
||
| 13 | Tue Oct 08 | Randomized Algorithms, continued (Min-Wt Vertex Cover, Min cut) |
|
| Reading | Bo's lecture notes: randomized algs; rescan last Thurs' reading |
||
| 14 | Thu Oct 10 | Randomized and Online Algorithms |
HW6 due |
| Reading | (none) |
||
| Resources | "Online Bipartite Matching Made Simple" by Birnbaum and Mathieu |
||
| 15 | Tue Oct 15 | Midterm practice day |
|
| 16 | Thu Oct 17 | Midterm Exam |
|
| 17 | Tue Oct 22 | Data Structures and Streaming: Hash Tables |
|
| Reading | |||
| 18 | Thu Oct 24 | Data Structures and Streaming: Bloom Filters |
|
| Reading | Jeff Erickson's lecture notes (read through 6.3) |
||
| Module 3: Continuous, Linear, and Convex Methods | |||
| 19 | Tue Oct 29 | Adjacency Matrices and Random Walks |
|
| Reading | The Anatomy of a Large-Scale Hypertextual Web Search Engine by Sergey Brin and Lawrence Page |
||
| Resources | Linear Algebra Review (notes: sections 1,2,3) |
||
| 20 | Thu Oct 31 | Random Walks cont'd, Markov Chain Monte Carlo |
HW7 due |
| Reading | Blum, Hopcroft, Kannan book Ch. 4 up through 4.2 |
||
| Resources | |||
| 21 | Tue Nov 05 | Dimensionality reduction: Singular Value Decomposition |
|
| Reading | Blum, Hopcroft, Kannan book Chapter 3.1 - 3.5 |
||
| 22 | Thu Nov 07 | Dimensionality reduction continued: Johnson-Lindenstrauss transform |
|
| Resources | |||
| 23 | Tue Nov 12 | Convex Optimization: Gradient Descent |
|
| Reading | Tibshirani slides #3-20 |
||
| Resources | Boyd and Vandenberghe book Ch 3.1.1; Figure 3.2; Ch 3.1.3, 3.1.4; Ch 9.1-9.3 |
||
| 24 | Thu Nov 14 | Online Convex Optimization: Polynomial Weights |
HW8 due |
| Reading | Penn lecture notes (skip the first page!) |
||
| 25 | Tue Nov 19 | Zero-Sum Games and the Minimax Theorem |
|
| Resources | |||
| 26 | Thu Nov 21 | (Online) Convex Optimization and Minmax |
HW9 due Friday |
| Reading | Shalev-Shwartz monograph Chapter 2.0, 2.3, and 2.4 |
||
| 27 | Tue Dec 03 | Online Convex Optimization |
|
| Reading | (previous reading) |
||
| 28 | Thu Dec 05 | Intro to Linear Programming |
HW10 due Sun. |
| Reading | Jeff Erickson's notes (read through Section H.3) |
||
| 29 | Tue Dec 10 | Linear Programming Applications |
|
| 30 | Thu Dec 12 | Review day |
HW11 due Sat. |