Instructor: Bo Waggoner
TAs: Vimal Kakaraparthi, Anish Thilagar
Time: Tues/Thurs 8:00am  9:15am, ECCS 1B12 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 23  Intro: wordRAM model, bigO notation 
HW1 posted 
Tasks  read syllabus 

Module 1: Combinatorial and Graph Algorithms  
2  Thu Aug 25  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 Aug 30  Shortest Paths on Graphs 
HW1 due; HW2 posted 
Tasks  watch Lecture 3 videos 

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

4  Thu Sep 01  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 06  Dynamic Programming  Part 2 
HW2 due; HW3 posted 
Tasks  watch Lecture 4 videos  Sections 46 

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

6  Thu Sep 08  Max Flow  Part 1 

Tasks  watch Lecture 5 videos  Sections 1  2 

Resources  
7  Tue Sep 13  Max Flow  Part 2 
HW3 due; HW4 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 15  Max Flow  Part 3 

Tasks  watch Lecture 5 videos  Sections 45 

Module 2: Approximation, Online, and Randomized Algorithms  
9  Tue Sep 20  Intro to Approximation Algorithms 
HW4 due; HW5 posted 
Tasks  watch Lecture 6 videos 

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

10  Thu Sep 22  Intro to Online Algorithms 

Tasks  watch Lecture 7 videos 

Resources  
11  Tue Sep 27  Randomized Algorithms  Part 1 
HW5 due; HW6 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 Sep 29  Randomized Algorithms  Part 2 

Tasks  watch Lecture 8 videos  Sections 45 

13  Tue Oct 04  Randomized Algorithms  Part 3 
HW6 due 
Tasks  watch Lecture 8 videos  Section 6 

14  Thu Oct 06  Recap day 

15  Tue Oct 11  No class; exam time (at home) 

16  Thu Oct 13  Hash Tables 
HW7 assigned 
Tasks  watch Lecture 9 videos 

17  Tue Oct 18  Streaming Algorithms 

Tasks  watch Lecture 10 videos 

Module 3: Continuous, Linear, and Convex Methods  
18  Thu Oct 20  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 25  Random Walks on Graphs  Part 2 
HW7 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 Oct 27  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 01  JohnsonLindenstrauss Transform 
HW9 assigned 
Tasks  watch Lecture 12 videos 

22  Thu Nov 3  Singular Value Decomposition 
HW8 due 
Tasks  watch Lecture 13 videos 

Resources  Blum, Hopcroft, Kannan book Ch 3.1  3.5 

23  Tue Nov 8  Dimensionality Reduction continued 

24  Thu Nov 10  Online NoRegret Learning 
HW9 due, HW10 assigned 
Tasks  read Lecture 14 notes 

25  Tue Nov 15  ZeroSum Games and the Minimax Theorem 

Tasks  read Lecture 15 notes 

Resources  
26  Thu Nov 18  ZeroSum Games continued 

Nov 2224  (Fall break) 

27  Tue Nov 29  Linear Programming Part 1 
HW10 due; HW11 assigned 
Tasks  read Lecture 16 notes, Sections 13 

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

28  Thu Dec 01  Linear Programming Part 2 

Tasks  read Lecture 16 notes, Sections 45 

29  Tue Dec 06  Review day 
HW11 due 
30  Thu Dec 08  No class  final exam! 

Sat Dec 10  Final exam due (online): 10pm 