CSE 347 Analysis of Algorithms, Spring 2019

Monday and Wednesday, 4:00-5:30 PM, Hillman 60.
Instructor: Brendan Juba
Office Hours: 5:30-6:30, (after lecture) Hillman 60 -> Jolley 508. (I will answer questions in Hillman 60 following lecture, and return to Jolley 508 when there are no more questions.)
Email:   first initial last name at wustl

Please use the class Piazza board for all course-related communication We will use it for course announcements. Email of a personal/confidential nature may be directed to the instructor at the email above.

Recitation Leaders

Teaching Assistants

Course Information

Course Schedule

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 DatesHomework
Lec. 1 Divide-and-Conquer I
Matrix multiplication and Strassen's algorithm
similar to KT 5.5
summary
1/14 Assigned:  Review Ch. 2 of KT (asymptotic analysis).
Review KT 5.1-5.2 (divide and conquer algorithms)
Lec. 2 Greedy Algorithms I
Scheduling
KT 4.1
summary
1/16 Assigned:  Homework 1
Holiday MLK Day - no lecture 1/21
Lec. 3 Dynamic Programming I
Weighted Scheduling
KT 6.1-6.2
summary
1/23 Assigned:  Review Ch. 3 of KT (on graphs).
Lec. 4 Greedy Algorithms II
Scheduling all requests; start Minimum Spanning Tree
KT 4.5
summary
1/28 Due:  Homework 1
Assigned:  Homework 2
Lec. 5 Greedy Algorithms III
Two algorithms: Kruskal and Prim
finish KT 4.5
summary
1/30
Lec. 6 Divide-and-Conquer II:
The closest pair problem
KT 5.4
summary
2/4 Due:  Homework 2
Assigned:  Homework 3
Lec. 7 Dynamic Programming II
Knapsack and Sequence Alignment
KT 6.4, 6.6
summary
2/6
Lec. 8 Max Flow I
Ford-Fulkerson Algorithm
KT 7.1
summary
2/11 Due:  Homework 3
Assigned:  Homework 4
Lec. 9 Max Flow II
Min-Cut
KT 7.2, start 7.5
summary
2/13 sample midterm exam
Lec. 10 Reductions I
Matchings and more
finish KT 7.5, 7.10, start 8.1
summary
2/18 Due:  Homework 4
Exam 1 Midterm Exam 1
(in class)
2/20
Lec. 11 Reductions II
Relating problems
finish KT 8.1, start 8.2
summary
2/25 Assigned:  Homework 5
Lec. 12 Intractability and NP-completeness
KT finish 8.2, 8.3, start 8.4
summary
2/27
Lec. 13 Intractability via Reductions I
KT finish 8.4, 8.8
summary
3/4 Due:  Homework 5
Assigned:  Homework 6
Review basic probability, KT 13.12, KT 13.3
Lec. 14 Average-case analysis:
Naive trees and hashing
summary
3/6
Holiday Spring Break - no lecture 3/11
Holiday Spring Break - no lecture 3/13
Lec. 15 Randomized algorithms I
From trees to treaps
Roughly, KT 13.5; see also KT 13.9
summary
3/18 Due:  Homework 6
Assigned:  Homework 7
Lec. 16 Intractability via Reductions II
KT 8.5, 8.7
summary
3/20
Lec. 17 Randomized algorithms II
Hashing
KT 13.6
summary
3/25 Due:  Homework 7
Assigned:  Homework 8
Lec. 18 Randomized algorithms III:
Algorithms that may err
KT 13.2, start 4.6
summary
3/27 sample midterm exam
Lec. 19 On-line algorithms I:
Amortized Analysis
KT 4.6, start 13.8
summary
4/1 Due:  Homework 8
Exam 2 Midterm Exam 2
(in class)
4/3
Lec. 20 On-line algorithms II:
Competitive Analysis
KT 13.8, 11.1, 11.3
summary
4/8 Assigned:  Homework 9
Lec. 21 Approximation algorithms I
Random solutions; start LPs
KT 13.4, start 11.6
summary
4/10
Lec. 22 Approximation algorithms II
Relaxing and rounding
KT 11.6
summary
4/15 Due:  Homework 9
Assigned:  Homework 10
Lec. 23 Approximation algorithms III
Polynomial-time approximation schemes
KT 11.8
summary
4/17
Lec. 24 Smoothed Analysis
summary
4/22 Due:  Homework 10
Lec. 25 Span analysis of divide-and-conquer
summary
4/24 Practice final exam