MWF 1:30-2:20PM, in: CSE2 G20

Office hours Allen Center 636

M 12:30-1:20, W 2:30-3:20 and F 12:30-1:20

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

Plesae use ed for course related questions.

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 | Topic | Slides/Notes | Inclass Exercise | Reading Assignment |
---|---|---|---|---|

Lecture 1 (03/25/24) | Stable Matchings | Section 1.1 of KT | ||

Lecture 2 (03/27/24) | Stable Matchings/Induction | Section 1.2 of KT | ||

Section 1 (03/28/24) | Stable Matching, Induction | pdf, Solution | ||

Lecture 3 (03/29/24) | Stable Matching, Asymptotics | pdf, annotated | ||

Lecture 4 (04/01/22) | Graphs, Induction | inclass-exercise | Chapter 2 of KT | |

Lecture 5 (04/03/24) | Trees | pdfannotated | Section 3.1 of KT BFS | |

Section 2 (04/04/24) | BFS | pdfpdf | ||

Lecture 6 (04/05/24) | Connected Components,Bipartiteness | Section 3.2,3.3,3.4 of KT BFS + Conn Comp Code | ||

Lecture 7 (04/08/24) | DFS, Topological sorting | Section 3.2 | ||

Lecture 8 (04/10/24) | Topological Sorting, Interval scheduling | Section 3.6, 4.1 of KT | ||

Section 3 (04/11/24) | DFS,Directed Graphs,Induction | pdf, solution | Section 3.6 of KT | |

Lecture 9 (04/12/24) | Interval Schedule/Partitioning | Section 4.1,4.5 of KT | ||

Lecture 10 (04/15/24) | Greedy: Minimum Spanning Tree | Section 4.4 of KT | ||

Lecture 11 (04/17/24) | Union-Find Data Structure | Section 4.4 of KT Supplement notes for Union Find/Kruskal's alg | ||

Section 4 (04/18/24) | Greedy/Kruskal | pdf, solutions | ||

Lecture 12 (04/19/24) | Divid and Conq | Sections 4.6, 5.1 of KT | ||

Lecture 13 (04/22/24) | Divide and Conq: Closest Pair | Sections 5.1,5.2 of KT | ||

Lecture 14 (04/24/24) | Integer Multiplication, Midpoint | Sections 5.4,5.5 of KT | ||

Section 5 (04/25/24) | Midterm Review | slides | ||

Lecture 15 (04/26/24) | Approx Algorithms | Section 4.4 of KT | ||

(04/29/24) Midterm (10:30-11:20) | ||||

Lecture 16 (05/01/24) | Approximation Algorithms, Dynamic Programming | |||

Section 6 (05/02/24) | Approximation Algorithms/DP | pdf, solution | ||

Lecture 17 (05/03/24) | DP: Interval Scheduling | Section 6.1 of KT Sections 5.1,5.2,5.4,5.8 of Manber's book | ||

Lecture 18 (05/06/24) | RNA Secondary structure | Sample Proof of Interval Scheduling Section 6.2 of KT | ||

Lecture 19 (05/08/24) | Longest path in DAG, LIS, Shortest Path | Section 6.2, 6.4 of KT | ||

Section 7 (05/09/24) | DP | pdf, solutions | ||

Lecture 20 (05/10/24) | Shortest Path, Network Flow | Section 6.5, 6.6 of KT | ||

Lecture 21 (05/13/24) | Network Flow | Section 7.1 of KT | ||

Lecture 22 (05/15/24) | Max Flow-Min Cut | Section 7.2 of KT | ||

Section 8 (05/16/24) | Network Flow | pdf, solution | ||

Lecture 23 (05/18/24) | Maximum matching, Hall's Condition | Section 7.2 of KT | ||

Lecture 24 (05/20/24) | Edge Disjoint Paths, Image Segmentation | Section 7.6 of KT | ||

Lecture 25 (05/22/24) | Linear Programs Intro | supplement-note-vertex-cover | ||

Section 9 (05/23/24) | LP | pdf, solutions | ||

Lecture 26 (05/24/24) | LP Duality | |||

(05/27/24) No Class: Memorial Day | ||||

Lecture 27 (05/29/24) | Polynomial Time Reductions | Section 7.9, 8.1 of KT | ||

Section 10 (05/30/24) | Reductions/Final Review | |||

Lecture 28 (05/31/24) | NP-Completeness | Section 7.10,7.11,8.3 of KT | ||

(06/03/24) Final Exam (2:30-4:20 CSEII G20) |

**Homeworks**
[Grading guidelines]:

Homework submission is due via Gradescope

- Homework 1 due Wednesday, 3-April at 11:59PM.
- Homework 2 due Wednesday, 10-April at 11:59PM.
- Homework 3 due Wednesday, 17-April at 11:59PM.
- Homework 4 due Wednesday, 24-April at 11:59PM.
- Homework 5 due Wednesday, 08-May at 11:59PM.
- Homework 6 due Wednesday, 15-May at 11:59PM.
- Homework 7 due Wednesday, 22-May at 11:59PM.
- Homework 8 due
**Thursday**, 30-May at 11:59PM.

TA |
Office hours |
Location |

Xiyang Liu | Fri 9:00-10:00 AM | Gates 150 |

Marian Dietz | Fri 11:30-12:20 PM | Gates 150 |

Raymond Patrick Guo | Fri 2:30-3:30 | Gates 150 |

Robert Stevens | Tue 11:30-12:20 | Gates 150 |

Airei Fukuzawa | Tue 12:30-1:20 PM | Gates (CSE II) 150 |

Aman Thukral | Tue 2:30-3:30 | Gates (CSE II) 121 |

Tom Tian | Tue 3:30-4:30 | Gates (CSE II) 152 |

Dorna Abdolazimi | Fri 3:30-4:20 | Gates 150 |

Sophie Lin Robertson | Wed 10:30-11:30 | Gates 150 |

Sela Navot | Wed 11:30-12:30 | Gates 131 |

Albert Weng | Wed 3:30-4:30 | Gates 150 |

**Exams:**

**Midterm exam**:

At 1:30-2:20 Gates G20 Monday 29-April-2024 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 midterm with sample solutions. Here is the Midterm exam of Spring 2021. Please try to solve the problems. I will upload the solutions by Friday. We will review solutions in sections this Thursday April 25th.**Final exam**:

At 2:30-4:20 Gates G20 Monday 3-Jun-2024. 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. Here is Final of 2018. No solution will be given for this one.**Please practice this final in a timed interval**Final Review Slides

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.