Maryam Aliakbarpour

Description

This page contains course materials for topics in greedy algorithms, maximum flow, and NP-completeness. The course emphasizes rigorous reasoning about algorithm design, correctness, and efficiency.
This page includes materials prepared and presented by Maryam Aliakbarpour for the second portions of the course covering greedy algorithms, maximum flow, and NP-completeness.

Schedule

Date	Material
Greedy Algorithms Lab 5 Lab 5 solution HW 4A
10/16/2025	Introduction to Greedy Algorithms, Car Refueling, and Scheduling
10/21/2025	Huffman Coding and Caching
Minimum Spanning Trees Lab 6 Lab 6 solution HW 4B
10/23/2025	Prim, Kruskal, Union-Find
10/28/2025	Advanced Union-Find, Boruvka’s Algorithm, Single-Link Clustering
Maximum Flow Lab 7 Lab 7 solution HW 5
10/30/2025	Max Flow, Min Cut, Ford-Fulkerson
11/04/2025	Max-Flow Min-Cut Theorem, Weak Duality, Running Time of FF
11/06/2025	Applications: Flow Decomposition, Bipartite Matching, Edge-Disjoint Paths, Vertex-Disjoint Paths
11/11/2025	Application: Baseball Elimination; Linear Programming
11/13/2025	Max-Flow Min-Cut Theorem with LP Duality
NP-Completeness and Approximation Lab 8 Lab 8 solution HW 6
11/18/2025	P vs NP, NP-Completeness, Cook–Levin Theorem
11/20/2025	Reductions: 3-SAT, MIS, Max-Clique, Vertex-Cover
11/25/2025	Reductions: Hamiltonian-Cycle, TSP; Approximation Algorithms: Vertex Cover
12/02/2025	(In)Approximability of TSP, Metric TSP, Set Cover and its Approximation Algorithm
12/04/2025	Review