Section 1: Tuesday and Thursday, 4:005:30 PM, Louderman 458.
Instructor: Brendan Juba
Email:
Section 2: Monday and Wednesday, 1:002:30 PM, Lab Sciences 250
Instructor: Jeremy Buhler
Email: jbuhler AT wustl DOT edu
See the "Staff" tab of the class Piazza board for office hours for us and our teaching assistants and other course staff. Please use Piazza for all courserelated communication; we will use it for course announcements. Email of a personal/confidential nature may be directed to the instructors at the emails above.
The schedule of topics for class meetings and of assignments may be subject to change as the semester progresses. Readings marked "KT" refer to sections of the course text relevant to each class. Assignments will be linked from the schedule as they are assigned.
Lecture no.  Topic  Dates  Homework 
Lec. 1 
Example analysis of algorithms: Euclid's GCD algorithm. Jeremy's notes Last year's lecture notes 
M: 8/28 T: 8/29 
Assigned:
Homework 0 Diagnostic Problems (optional) Review Ch. 2 of KT (asymptotic analysis). 
Lec. 2 
DivideandConquer I Matrix multiplication and Strassen's algorithm similar to KT 5.5 Jeremy's notes Last year's lecture notes Lecture notes on "optimal" running times from last year 
W: 8/30 R: 8/31 
Assigned: Review KT 5.15.2 
Lec. 3 
Greedy Algorithms I Scheduling KT 4.1 Jeremy's notes Last year's lecture notes 
T: 9/5 W: 9/6 
Due:
Homework 0 Assigned: Homework 1 
Lec. 4 
Dynamic Programming I Weighted Scheduling KT 6.16.2 Jeremy's notes Last year's lecture notes 
R: 9/7 M: 9/11 

Lec. 5 
DivideandConquer II: The closest pair problem KT 5.4 Jeremy's notes Last year's lecture notes 
T: 9/12 W: 9/13 
Due:
Homework 1 Assigned: Homework 2 Review Ch. 3 of KT (on graphs). 
Lec. 6 
Greedy Algorithms II Scheduling all requests; start Minimum Spanning Tree KT 4.5 Jeremy's notes Last year's lecture notes 
R: 9/14 M: 9/18 

Lec. 7 
Greedy Algorithms III Two algorithms: Kruskal and Prim finish KT 4.5 Jeremy's notes Last year's lecture notes 
T: 9/19 W: 9/20 
Due:
Homework 2 Assigned: Homework 3 
Lec. 8 
Dynamic Programming II Knapsack and Sequence Alignment KT 6.4, 6.6 Jeremy's notes Last year's lecture notes 
R: 9/21 M: 9/25 

Lec. 9 
Span analysis of divideandconquer Last year's lecture notes 
T: 9/26 W: 9/27 
Due:
Homework 3 Assigned: Homework 4 
Lec. 10 
Max Flow I FordFulkerson Algorithm KT 7.1 Last year's lecture notes 
R: 9/28 M: 10/2 

Lec. 11 
Max Flow II MinCut KT 7.2 Last year's lecture notes 
T: 10/3 W: 10/4 
Due:
Homework 4 Assigned: Homework 5 
Lec. 12 
Reductions I Matchings and more KT 7.5, 7.10 Last year's lecture notes 
R: 10/5 M: 10/9 

Lec. 13 
Reductions II Relating problems KT 8.1, start 8.2 Last year's lecture notes 
T: 10/10 W: 10/11 
Due:
Homework 5 
Lec. 14 
Intractability and NPcompleteness KT finish 8.2, 8.3, start 8.4 Last year's lecture notes 
R: 10/12 W: 10/18 

Lec. 15 
Intractability via Reductions I KT finish 8.4, 8.8 Last year's lecture notes 
R: 10/19 M: 10/23 

Midterm  Midterm Exam (in class) 
T: 10/24 W: 10/25 
Assigned:
Homework 6 
Lec. 16 
Averagecase analysis: Naive trees and hashing Last year's lecture notes 
R: 10/26 M: 10/30 
Assigned: Review basic probability, KT 13.12, KT 13.3 
Lec. 17 
Randomized algorithms I From trees to Treaps Roughly, KT 13.5; see also KT 13.9 Last year's lecture notes 
T: 10/31 W: 11/1 
Due:
Homework 6 Assigned: Homework 7 
Lec. 18 
Intractability via Reductions II KT 8.5, 8.7 Last year's lecture notes 
R: 11/2 M: 11/6 

Lec. 19 
Randomized algorithms II Hashing KT 13.6 Last year's lecture notes 
T: 11/7 W: 11/8 
Due:
Homework 7 Assigned: Homework 8 
Lec. 20 
Randomized algorithms III: Algorithms that may err KT 13.2 Last year's lecture notes 
R: 11/9 M: 11/13 

Lec. 21 
Online algorithms I: Amortized Analysis KT 4.6 Last year's lecture notes 
T: 11/14 W: 11/15 
Due:
Homework 8 Assigned: Homework 9 
Lec. 22 
Online algorithms II: Competitive Analysis KT 13.8, 11.1 Last year's lecture notes 
R: 11/16 M: 11/20 

Lec. 23 
Approximation algorithms I Greedy and random KT 11.3, 13.4 Last year's lecture notes 
T: 11/21 M: 11/27 
Due:
Homework 9 
Lec. 24 
Approximation algorithms II Relaxing and rounding KT 11.6 Last year's lecture notes 
T: 11/28 W: 11/29 
Assigned:
Homework 10 
Lec. 25 
Tentative: Approximation algorithms III Polynomialtime approximation schemes KT 11.8 Last year's lecture notes 
R: 11/30 M: 12/4 

Lec. 26 
Tentative: Smoothed analysis Lloyd's algorithm for kmeans Last year's lecture notes 
T: 12/5 W: 12/6 
Due:
Homework 10 
Review 
Final Review 
R: 12/7 M: 12/11 
Practice final exam 