CSE 347 Analysis of Algorithms, Fall 2017

Sections

Section 1: Tuesday and Thursday, 4:00-5:30 PM, Louderman 458.
Instructor: Brendan Juba
Email:   first initial last name at wustl

Section 2: Monday and Wednesday, 1:00-2: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 course-related communication; we will use it for course announcements. Email of a personal/confidential nature may be directed to the instructors at the emails above.

Recitation Leaders

Teaching Assitants

Grading 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 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 Divide-and-Conquer 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.1-5.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.1-6.2
Jeremy's notes
Last year's lecture notes
R: 9/7
M: 9/11
Lec. 5 Divide-and-Conquer 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 divide-and-conquer
Last year's lecture notes
T: 9/26
W: 9/27
Due:  Homework 3
Assigned:  Homework 4
Lec. 10 Max Flow I
Ford-Fulkerson Algorithm
KT 7.1
Last year's lecture notes
R: 9/28
M: 10/2
Lec. 11 Max Flow II
Min-Cut
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 NP-completeness
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 Average-case 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 On-line 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 On-line 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
Polynomial-time 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 k-means
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