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 