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) 