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 