CSE 347 Analysis of Algorithms, Spring 2017

Sections

Section 1: Tuesday and Thursday, 4:00-5:30 PM, Crow 204.
Instructor: Brendan Juba
Office Hours:   Tuesday and Thursday, 5:30-6:15 PM (after class), Jolley 508
Email:   first initial last name at wustl

Section 2: Monday and Wednesday, 10-11:30 AM, Lopata Hall 202
Instructor: Robert Utterback
Office Hours:   Mondays 11:30 AM-12:30 PM and Thursdays 2-3 PM, Jolley 517
Email:   first name dot last name at wustl

Teaching Assistants

Henry Chai
Office Hours:   Thursdays, 10-11 AM, Lopata 201

Roger Iyengar
Office Hours:   Tuesdays, 11 AM-noon, Urbauer 114

Cindy Le
Office Hours:   Mondays, 2-3 PM, Urbauer 116

Renee Mirka
Office Hours:   Mondays, 5-6 PM, Jolley 517

Zimu Wang
Office Hours:   Fridays, 5-6 PM, Urbauer 116

Wenjia Zhang
Office Hours:   Wednesdays, 3-4 PM, Jolley 517

Grading Assistants

Connor Basich
George Fei

Description

Introduces techniques for the mathematical analysis of algorithms, including randomized algorithms and non-worst-case analyses such as amortized and competitive analysis. Introduces the standard paradigms of divide-and-conquer, greedy, and dynamic programming algorithms, as well as reductions. Also provides an introduction to the study of intractability and techniques to determine when good algorithms cannot be designed.

Pre-requisites

Formally, CSE 247. Informally, this class will demand "mathematical maturity." This means that you should be comfortable reading and producing mathematical arguments, i.e., "proofs." A key part of this course will be coming up with and clearly presenting such proofs on the homework.

Textbook

We will use Algorithm Design by Jon Kleinberg and Eva Tardos. Homework problems will be assigned from the text. I will also indicate which sections of the text correspond to lectures, when these are available.

Piazza

All students enrolled in the class are automatically signed up for Piazza, a website for facilitating discussions about classes. Please register as soon as you receive the e-mail, if you haven't already. All questions that are not of a personal nature should be posted to Piazza. You will find it helpful when your classmates have already asked a question for you, with an answer already posted. But, in order to sustain this, you must ask your questions to Piazza as well, and so we will strictly maintain this policy.

The Piazza page for this class is located at piazza.com/wustl/spring2017/cse347/home

Homework, Exams, and Grading

Tentatively, there will be eight homework assignments, a midterm exam, and a final exam. The homeworks will be worth 40% of the grade, the midterm will be worth 25%, and the final exam will be worth 35%. The final exam is cumulative.

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 E-Homework 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!)

Collaboration and Academic Integrity policy

On homeworks, students are highly encouraged to collaborate, and are permitted to use other sources so long as Students should also note their collaborators on their submissions. Each student will be required to produce and submit his or her own, individual writeups.

Group Study Sessions

Again, we stress that collaboration on solving the homework problems is highly encouraged. Thanks to the efforts of students in the class, a weekly group study session has been arranged in Simon 023 7-10 PM on Mondays. Anyone who does not currently have a group to work with is strongly encouraged to attend these sessions.

Disability Resources

Students with disabilities or suspected disabilities are strongly encouraged to both bring any additional considerations to the attention of the instructors and make full use of the University's Disability Resource Center (http://disability.wustl.edu).

Course Website

An up-to-date version of this document appears on the web at http://www.cse.wustl.edu/~bjuba/cse347/s17.

Schedule

The schedule of lecture topics and assignments may be subject to change as the semester progresses.
Lecture no.Topic DatesHomework
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.1-5.2
Lec. 4 Finish Greedy Algorithms;
Start Divide-and-Conquer
finish KT 4.5; similar to KT 5.5
Lecture notes
R: 1/26
M: 1/30
Lec. 5 Divide-and-Conquer II:
The closest pair problem
KT 5.4
Lecture notes
T: 1/31
W: 2/1
Lec. 6 Span analysis of divide-and-conquer
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.1-6.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
Ford-Fulkerson Algorithm
KT 7.1
Lecture notes
R: 2/16
M: 2/20
Lec. 11 Max Flow II
Min-Cut
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 NP-completeness
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 Average-case 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 On-line algorithms I:
Amortized Analysis
KT 4.6
Lecture notes
R: 4/6
M: 4/10
Due:  Homework 5
Assigned:  Homework 6
Lec. 22 On-line 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
Polynomial-time approximation schemes
KT 11.8
Lecture notes
R: 4/20
M: 4/24
Lec. 26 Smoothed analysis
Lloyd's algorithm for k-means
Lecture notes
T: 4/25
W: 4/26
Review Final Review
R: 4/27
M: 5/1
Due:  Homework 7
Practice final exam