CSE 421: Introduction to Algorithms
Spring, 2020
Shayan Oveis Gharan
MWF 1:30-2:20, Zoom Meeting ID: 166376509
Office hours Zoom Meeting ID: 5948822807
M/W 2:30-3:20
Also, T 4:30-5:20
Email list:
Class email list: cse421a_sp20 [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 (03/30/20) | Course Overview | notes | ||
| Lecture 2 (04/01/20) | Stable Matchings | notes | Stable Matching Example Section 1.1 of KT | |
| Lecture 3 (04/03/20) | Stable Matchings | notes | Section 1.2 of KT | |
| Lecture 4 (04/06/20) | Asymptotics | notes | In class exercise Chapter 2 of KT | |
| Lecture 5 (04/08/20) | Graphs, Trees | notes | In Class Exercise Section 3.1 of KT | |
| Lecture 6 (04/10/20) | BFS | notes | Section 3.2 of KT | |
| Lecture 7 (04/13/20) | Connected Comps, Bipartiteness | pdf Lecture Video | notes | In Class Exercise Section 3.3,3.4 of KT |
| Lecture 8 (04/15/20) | DFS, Topological Sorting | notes | Section 3.2 of KT | |
| Lecture 9 (04/17/20) | Topological Sorting | notes | Section 3.6 of KT | |
| Lecture 10 (04/20/20) | Greedy: Interval Scheduling/Partitioning | notes | Section 4.1,4.5 of KT | |
| Lecture 11 (04/22/20) | Minimum Spanning Tree | Notes | Section 4.4 of KT | |
| Lecture 12 (04/24/20) | Union Find DS, Dijkstra's Alg | Notes | Supplement Notes on Union Find Section 4.6 of KT | |
| Lecture 13 (04/27/20) | Dijkstra's Alg | Notes | Supplement Notes on Dikjstra, Section 4.4 of KT | |
| Lecture 14 (04/29/20) | Divide and Conq: Closest Pair | Notes | Section 5.1,5.2 of KT | |
| Lecture 15 (05/01/20) | Divide and Conq: Integer Multiplication | Section 5.4,5.5 of KT | ||
| (05/04/20) Midterm | ||||
| Lecture 16 (05/06/20) | Approximation Algorithms | Notes | Notes on Set Cover | |
| Lecture 17 (05/08/20) | Algorithm Design By Induction | Notes | Sections 5.1,5.2,5.4,5.8 of Manber's book | |
| Lecture 18 (05/11/20) | DP: Interval Scheduling | Notes | Section 6.1 of KT | |
| Lecture 19 (05/13/20) | DP: Knapsack, | Notes | Section 6.2, 6.4 of KT | |
| Lecture 20 (05/15/20) | RNA Secondary Structure, Seq Alignment | Notes | Section 6.5 of KT | |
| Lecture 21 (05/18/20) | DP: Longest Path in DAG, LIS, Shortest Path | Section 6.6 of KT | ||
| Lecture 22 (05/20/20) | Network Flow | Section 7.1 of KT | ||
| Lecture 23 (05/22/20) | Max Flow-Min Cut, Maximum matching | Section 7.2 of KT | ||
| (05/25/20) No Class: Memorial Day | ||||
| Lecture 24 (05/27/20) | Matchings | Notes | Section 7.6 of KT | |
| Lecture 25 (05/29/20) | Hall's Conidtion, Edge Disjoint Pathsl | Notes | Section 7.6 of KT | |
| Lecture 26 (05/01/20) | Image Segmentation, Polynomial Time Reductions | Notes | Section 7.9, 8.1 of KT | |
| Lecture 27 (06/03/20) | Polynomial-time Reductions | Notes | Section 7.10,7.11,8.3 of KT | |
| Lecture 28 (06/05/20) | NP-completeness | |||
| (06/08/20) Final Exam | ||||
Homeworks [Grading guidelines]:
Homework submission is due via Canvas
- Homework 1 due Thursday, 9-April at 11:59PM.
- Homework 2 due Thursday, 16-April at 11:59PM.
- Homework 3 due Thursday, 23-April at 11:59PM.
- Homework 4 due Thursday, 30-April at 11:59PM.
- Homework 5 due Thursday, 14-May at 11:59PM.
- Homework 6 due Thursday, 21-May at 11:59PM.
- Homework 7 due Friday, 28-May at 11:59PM. Here is Tex file, and preamble.tex
- Homework 8 due Friday, 05-May at 11:59PM.
| TA | Office hours | Meeting Id |
| Anny Kong | Mon 11:30-12:20 | 7980928356 |
| Andrey Ryabtsev | Mon 3:30-4:20 | 5690154666 |
| Jason Shiyoji Waataja | Tue 10:00-10:50 | 4237094217 |
| Liangyu Zhao | Tue 12:30-1:20 | 3215688552 |
| Ansh Nagda | Tue 1:30-2:20 | 3246340598 |
| Joy He | Tue 3:30-4:20 | 9398646856 |
| Ivy Wang | Wed 9:30-10:20 | 2597803488 |
| Siddharth Iyer Vaidyanathan | Wed 3:30-4:20 | 9225427905 |
| Xihu Zhang | Wed 4:30-5:20 | 8563721386 |
| Sally Dong | Thu 10:30-11:20 | 6744319699 |
| Alex Fang | Thu 11:30-12:20 | 9763086367 |
Exams:
- Midterm exam:
This will be open book and open notes, hard copies only. You are not allowed to access internet. 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. I will upload the solutions by Friday. There will be a review session on Sunday, 03-May-2020 at 3:00 pm, Zoom Meeting ID: 5948822807. Please bring your questions. Here are recorded video, Slides, Notes for the review session. - Final exam:
At 2:30PM-4:45 on Monday, 8-Jun-2020. 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, 07-Jun-2020 at 3:00 pm. in Zoom Meeting ID: 5948822807. Please bring your questions. More Practice Problems Here are slides for reviewing final. Notes and recorded video.
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.