Skip to main content
Work in Progress
•
The site is new and most content is under development.
Advanced Algorithms
Latest Edition
Search
K
Cancel
←
All Courses
Advanced Algorithms
Latest Edition
←
Back to All Courses
Course Content
Notes
Assessments
Editions
Greedy Algorithms
A Generic Problem
Definition and Examples
Greedy Works!
When Greedy Fails
Scheduling with Deadlines
Reductions I: Flows
Introduction
Ford-Fulkerson
Maxflow-Mincut
Flow Decomposition
Tuple Selection
Exam Scheduling
IPL Elimination
Reductions II: Hardness
P, NP, NP-hardness
Max Independent Set
Graph Coloring
3D Matching
Subset Sum
Finding the Right Problem
Interlude: Complexity
co-NP
PSPACE
PSPACE reductions - I
PSPACE reductions - II
PSPACE reductions - III
Randomized Algorithms
Probability Basics
Randomized QS - I
Randomized QS - II
Karger's MinCut Algorithm
Minimum Spanning Tree
Approximation Algorithms
Greedy Set Cover
Bin Packing
Vertex Cover via Matchings
Vertex Cover with LP - I
Primal-Dual
Vertex Cover with LP - II
Parameterized Algorithms
Introduction
Iterative Compression - I
Iterative Compression - II
Pathwidth
MIS on thin grids
Treewidth
DP for MIS
Nice Tree Decompositions
Exact Algorithms
Branch and Bound
PIE for chromatic number - I
PIE for chromatic number - II
Dynamic Programming - I
Dynamic Programming - II
Parameterized Approximation
Partial Vertex Cover
k-Path Transversal - I
k-Path Transversal - II
Min k-Cut - I
Min k-Cut - II
Min k-Cut - III
Randomized FPT Techniques
Color Coding - I
Color Coding - II
Chromatic Coding - I
Chromatic Coding - II
Derandomization
Randomized Approximation
Facility Location - I
Facility Location - II
Multiway Cut - I
Multiway Cut - II
Set Cover
Hardness
Hardness of Approximation
PCP Theorem - I
PCP Theorem - II
Unique Games Conjecture
para-NP Hardness
W-Hardness
co-NP
PSPACE reductions - I