Greedy

Vertex Cover is NP-hard: there is no known polynomial algorithm that finds a minimum cover. But a five-line greedy algorithm guarantees a cover whose size is at most twice the minimum, and the proof fits on a napkin. That guarantee, the approximation ratio, is the difference between a heuristic that might be terrible and an algorithm with a written contract about how far from optimal its answer can be. **Approximation Algorithms** introduces that contract-based view of NP-hard optimization. You will define approximation ratio formally and walk through the classic constant-factor algorithms: a 2-approximation for Vertex Cover via greedy maximal matching, an `O(log n)`-approximation for Set Cover via greedy element-counting, and a 2-approximation for Metric TSP that exploits the triangle inequality on top of an MST. The lesson then covers approximation schemes (PTAS, polynomial in `n` for any fixed `epsilon`; FPTAS, polynomial in both), with Knapsack FPTAS as the canonical example. Throughout, the lesson contrasts approximation algorithms with heuristics, where heuristics give no guarantee at all. In **Greedy (Intro)**, you saw simple greedy strategies and their correctness proofs. **Dynamic Programming (Advanced)** introduced 0/1 Knapsack as an NP-hard exact algorithm. This lesson asks the next question: when exact is too slow, how close to optimal can we provably get? Next, **Advanced Bit Manipulation** turns to bit-level tricks for `O(1)` and bitmask-DP solutions.

0/1 Knapsack is exponentially many subsets to consider, but commercial solvers like CPLEX and Gurobi answer instances with thousands of items in seconds. The trick is not better hardware but smarter exploration: at every node of the search tree, compute a cheap upper bound on what any completion of the partial solution could possibly achieve, and prune the entire subtree if that bound cannot beat the best solution found so far. That single discipline of provably-suboptimal pruning is what defines branch and bound. **Branch and Bound** introduces the framework as a refinement of backtracking. You will design bounding functions (typically a relaxation, like fractional knapsack as a bound for 0/1 knapsack), build state-space trees, and choose between three exploration strategies: FIFO (BFS-like), LIFO (DFS-like), and least-cost (priority queue). Classic applications include 0/1 Knapsack with the fractional-relaxation bound, the Traveling Salesman Problem, and the job-assignment problem. The lesson also draws the line between B&B and DP so you know when each is the right approach. In **Backtracking (Intro)**, you walked an implicit decision tree with choose, explore, unchoose. **Greedy (Intro)** taught you that locally optimal choices sometimes give global optima. Branch and bound borrows the search structure of one and the bounding intuition of the other. Next, **Divide and Conquer (Advanced)** turns to algebraic D&C tricks like Karatsuba and Strassen.

"For each element in the array, find the next greater element" is a brute-force `O(n^2)` problem until you notice that a stack maintained in decreasing order lets you answer every query as a side effect of a single left-to-right scan. The whole algorithm runs in `O(n)`, and the same monotonic-stack pattern solves trapping rain water, largest rectangle in a histogram, stock spans, and a long tail of related problems with the same template. **Advanced Greedy & Data Structures** is where greedy thinking meets specialized scaffolding. You will implement the monotonic stack pattern for next-greater and next-smaller variants, the monotonic deque for sliding-window maximum and minimum (also a key DP optimization), and sweep-line algorithms for interval and event problems (meeting rooms, interval merge, rectangle area union). The lesson closes with advanced greedy problems that need a heap or priority queue: full Huffman encoding, task scheduling with cooldown, the gas station problem, and activity selection with deadlines and profits. In **Greedy (Intro)**, you saw simple greedy strategies that needed only sorting. **Heaps & Priority Queue** taught you `O(log n)` access to the minimum or maximum, which is exactly what these advanced greedy patterns rely on for their efficiency. Next, **Branch and Bound** extends backtracking with the same kind of bounding-function pruning, applied to optimization search trees.

Given coin denominations of 1, 5, and 25, the greedy "take the largest coin that fits" strategy gives change optimally. Add a coin worth 10 to the system and greedy stays optimal. Replace 25 with 21 and greedy quietly breaks: making 63 cents now wants three 21s, but greedy says one 21 plus two 1s and ten more 1s. The same algorithm, the same input shape, and yet correctness depends entirely on a structural property of the problem. **Greedy (Intro)** explains exactly which property that is. You will learn to test for the greedy-choice property and optimal substructure, the twin ingredients that justify a greedy decision. The lesson covers the canonical problems where greedy provably works (activity selection by earliest end time, fractional knapsack by value-to-weight ratio, job scheduling with deadlines, the jump game, Huffman encoding) and walks through the exchange-argument style of correctness proof. It also shows where greedy fails (0/1 knapsack, coin change with arbitrary denominations) so you know when to reach for DP instead. In **Sorting (Elementary)**, you saw why sorting often costs `O(n log n)`; almost every greedy algorithm starts with a sort step. **Big-O Notation (Upper Bound)** gave you the language to express that cost. Next, **Dynamic Programming (Intro)** picks up where greedy fails, when the local optimum does not guarantee the global one.