CSE 347 Analysis of Algorithms, Spring 2020

Tuesday and Thursday, 4:00-5:20 PM, Zoom Meeting ID 153 784 362. (Alternative means of connecting to Zoom)
Instructor: Brendan Juba
Office Hours: 5:20-6:00, (after lecture)
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

TA office hours will be held via Zoom for the remainder of the semester.

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 notes and source files for these notes are also posted here. Here is a file containing definitions of additional commands needed to compile the TeX source for the lecture notes: notes-preamble.tex

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