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:

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

Amy An, Section A
Fri 1-2 PM, Meeting ID 646 580 796
Office Hours: Friday, 8 PM - 9PM, Meeting ID 243 322 117
Luxiao Zheng, Section B
Fri 2-3 PM, Meeting ID 727 539 006
Roman Accardi, Section C
Fri 3-4 PM, Meeting ID 322 273 102

Teaching Assistants

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

Jacob Quigley (head TA)
Office Hours: Thursday, 6 PM - 8 PM Meeting ID 566 388 889
Aidan Kelley (secton A assistant)
Office Hours: Sunday, 9 PM - 10 PM, Meeting ID 407 213 758
Ann Zhou (Piazza monitor)
Office Hours: Wednesday, 1:50 PM - 2:50 PM
Pavan Narahari (section B assistant)
Office Hours: Monday, 4 PM - 5 PM, Meeting ID 758 532 130
Edwin Qiu (Piazza monitor)
Office Hours: Tuesday, 10 AM - 11 AM, Meeting ID 698 879 752
Will Wick (Piazza monitor)
Office Hours: Saturday, 1 PM - 3 PM, Meeting ID 858 217 261
Nina Woythaler (Piazza monitor)
Office Hours: Thursday, 11:45 AM - 12:45 PM Meeting ID 665 264 451
Mike Ahn (Piazza monitor)

Course Information

NEW: Guide to on-line participation
NEW: Instructions for taking exams online
UPDATED: Course overview
Policy on collaboration and academic integrity
Guide to submitting homework electronically
Piazza discussion board

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 Dates Homework

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

Lecture no.	Topic	Dates	Homework
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