Instructor: Bo Waggoner
TAs: Gabe Andrade, Dhamma Kimpara
Time: Tues/Thurs 8:00am  9:15am, ECCS 1B12 and online
Course information and syllabus
News:
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.
There will be no required textbook (readings will be posted or linked).
Course links:
The course does not have a required textbook. Resources:
1  Tue Aug 24  Intro: wordRAM model, bigO notation 
HW1 posted 
Tasks  read syllabus 

Module 1: Combinatorial and Graph Algorithms  
2  Thu Aug 26  Depthfirstsearch, 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 31  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 02  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 07  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 9  Max Flow  Part 1 

Tasks  watch Lecture 5 videos  Sections 1  2 

Resources  
7  Tue Sep 14  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 16  Max Flow  Part 3 

Tasks  watch Lecture 5 videos  Sections 45 

Module 2: Approximation, Online, and Randomized Algorithms  
9  Tue Sep 21  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 23  Intro to Online Algorithms 
HW4 peer feedback 
Tasks  watch Lecture 7 videos 

Resources  
11  Tue Sep 28  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 30  Randomized Algorithms  Part 2 
HW5 peer feedback 
Tasks  watch Lecture 8 videos  Sections 45 

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

14  Thu Oct 07  Recap day 
HW6 peer feedback 
15  Tue Oct 12  No class; exam time (at home) 

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

17  Tue Oct 19  Streaming Algorithms 

Tasks  watch Lecture 10 videos 

Module 3: Continuous, Linear, and Convex Methods  
18  Thu Oct 21  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 26  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 28  Random Walks on Graphs  Part 3 
HW7 peer feedback 
Tasks  watch Lecture 11 videos  Section 5 

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

21  Tue Nov 02  JohnsonLindenstrauss Transform 
HW8 due; HW9 assigned 
Tasks  watch Lecture 12 videos 

22  Thu Nov 4  Singular Value Decomposition 

Tasks  watch Lecture 13 videos 

23  Tue Nov 9  Singular Value Decomposition (continued) 

24  Thu Nov 11  Polynomial Weights 
HW9 due; HW10 assigned 
Tasks  read Penn notes on polynomial weights (skip first page) 

25  Tue Nov 16  ZeroSum Games and the Minimax Theorem 

Tasks  Penn notes on zerosum games 

Resources  
26  Thu Nov 18  ZeroSum Games (continued) 
HW10 due 
27  Tue Nov 29  Linear Programming Part 1 
HW11 assigned 
Resources  Prof. Erickson's LP notes (section H.3 onward) 

28  Thu Dec 02  Linear Programming Part 2 

29  Tue Dec 07  Review day 
HW11 due 
Thu Dec 09  No class  final exam! 

Sat Dec 11, 10pm  Final exam closes, 10:00pm 