Section 1: Tuesday and Thursday, 4:005:30 PM, Crow 204.
Instructor: Brendan Juba
Office Hours: Tuesday and Thursday, 5:306:15 PM (after class),
Jolley 508
Email:
Section 2: Monday and Wednesday, 1011:30 AM, Lopata Hall 202
Instructor: Robert Utterback
Office Hours: Mondays 11:30 AM12:30 PM and Thursdays 23 PM, Jolley 517
Email:
The Piazza page for this class is located at piazza.com/wustl/spring2017/cse347/home
Homework is an essential component of this course and lectures will sometimes
refer to the results of homework problems.
We will be using electronic homework submissions this semester: your homeworks
will need to be electronically typeset and submitted via Blackboard. Please see
the EHomework Guide for details on how to submit
your homework assignments and retrieve your graded assignments.
The course schedule contains a tentative schedule for
the homework assignments. Homework will be due at 11:59PM
on the indicated day. You have a total of 4 6 late days per semester at
no grade penalty. At most two days late may be used per assignment. If you
have used up these four six late days, your score will be reduced by 25%
off of the total (not yours) score per late day. (Note that days on the
weekend still count as late days!)
Lecture no.  Topic  Dates  Homework 
Lec. 1 
Example analysis of algorithms: Euclid's GCD algorithm. Lecture notes 
T: 1/17 W: 1/18 
Assigned: Review Ch. 2 of KT (asymptotic analysis). 
Lec. 2 
Greedy Algorithms I Scheduling KT 4.1 Lecture notes 
R: 1/19 M: 1/23 
Assigned: Review Ch. 3 of KT (on graphs). 
Lec. 3 
Greedy Algorithms II Minimum Spanning Tree KT 4.5 Lecture notes 
T: 1/24 W: 1/25 
Assigned:
Homework 1 (source files) Review KT 5.15.2 
Lec. 4 
Finish Greedy Algorithms; Start DivideandConquer finish KT 4.5; similar to KT 5.5 Lecture notes 
R: 1/26 M: 1/30 

Lec. 5 
DivideandConquer II: The closest pair problem KT 5.4 Lecture notes 
T: 1/31 W: 2/1 

Lec. 6 
Span analysis of divideandconquer Lecture notes 
R: 2/2 M: 2/6 
Due:
Homework 1 Assigned: Homework 2 
Lec. 7 
Lower bounds in limited models: Is MergeSort optimal? Lecture notes 
T: 2/7 W: 2/8 

Lec. 8 
Dynamic Programming I Weighted Scheduling KT 6.16.2 Lecture notes 
R: 2/9 M: 2/13 

Lec. 9 
Dynamic Programming II Knapsack and Sequence Alignment KT 6.4, 6.6 Lecture notes 
T: 2/14 W: 2/15 
Due:
Homework 2 Assigned: Homework 3 
Lec. 10 
Max Flow I FordFulkerson Algorithm KT 7.1 Lecture notes 
R: 2/16 M: 2/20 

Lec. 11 
Max Flow II MinCut KT 7.2 Lecture notes 
T: 2/21 W: 2/22 

Lec. 12 
Reductions I Matchings and more KT 7.5, 7.10 Lecture notes 
R: 2/23 M: 2/27 
Due:
Homework 3 Sample midterm 
Lec. 13 
Reductions II KT 8.1, start 8.2 Lecture notes 
T: 2/28 W: 3/1 

Lec. 14 
Intractability and NPcompleteness KT finish 8.2, 8.3, start 8.4 Lecture notes 
R: 3/2 M: 3/6 

Midterm  Midterm Exam (in class) 
T: 3/7 W: 3/8 

Lec. 15 
Intractability via Reductions I KT finish 8.4, 8.8 Lecture notes 
R: 3/9 M: 3/20 
Assigned:
Homework 4 
Lec. 16 
Intractability via Reductions II KT 8.5, 8.7 Lecture notes 
T: 3/21 W: 3/22 

Lec. 17 
Averagecase analysis: Naive trees and hashing Lecture notes 
R: 3/23 M: 3/27 
Assigned: Review basic probability, KT 13.12, KT 13.3 
Lec. 18 
Randomized algorithms I From trees to Treaps Roughly, KT 13.5; see also KT 13.9 Lecture notes 
T: 3/28 W: 3/29 
Due:
Homework 4 Assigned: Homework 5 
Lec. 19 
Randomized algorithms II Hashing KT 13.6 Lecture notes 
R: 3/30 M: 4/3 

Lec. 20 
Randomized algorithms III: Algorithms that may err KT 13.2 Lecture notes 
T: 4/4 W: 4/5 

Lec. 21 
Online algorithms I: Amortized Analysis KT 4.6 Lecture notes 
R: 4/6 M: 4/10 
Due:
Homework 5 Assigned: Homework 6 
Lec. 22 
Online algorithms II: Competitive Analysis KT 13.8, 11.1 Lecture notes 
T: 4/11 W: 4/12 

Lec. 23 
Approximation algorithms I Greedy and random KT 11.3, 13.4 Lecture notes 
R: 4/13 M: 4/17 

Lec. 24 
Approximation algorithms II Relaxing and rounding KT 11.6 Lecture notes 
T: 4/18 W: 4/19 
Due:
Homework 6 Assigned: Homework 7 
Lec. 25 
Approximation algorithms III Polynomialtime approximation schemes KT 11.8 Lecture notes 
R: 4/20 M: 4/24 

Lec. 26 
Smoothed analysis Lloyd's algorithm for kmeans Lecture notes 
T: 4/25 W: 4/26 

Review 
Final Review 
R: 4/27 M: 5/1 
Due:
Homework 7 Practice final exam 