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

Grading Scheme (Roughly):

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


Lecture Slides
Lecture Topic Slides Notes Reading Assignment
Lecture 1 (03/30/20) Course Overview pdf notes
Lecture 2 (04/01/20) Stable Matchings pdf notes Stable Matching Example
Section 1.1 of KT
Lecture 3 (04/03/20) Stable Matchings pdf notes Section 1.2 of KT
Lecture 4 (04/06/20) Asymptotics pdf notes In class exercise
Chapter 2 of KT
Lecture 5 (04/08/20) Graphs, Trees pdf notes In Class Exercise
Section 3.1 of KT
Lecture 6 (04/10/20) BFS pdf 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 pdf notes Section 3.2 of KT
Lecture 9 (04/17/20) Topological Sorting pdf notes Section 3.6 of KT
Lecture 10 (04/20/20) Greedy: Interval Scheduling/Partitioning pdf notes Section 4.1,4.5 of KT
Lecture 11 (04/22/20) Minimum Spanning Tree pdf Notes Section 4.4 of KT
Lecture 12 (04/24/20) Union Find DS, Dijkstra's Alg pdf Notes Supplement Notes on Union Find
Section 4.6 of KT
Lecture 13 (04/27/20) Dijkstra's Alg pdf Notes Supplement Notes on Dikjstra,
Section 4.4 of KT
Lecture 14 (04/29/20) Divide and Conq: Closest Pair pdf Notes Section 5.1,5.2 of KT
Lecture 15 (05/01/20) Divide and Conq: Integer Multiplication pdf Section 5.4,5.5 of KT
(05/04/20) Midterm
Lecture 16 (05/06/20) Approximation Algorithms pdf Notes Notes on Set Cover
Lecture 17 (05/08/20) Algorithm Design By Induction pdf Notes Sections 5.1,5.2,5.4,5.8 of Manber's book
Lecture 18 (05/11/20) DP: Interval Scheduling pdf Notes Section 6.1 of KT
Lecture 19 (05/13/20) DP: Knapsack, pdf Notes Section 6.2, 6.4 of KT
Lecture 20 (05/15/20) RNA Secondary Structure, Seq Alignment pdf Notes Section 6.5 of KT
Lecture 21 (05/18/20) DP: Longest Path in DAG, LIS, Shortest Path pdf Section 6.6 of KT
Lecture 22 (05/20/20) Network Flow pdf Section 7.1 of KT
Lecture 23 (05/22/20) Max Flow-Min Cut, Maximum matching pdf Section 7.2 of KT
(05/25/20) No Class: Memorial Day
Lecture 24 (05/27/20) Matchings pdf Notes Section 7.6 of KT
Lecture 25 (05/29/20) Hall's Conidtion, Edge Disjoint Pathsl pdf Notes Section 7.6 of KT
Lecture 26 (05/01/20) Image Segmentation, Polynomial Time Reductions pdf Notes Section 7.9, 8.1 of KT
Lecture 27 (06/03/20) Polynomial-time Reductions pdf Notes Section 7.10,7.11,8.3 of KT
Lecture 28 (06/05/20) NP-completeness pdf
(06/08/20) Final Exam

Homeworks [Grading guidelines]:

Homework submission is due via Canvas

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.