CSE 421: Introduction to Algorithms
Winter, 2018
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]Please send any e-mail questions about the course to cse421-staff@cs.washington.edu.
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
Lecture Slides
| Lecture | Topic | Slides | Notes | Reading Assignment |
|---|---|---|---|---|
| Lecture 1 (01/03/18) | Stable Matchings | Section 1.1 of KT | ||
| Lecture 2 (01/05/18) | Section 1.2 of KT | |||
| Lecture 3 (01/08/18) | Overview/Asymptotics | Chapter 2 of KT In class exercise | ||
| Lecture 4 (01/10/18) | Algrithm Design by Induction | Section 5.1,5.2,5.4,5.8 of Manber's Book | ||
| Lecture 5 (01/12/18) | Graphs (Intro) | Section 3.1 of KT | ||
| (01/15/18) No Class: Martin Luther King's day | ||||
| Lecture 6 (01/17/18) | Trees / BFS | Section 3.1,3.2,3.3 of KT | ||
| Lecture 7 (01/19/18) | Connected Comps/Bipartite Graphs | Sections 3.2, 3.4 of KT Supplement Notes | ||
| Lecture 8 (01/22/18) | DFS / Topological Ordering | Section 3.2,3.6 of KT In-class exercise | ||
| Lecture 9 (01/24/18) | Topological Sort/Interval Scheduling | Section 4.1 of KT | ||
| Lecture 10 (01/26/18) | Interval Scheduling, Interval Partitioning, MST | Section 4.1,4.5 of KT | ||
| Lecture 11 (01/29/18) | MST, Union find | Sections 4.5,4.6 of KT | ||
| Lecture 12 (01/31/18) | Union Find, Dijkstra's Alg | Section 4.6,4.4 of KT Supplement Notes | ||
| Lecture 13 (02/02/18) | Dijkstra, Closest Points | Section 4.4,5.1,5.4 of KT | ||
| Lecture 14 (02/05/18) | Closest Points, Master Theorem | Section 5.4,5.2 | ||
| Lecture 15 (02/07/18) | Integer Multiplication, Median | Section 5.5 of KT supplement notes | ||
| Lecture 16 (02/09/18) | Vertex Cover / Set Cover | |||
| (02/12/18) Midterm | ||||
| Lecture 17 (02/14/18) | Dynamic Programming: Weighted Interval Scheduling, Knapsack | Sections 6.1,6.2,6.4 of KT | ||
| Lecture 18 (02/16/18) | Weighted Interval Scheduling, Knapsack | |||
| (02/19/18) No Class: President's day | ||||
| Lecture 19 (02/21/18) | Sequence Alignment, Longest Path in a DAG | Section 6.5,6.6 of KT | ||
| Lecture 20 (02/23/18) | LIS, Shortest Paths | |||
| Lecture 21 (02/26/18) | Network Flow | Section 7.1,7.2 of KT | ||
| Lecture 22 (02/28/18) | Max Flow-Min Cut, Bipartite Matching | Section 7.2, 7.5 of KT | ||
| Lecture 23 (03/02/18) | Hall's Condition, Edge Disjoint Path, Image Segmentation | section 7.5,7.6 of KT | ||
| Lecture 24 (03/05/18) | Network Connectivity, Image Segmentation, Reductions | Sections 7.10, 8.1 of KT | ||
| Lecture 25 (03/07/18) | Reductions, NP-Completeness | Sections 8.1,8.2 of KT | ||
| Lecture 26 (03/09/18) | Linear Programming | |||
Homeworks [Grading guidelines]:
Homework submission is due via Canvas
- Homework 1 due Thursday, 11-Jan at 5:00PM.
- Homework 2 due Thursday, 18-Jan at 5:00PM.
- Homework 3 due Thursday, 25-Jan at 5:00PM.
- Homework 4 due Thursday, 1-Feb at 5:00PM.
- Homework 5 due Thursday, 8-Feb at 5:00PM.
- Homework 6 due Thursday, 22-Feb at 5:00PM.
- Homework 7 due Thursday, 01-Mar at 5:00PM.
- Homework 8 due Thursday, 08-Mar at 5:00PM.
| 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.