Instructor: Bo Waggoner
TAs: Dhamma Kimpara, Maneesha Papireddygari
Time: Tues/Thurs 9:30am  10:45am, ECCS 1B28 and online
Course information and syllabus
This graduatelevel 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 linearalgebra based methods.
Course links:
The course does not have a required textbook. Resources:
1  Tue Aug 29  Intro: wordRAM model, bigO notation 
HW01 posted 
Tasks  read syllabus 

Module 1: Combinatorial and Graph Algorithms  
2  Thu Aug 31  DFS and topological sort 

Tasks  watch Lecture 2 videos 

Resources  Slides from KleinbergTardos Chapter 3; DPV Chapter 3; Erickson Chapter 5 Section 5.2, 5.4, 5.5, 5.6; and Chapter 6 up through 6.4 

3  Tue Sep 05  Shortest Paths on Graphs 
HW01 due; HW02 posted 
Tasks  watch Lecture 3 videos 

Resources  DPV Chapter 4; Erickson Chapter 8 (skip Section 8.5) 

4  Thu Sep 07  Dynamic Programming  Part 1 

Tasks  watch Lecture 4 videos  Sections 13 

Resources  DPV Chapter 6.1, 6.2, 6.3; Erickson Chapter 3.7 

5  Tue Sep 12  Dynamic Programming  Part 2 
HW02 due; HW03 posted 
Tasks  watch Lecture 4 videos  Sections 46 

Resources  Bo's knapsack notes; DPV Chapter 6.4, 6.6 

6  Thu Sep 14  Max Flow  Part 1 

Tasks  watch Lecture 5 videos  Sections 1  2 

Resources  
7  Tue Sep 19  Max Flow  Part 2 
HW03 due; HW04 posted 
Tasks  watch Lecture 5 videos  Section 3 

Resources  Erickson Chapter 10.1  10.4; advanced, bonus reading: R. Kleinberg lecture notes 

8  Thu Sep 21  Max Flow  Part 3 

Tasks  watch Lecture 5 videos  Sections 45 

Module 2: Approximation, Online, and Randomized Algorithms  
9  Tue Sep 26  Intro to Approximation Algorithms 
HW04 due; HW05 posted 
Tasks  watch Lecture 6 videos 

Resources  KleinbergTardos approx algs slides (through slide 16), Erickson approx algs notes 

10  Thu Sep 28  Intro to Online Algorithms 

Tasks  watch Lecture 7 videos 

Resources  
11  Tue Oct 3  Randomized Algorithms  Part 1 
HW05 due; HW06 posted 
Tasks  watch Lecture 8 videos  Sections 13 

Resources  Peter Cameron probability book Chapter 1.1, 1.2, 1.3, 1.10, and optionally 1.4. 

12  Thu Oct 5  Randomized Algorithms  Part 2 

Tasks  watch Lecture 8 videos  Sections 45 

13  Tue Oct 10  Randomized Algorithms  Part 3 
HW06 due 
Tasks  watch Lecture 8 videos  Section 6 

14  Thu Oct 12  Review day 

15  Tue Oct 17  Hash Tables 

Tasks  watch Lecture 9 videos 

16  Thu Oct 19  No class; exam time (at home)  
17  Tue Oct 24  Streaming Algorithms 

Tasks  watch Lecture 10 videos 

Module 3: Continuous, Linear, and Convex Methods  
18  Thu Oct 26  Random Walks on Graphs  Part 1 

Tasks  watch Lecture 11 videos  Sections 1 and 2 

Resources  Linear algebra review notes (Sections 1,2,3) 

19  Tue Oct 31  Random Walks on Graphs  Part 2 
HW07 due 
Tasks  watch Lecture 11 videos  Sections 3 and 4 

Resources  The Anatomy of a LargeScale Hypertextual Web Search Engine by Sergey Brin and Lawrence Page 

20  Thu Nov 2  Random Walks on Graphs  Part 3 

Tasks  watch Lecture 11 videos  Section 5 

Resources  Blum, Hopcroft, Kannan book Ch 4 up through 4.2 

21  Tue Nov 7  JohnsonLindenstrauss Transform 
HW08 due 
Tasks  watch Lecture 12 videos 

22  Thu Nov 9  Singular Value Decomposition 

Tasks  watch Lecture 13 videos 

Resources  Blum, Hopcroft, Kannan book Ch 3.1  3.5 

23  Tue Nov 14  Online NoRegret Learning 
HW09 due, HW10 assigned 
Tasks  read Lecture 14 notes 

24  Thu Nov 16  ZeroSum Games and the Minimax Theorem 

Tasks  read Lecture 15 notes 

Resources  
Nov 2123  (Fall break) 

25  Tue Nov 28  ZeroSum Games (continued) and Linear Programming (Part 1) 

Tasks  read Lecture 16 notes, Sections 13 

Resources  Prof. Erickson's LP notes (section H.3 onward) 

26  Thu Nov 30  Linear Programming (Part 1 and/or 2) 
HW10 due; HW11 assigned 
Tasks  read Lecture 16 notes, Sections 13 

27  Tue Dec 5  Linear Programming (Part 2) 

Tasks  read Lecture 16 notes, Sections 45 

28  Thu Dec 7  Review or special topics day 
HW11 due 
29  Tue Dec 12  Special topic day  Quantum computing 
Final exam released 
Resources  
30  Thu Dec 14  No class  final exam! 

Sat Dec 16  Final exam due (online): 4pm 