CSE 421: Introduction to Algorithms

Spring, 2021

Shayan Oveis Gharan

MWF 1:30-2:20, Zoom Meeting ID: 97771906541
Office hours Zoom Meeting ID: 94137597308
M/W 2:30-3:20
Also, Tue 4:30-5:20 we have problem solving session at 99626064244

Email list:
Class email list: cse421a_sp21     [archives]

Please send any e-mail questions about the course to cse421-staff@cs.washington.edu.

Plesae use ed 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%
Extra Credit Problems Can increase final GPA by 0.1
Quizzes Can Increase final GPA by 0.1

Lecture Slides
Lecture Topic Slides/Notes Inclass Exercise Reading Assignment
Lecture 1 (03/29/21) Stable Matchings pdf, Notes Section 1.1 of KT
Lecture 2 (03/31/21) Stable Matchings pdf, Notes Section 1.2 of KT
Lecture 3 (04/02/21) Stable Matchings/Induction pdf, Notes
Lecture 4 (04/05/21) Asymptotics pdfNotes in-class exercise
Chapter 2 of KT
Lecture 5 (04/07/21) Graphs, Trees pdf, Notes
Section 3.1 of KT
Lecture 6 (04/09/21) BFS pdf, Notes
Section 3.2 of KT
Induction on Graphs
Lecture 7 (04/12/21) Connected Comps pdf, Notes Inclass Exercise
Section 3.3,3.4 of KT,
sample alg+proof
Lecture 8 (04/14/21) Bipartiteness pdf,Notes Inclass Exercise Section 3.2 of KT
Lecture 9 (04/16/21) DFS, Topological Sorting pdf,Notes, Latex Notes Section 3.6 of KT
Lecture 10 (04/19/21) Greedy: Interval Scheduling/Partitioning pdf, Notes, Latex Notes Section 4.1,4.5 of KT
Lecture 11 (04/21/21) Minimum Spanning Tree pdf, Notes Latex Notes Section 4.4 of KT
Lecture 12 (04/23/21) Union Find DS pdf,Notes Supplementary Notes
Sections 4.6, 5.1 of KT
Lecture 13 (04/26/21) Divide and Conq: Closest Pair pdf,Notes Sections 5.1,5.2 of KT
Lecture 14 (04/28/21) Divide and Conq: Integer Multiplication pdf,Notes Sections 5.4,5.5 of KT
Lecture 15 (04/30/21) Divide and Conq: Midpoint pdf,Notess Section 4.4 of KT
(05/03/21) Midterm (1:30-2:35 and 10:00-11:05 PST)
Lecture 16 (05/05/21) Approximation Algorithms pdf, Notes Vertex Cover Supplement,
Set Cover Supplemeent
Lecture 17 (05/07/21) Dijkstra's Algorithm, Algorithm Design By Induction pdf,Notes Supplement Notes for Dijkstra Sections 5.1,5.2,5.4,5.8 of Manber's book
Lecture 18 (05/10/21) DP: Interval Scheduling pdf, Notes Section 6.1 of KT
Lecture 19 (05/12/21) DP: Knapsack, pdf Section 6.2, 6.4 of KT
Lecture 20 (05/14/21) RNA Secondary Structure, Seq Alignment pdf, Notes Section 6.5 of KT
Lecture 21 (05/17/21) DP: Longest Path in DAG, LIS, Shortest Path pdf, Notes Latex Notes Section 6.6 of KT
Lecture 22 (05/19/21) Network Flow pdf,Notes Section 7.1 of KT
Lecture 23 (05/21/21) Max Flow-Min Cut, Maximum matching pdf,Notes Section 7.2 of KT
Lecture 24 (05/24/21) Edge Disjoint paths, Matchings pdf, Notes Section 7.6 of KT
Lecture 25 (05/26/21) Hall's Conidtion, Image Segmentation pdf, Notes Section 7.6 of KT
Lecture 26 (05/28/21) Polynomial Time Reductions pdf, Notes Section 7.9, 8.1 of KT
(05/31/21) No Class: Memorial Day
Lecture 27 (06/02/21) NP-Completeness pdf Section 7.10,7.11,8.3 of KT
Lecture 28 (06/04/21) Bellman Ford Algorithm, Extra Materials pdf
(06/07/21) Final Exam (2:30-5:30 and 10:00-1:00 PST)

Homeworks [Grading guidelines]:

Homework submission is due via Gradescope

TA Office hours Meeting Id
Savanna J Yee Mon 10:00 AM-10:50 AM 97332958862
Mickey Moonkaen Mon 4:00 PM-4:50 PM 94908850680
Todor Dimitrov Tue 9:00 AM-9:50 AM 7606986951
Albert Liang Zhong Tues 12:30 PM-1:20 PM 95015984293
Aidan Arieh Gottlieb Tue 2:30 PM-3:20 PM 2075377702
Yunkyu Song Tue 5:30 PM-6:20 PM 91882309072
Chase Lee Wed 8:00 AM-8:50 AM 97185046505
Liangyu Zhao Wed 4:00 PM-4:50 PM 3215688552
Mrigank Arora Thu 9:00 AM-9:50 AM 98031098493
Johnson Kuang Thu 11:00 AM-11:50 AM 7935407872

Notes for problem solving session on 04/27/21

Exams:

  • Midterm exam:
    At 1:30-2:35 (PM) and 10:00-11:05 (PM) Monday 03-May-2021 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 with sample solutions is available. Here is Midterm exam of 2020. No solutions will be posted for this midterm. Please try to solve the problems. I will upload the solutions by Friday. There will be a review session on Saturday, 01-May-2021 at 10:00 am, Zoom Meeting ID: 5948822807. Please bring your questions. Here are notes for midterm review session Here are recorded video, Slides for the review session.
  • Final exam:
    At 2:30-5:30 (PM) and 10:00 (PM)-1:00 (AM) on Monday 7-Jun-2021. Similar to midterm, it will be open book and open notes, hard copies only.
    There is a 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. More Practice Problems There will be a review session on Saturday, 05-Jun-2021 at 10:00 am. in Zoom Meeting ID: 5948822807. Please bring your questions. 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.