## CSE 421: Introduction to Algorithms

#### Shayan Oveis Gharan

MWF 2:30-3:20, MGH 389
Office hours in CSE 636
M/W/F 3:30-4:20
Also, W 1:30-2:20

##### Email list:
Class email list: cse421a_wi18     [archives]

Plesae use Canvas's builtin discussion board for course related questions.

##### Textbook:
Algorithm Design by Jon Kleinberg and Eva Tardos, Addison-Wesley, 2006.

We will cover almost all of chapters 1-8 of the Kleinberg/Tardos text plus some additional material from later chapters. In addition, I recommend reading chapter 5 of Introduction to Algorithms: A Creative Approach, by Udi Manber, Addison-Wesley 1989. This book has a unique point of view on algorithm design.

Another handy reference is Steven Skiena's Stonybrook Algorithm Repository

 Homework 50% Midterm 15-20% Final Exam 30-35%

##### Lecture Slides
Lecture Topic Slides Notes Reading Assignment
Lecture 1 (01/03/18) Stable Matchings pdf pdf Section 1.1 of KT
Lecture 2 (01/05/18) pdf pdf Section 1.2 of KT
Lecture 3 (01/08/18) Overview/Asymptotics pdf pdf Chapter 2 of KT
In class exercise
Lecture 4 (01/10/18) Algrithm Design by Induction pdf pdf Section 5.1,5.2,5.4,5.8 of Manber's Book
Lecture 5 (01/12/18) Graphs (Intro) pdf pdf Section 3.1 of KT
(01/15/18) No Class: Martin Luther King's day
Lecture 6 (01/17/18) Trees / BFS pdf pdf Section 3.1,3.2,3.3 of KT
Lecture 7 (01/19/18) Connected Comps/Bipartite Graphs pdf pdf Sections 3.2, 3.4 of KT
Supplement Notes
Lecture 8 (01/22/18) DFS / Topological Ordering pdf pdf Section 3.2,3.6 of KT
In-class exercise
Lecture 9 (01/24/18) Topological Sort/Interval Scheduling pdf pdf Section 4.1 of KT
Lecture 10 (01/26/18) Interval Scheduling, Interval Partitioning, MST pdf pdf Section 4.1,4.5 of KT
Lecture 11 (01/29/18) MST, Union find pdf pdf Sections 4.5,4.6 of KT
Lecture 12 (01/31/18) Union Find, Dijkstra's Alg pdf pdf Section 4.6,4.4 of KT
Supplement Notes
Lecture 13 (02/02/18) Dijkstra, Closest Points pdf pdf Section 4.4,5.1,5.4 of KT
Lecture 14 (02/05/18) Closest Points, Master Theorem pdf pdf Section 5.4,5.2
Lecture 15 (02/07/18) Integer Multiplication, Median pdf Section 5.5 of KT
supplement notes
Lecture 16 (02/09/18) Vertex Cover / Set Cover pdf pdf pdf
(02/12/18) Midterm
Lecture 17 (02/14/18) Dynamic Programming: Weighted Interval Scheduling, Knapsack pdf pdf Sections 6.1,6.2,6.4 of KT
pdf
Lecture 18 (02/16/18) Weighted Interval Scheduling, Knapsack pdf
(02/19/18) No Class: President's day
Lecture 19 (02/21/18) Sequence Alignment, Longest Path in a DAG pdf Section 6.5,6.6 of KT
Lecture 20 (02/23/18) LIS, Shortest Paths pdf pdf
Lecture 21 (02/26/18) Network Flow pdf Section 7.1,7.2 of KT
Lecture 22 (02/28/18) Max Flow-Min Cut, Bipartite Matching pdf pdf Section 7.2, 7.5 of KT
Lecture 23 (03/02/18) Hall's Condition, Edge Disjoint Path, Image Segmentation pdf pdf section 7.5,7.6 of KT
Lecture 24 (03/05/18) Network Connectivity, Image Segmentation, Reductions pdf pdf Sections 7.10, 8.1 of KT
Lecture 25 (03/07/18) Reductions, NP-Completeness pdf pdf Sections 8.1,8.2 of KT
Lecture 26 (03/09/18) Linear Programming pdf

Homework submission is due via Canvas

 TA Office hours (from October) Room Tianchi Cao Tue 12:00-12:50 CSE 007 Ben Jones Tue 2:00-2:50 CSE 021 Eddie Huang Wed 9:00-9:50 CSE 007 Robbie Weber Thu 10:30-11:20 CSE 007

Exams:

• Midterm exam:
In MGH 389 at the regular class time on Monday, 12-Feb-2018. This will be open book and open notes, hard copies only. The coverage includes all topics through divide and conquer. An old sample midterm is available along with sample solutions. Please try to solve the problems before looking at the asnwer sheet.
There will be a review session on Sunday, 11-Feb-2018 at 4:00 pm in EE 125. Please bring your questions.
• Final exam:
In MGH 389 on Tuesday, 13-Mar-2018 at 2:30-4:20 pm as shown in the UW exam schedule. This will be open book and open notes, hard copies only.
There is an practice final from previous offerings of the course. Here is a solutions to the sample final. Here is another old final. And here is the solution. There will be a review session on Sunday, 11-Mar-2018 at 4:00 pm in EEB 125. Please bring your questions.

Portions of the CSE 421 Web may be reprinted or adapted for academic nonprofit purposes, providing the source is accurately quoted and duly credited. The CSE 421 Web: © 1993-2017, Paul G. Allen School of Computer Science and Engineering, University of Washington.