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:

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:

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

these are documented properly on each problem (including a full reference to the original source -- i.e., author, title, publication date, and so on) and
the text is original -- verbatim copying of a source is not permitted.

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	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.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