CSE 421: Introduction to Algorithms
Spring, 2019
Shayan Oveis Gharan
MWF 1:30-2:20, CSE2 G01
Office hours in CSE 636
M/W/F 2:30-3:20
Also, T 4:30-5:20
Email list:
Class email list: cse421a_sp19 [archives]Please send any e-mail questions about the course to cse421-staff@cs.washington.edu.
Plesae use Piazza 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 (04/01/19) | Stable Matchings | slides | notes | Section 1.1 of KT |
| Lecture 2 (04/03/19) | Stable Matchings | slides | notes | Section 1.2 of KT |
| Lecture 3 (04/05/19) | Overview, Asymptotics | slides | notes | Chapter 2 of KT in-class exercise |
| Lecture 4 (04/08/19) | Graphs, Trees | slides | notes | Section 3.1 of KT in-class exercise |
| Lecture 5 (04/10/19) | BFS, Connected Comps | slides | notes | Section 3.2,3.3 of KT in-class exercise |
| Lecture 6 (04/12/19) | Bipartiteness | slides | notes | Section 3.4 of KT BFS Notes |
| Lecture 7 (04/15/19) | DFS, Topological Sorting | slides | notes | Section 3.2, 3.6 of KT in-class exercise |
| Lecture 8 (04/17/19) | Greedy Alg: Interval Scheduling, | slides | notes | Section 4.1 of KT |
| Lecture 9 (04/19/19) | Interval Partitioing/MST | slides | notes | Section 4.1, 4.5 of KT |
| Lecture 10 (04/22/19) | Minimum Spanning Tree Problem | slides | notes | Section 4.4,4.6 of KT |
| Lecture 11 (04/24/19) | Union Find DS | slides | notes | Section 4.6 of KT Notes on Union Find, Distinct Edges |
| Lecture 12 (04/26/19) | Dijkstra's Alg | slides | notes | Section 4.4 of KT Dijkstra's Alg |
| Lecture 13 (04/29/19) | Master Theorem, Closest Point | slides | notes | Section 5.1, 5.2 of KT |
| Lecture 14 (05/01/19) | Integer Multiplication | slides | notes | Section 5.4, 5.5 of KT Integer Multiplication Pf |
| Lecture 15 (05/03/19) | Approx Algorithms | slides | notes | Section 5.4 of KT Vertex Cover Approx Alg |
| (05/06/19) Midterm | ||||
| Lecture 16 (05/08/19) | Algorithm Design by Induction | slides | notes | Set Cover Sections 5.1,5.2,5.4,5.8 of Manber's book |
| Lecture 17 (05/10/19) | Weighted Interval Scheduling | slides | notes | Section 6.1,6.2 of KT |
| Lecture 18 (05/13/19) | Knapsack | slides | notes | |
| Lecture 19 (05/15/19) | RNA Secondary Structure, Sequence Alignment | slides | notes | Section 6.4,6.5 of KT |
| Lecture 20 (05/17/19) | Longest Path in a DAG, LIS, Shortest Paths | slides | notes | Section 6.6 of KT |
| Lecture 21 (05/20/19) | Network Flow | slides | notes | Section 7.1 of KT |
| Lecture 22 (05/22/19) | Max Flow-Min Cut | slides | notes | Section 7.2,7.5 of KT |
| Lecture 23 (05/24/19) | Hall's Condition | slides | notes | |
| (05/27/19) No Class: Memorial Day | ||||
| Lecture 24 (05/29/19) | Edge Disjoint Paths, Image Segmentation | slides | notes | Section 7.6 of KT |
| Lecture 25 (05/31/19) | Image Segmentation, Projection Proposal | slides | notes | Section 7.9,7.10,7.11 of KT |
| Lecture 26 (06/03/19) | Polynomial-time Reductions | slides | notes | Section 8.1 of KT |
| Lecture 27 (06/05/19) | NP-Completeness | slides | Section 8.3,8.4 of KT | |
| Lecture 28 (06/07/19) | Polytime Maxflow/Linear Programming | slides | ||
| Final Review (06/09/19) | slides | notes | ||
Homeworks [Grading guidelines]:
Homework submission is due via Canvas
- Homework 1 due Thursday, 11-April at 6:00PM.
- Homework 2 due Thursday, 18-April at 6:00PM.
- Homework 3 due Thursday, 25-April at 5:00PM.
- Homework 4 due Thursday, 02-May at 5:00PM.
- Homework 5 due Thursday, 16-May at 5:00PM.
- Homework 6 due Thursday, 23-May at 5:00PM.
- Homework 7 due Thursday, 30-May at 5:00PM.
- Homework 8 due Thursday, 06-May at 5:00PM.
| TA | Office hours | Room |
| Aditya Saraf | Tue 2:30-3:20 | Allen 021 |
| Guanghao Ye | Wed 11:30-12:20 | Gates 151 |
| Anny Kong | Thu 10:00-10:50 | Gates 151 |
| Justin Mcgowen | Tue 3:30-4:20 | Gates 153 |
| Zongyuan Chen | Mon 10:30-11:20 | Allen 021 |
| Gabriel Cadamuro | ||
| Leiyi Zhang | ||
| Liangyu Zhao | Tue 11:00-11:45 | Gates 153 |
| Alice Zhao |
Exams:
- Midterm exam:
In CSE2 G01 at the regular class time on Monday, 06-May-2019. 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, 05-May-2019 at 3:00 pm in EE 125. Please bring your questions. - Final exam:
In CSE2 G01 on Monday, 10-Jun-2019 at 2:30-4:20 pm as shown in the UW exam schedule. Similar to midterm, it will be open book and open notes, hard copies only.
There is an practice final from previous offerings of the course. here is the solutions to the sample final. Here is another old final. And here is the solution. There will be a review session on Sunday, 09-Jun-2019 at 3:00 pm. in GWN 201. 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.