Stable Matching, Proofs/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
Midterm
(Mon, Nov 4)
6:00-7:30 pm
Midterm (Evening, CSE2 G20)
Applications of MaxFlow/MinCut I
Applications of MaxFlow/MinCut II
No Lecture: Veteran's Day Observed
Algorithmic Toolbox
Linear Programming
Linear Programming Duality
NP-completeness I: Reductions
Linear Programming Algorithms
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 2024.