Instructor: Bo Waggoner
TA: Gabe Andrade
Time: Tues/Thurs 11:10am  12:25pm
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.
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 25  Intro: wordRAM model, bigO notation 
HW1 posted 
Tasks  read syllabus 

Module 1: Combinatorial and Graph Algorithms  
2  Thu Aug 27  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 Sep 01  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 03  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 08  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 10  Max Flow  Part 1 

Tasks  watch Lecture 5 videos  Sections 1  2 

Resources  
7  Tue Sep 15  Max Flow  Part 2 
HW3 due 
Tasks  watch Lecture 5 videos  Section 3 

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

8  Thu Sep 17  Max Flow  Part 3 
Quiz 1 
Tasks  watch Lecture 5 videos  Sections 45 

Resources  
Module 2: Approximation, Online, and Randomized Algorithms  
9  Tue Sep 22  Intro to Approximation Algorithms 
HW4 assigned 
Tasks  watch Lecture 6 videos 

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

10  Thu Sep 24  Intro to Online Algorithms 

Tasks  watch Lecture 7 videos 

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

Tasks  watch Lecture 8 videos  Sections 45 

13  Tue Oct 06  Randomized Algorithms  Part 3 
HW5 due 
Tasks  watch Lecture 8 videos  Section 6 

14  Thu Oct 08  Recap day 
Quiz 2 
15  Tue Oct 13  Project discussion 

Resources  
16  Thu Oct 15  Hash Tables 
HW6 assigned 
Tasks  watch Lecture 9 videos 

17  Tue Oct 20  Streaming Algorithms 

Tasks  watch Lecture 10 videos 

Module 3: Continuous, Linear, and Convex Methods  
18  Thu Oct 22  Random Walks on Graphs  Part 1 
Project proposals due 
Tasks  watch Lecture 11 videos  Sections 1 and 2 

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

19  Tue Oct 27  Random Walks on Graphs  Part 2 
HW6 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 29  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 03  No class  voting day in U.S. 
HW7 due tomorrow 
22  Thu Nov 05  JohnsonLindenstrauss Transform 
HW8 assigned 
Tasks  watch Lecture 12 videos 

23  Tue Nov 10  Singular Value Decomposition 

Tasks  watch Lecture 13 videos 

24  Thu Nov 12  Polynomial Weights 
Quiz 3 
Tasks  read Penn notes on polynomial weights (skip first page) 

25  Tue Nov 17  ZeroSum Games and the Minimax Theorem 
HW8 due HW9 assigned 
Tasks  Penn notes on zerosum games 

Resources  
26  Thu Nov 19  Linear Programming Part 1 

Tasks  Prof. Erickson's LP notes (through section H.3) 

27  Tue Nov 24  Linear Programming Part 2 
HW9 due project update due HW10 assigned 
Resources  Prof. Erickson's LP notes (section H.4 onward) 

28  Tue Dec 01  Project Presentations 

29  Thu Dec 03  Project Presentations 
Quiz 4 
Mon Dec 7  HW10 due 

Fri Dec 11  Final project writeup due, 7:00pm 