Stable Matching, Induction review
Stable Matching, Overview
Overview, Graph Traversal (BFS)
Graph Traversal (DFS & Applications)
Topological Sort
Graph Search, Asymptotics
More Greedy Algorithms
Dijkstra's Algorithm
Minimum Spanning Trees:
Prim's and Kruskal's Algorithms and beyond
Problem Solving Strategy
Greedy Algorithms
Multiplication: Matrix, Integer, Polynomial
Strassen, Karatsuba, FFT
Median, Quicksort
Beyond the Master Theorem
Problem Solving Strategy
Divide and Conquer
Dynamic Programming
Longest Increasing Subsequence, Knapsack
Dynamic Programming
RNA Secondary Structure, Edit Distance (Sequence Alignment)
Problem Solving Strategy
Dynamic Programming
Dynamic Programming
Bellman-Ford algorithm, Applications
MaxFlow/MinCut
Ford-Fulkerson Algorithm
Network Flow in Polynomial Time
Applications of MaxFlow/MinCut I
Midterm
(Wed, Nov 8)
6:00-7:30 pm
Midterm (Evening, CSE2 G20)
No Lecture: Veteran's Day Observed
Applications of MaxFlow/MinCut II
Algorithmic Toolbox
Linear Programming
Linear Programming Duality
Linear Programming Algorithms
NP-completeness I: Reductions
No Section: Thanksgiving Holiday
No Lecture: Thanksgiving Holiday
Dealing with NP-completeness
Parametrized complexity
SAT Solvers
The final exam is scheduled at 2:30-4:20 pm in our regular classroom (CSE2 G20) at the time specified in the UW Final Exam Schedule for Autumn 2023.