CSE 421: Introduction to Algorithms

Winter, 2022

Yin Tat Lee

MWF 1:30-2:20, CSE2 G20
Office hours 2:30-3:30pm in (Zoom: Same link as the lecture.)
The class will be on zoom in the first 2 weeks.
Zoom link: https://washington.zoom.us/j/94725527396

Links:
Grading Scheme:
  • Homework (50%)
  • Midterm (20%)
  • Final (30%)
Turning machine


Tentative Schedule
Lecture Topic Slides References
Part I: Graphs
Lec. 1 (01/03/22) Stable Matchings pptx/pdf, demo, proof Sec 1, reading, video 1,2
Lec. 2 (01/05/22) Graphs pptx/pdf, proof Sec 2, 3.1, video
Lec. 3 (01/07/22) Breadth First Search pptx/pdf, proof Sec 3.2-3.4, App 1,2, video
Lec. 4 (01/10/22) Depth-first search pptx/pdf, proof Sec 3.6, App 1, 2, video
Part II: Greedy Methods
Lec. 5 (01/12/22) Interval Scheduling pptx/pdf, proof Sec 4.1, video
Lec. 6 (01/14/22) Minimizing Lateness, Optimal Caching pptx/pdf, proof Sec 4.2-4.3, Practice, video
Holiday (01/17/22) Martin Luther King Day
Lec. 7 (01/19/22) Dijkstra Algorithm
Lec. 8 (01/21/22) Minimum Spinning Tree (by Jeremy Lin)
Lec. 9 (01/24/22) Huffman Codes
Part III: Divide and Conquer
Lec. 10 (01/26/22) Closest Points
Lec. 11 (01/28/22) Median and Multiplication
Lec. 12 (01/31/22) Fast Fourier Transform
Lec. 13 (02/02/22) Midterm review
Special (02/04/22) Midterm
Part IV: Dynamic Programming
Lec. 14 (02/07/22) Weighted Interval Scheduling, Knapsack
Lec. 15 (02/09/22) RNA, Sequence Alignment
Lec. 16 (02/11/22) Shortest Paths with Negative weights
Lec. 17 (02/14/22) More Dynamic Programming
Part V: Network Flow
Lec. 18 (02/16/22) Maxflow (by Sally Dong)
Lec. 19 (02/18/22) Ford-Fulkerson
Holiday (02/22/22) Presidents' Day
Lec. 20 (02/23/22) Edmonds-Karp Algorithm
Lec. 21 (02/25/22) Linear program
Lec. 22 (02/28/22) Simplex Method
Lec. 23 (03/02/22) Ellipsoid Method
Part VI: NP completeness
Lec. 24 (03/04/22) NP completeness
Lec. 25 (03/07/22) Reductions
Lec. 26 (03/09/22) Approximation Algorithms
Lec. 27 (03/11/22) Final review
Special (03/14/22) Final

Homeworks:

  • Homework 1 due Wednesday, 12-Jan at 1:30PM.
  • Homework 2 due Wednesday, 19-Jan at 1:30PM.
  • Homework 3 due Wednesday, 26-Jan at 1:30PM.
  • Homework 4 due Wednesday, 2-Feb at 1:30PM.
  • Homework 5 due Wednesday, 16-Feb at 1:30PM.
  • Homework 6 due Wednesday, 23-Feb at 1:30PM.
  • Homework 7 due Wednesday, 2-Mar at 1:30PM.
  • Homework 8 due Wednesday, 9-Mar at 1:30PM.
Sick Policy:
  • If you feel sick or suspect COVID, do not come to class. There are recordings and slides for all lectures. Virtual mid-term and final can be arranged for medical reasons. Email yintat@uw for such an arrangement before the exam starts.
Late Policy:
  • Homework is due at the start of class on the due date. 20% off after the due time. 40% off 1 day after the due time. 100% off 2 days after the due time. The deduction is counted question-wise. Please hand in whatever you finish first.
  • There is extra credit for you to earn some extra marks. Therefore, no extension except for an emergency reason.
Regrade Policy:
  • Put a regrade comment on homework in gradescope within 5 days after the grade is posted.
UW Policy:

Office hours:

TA Office hours Room
If the lectures are virtual, the OH will be virtual.
Andreea Ghizila
andreeag@uw
Mon 11:30-12:30pm 4th Floor breakout / Zoom
Sally Dong
sallyqd@uw
Tue 11am-12noon 4th Floor breakout / Zoom
Jason Waataja
jwaataja@uw
Tue 3-4pm 4th Floor breakout / Zoom
Jeremy Lin
linjer23@uw
Tue 2-3pm 4th Floor breakout / Zoom
Ashwin Banwari
ash1152@uw
Fri 2:30-3:30pm 5th Floor breakout / Zoom
Swati Padmanabhan
pswati@uw
Fri 3:30-4:30pm 5th Floor breakout / Zoom

Midterm exam:

Please try to solve the problems before looking at the solutions.

Final exam:

Please try to solve the problems before looking at the solutions.


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-2022, Paul G. Allen School of Computer Science and Engineering, University of Washington.