What you'll learn
The final module is about judgment. When a problem is NP-hard, you don't give up — you approximate or use heuristics. And for any problem, you need a way to choose the right approach. We close with a decision framework and a master cheat sheet of everything you've learned.
By the end you'll be able to:
- Use approximation algorithms with provable ratios
- Apply heuristics and local search
- Follow a framework to choose an algorithm for any problem
Approximation algorithms
An approximation algorithm runs in polynomial time and returns a solution provably close to optimal. Its approximation ratio bounds how far off it can be — a 2-approximation is never worse than twice optimal. The classic: cover every edge by greedily taking both endpoints of any uncovered edge — at most twice the minimum vertex cover:
def vertex_cover_2approx(edges):
cover = set()
for u, v in edges:
if u not in cover and v not in cover:
cover.add(u); cover.add(v) # take BOTH endpoints
return cover
# guaranteed at most 2x the optimal cover sizeNote
Heuristics & local search
A heuristic has no guarantee but works well in practice. Local search starts with a solution and repeatedly makes small improving changes until stuck at a local optimum. To escape local optima, simulated annealing sometimes accepts worse moves (less often over time), and genetic algorithms evolve a population of solutions. These power real-world scheduling, routing, and layout where optimal is out of reach.
Tip
k, not in n.A decision framework
Faced with any algorithmic problem, work through four steps:
Understand
Nail the inputs, outputs, constraints, and input size n.
Match a paradigm
Brute force, greedy, divide & conquer, DP, or a graph model?
Analyze
Work out the Big-O. Is it fast enough for the given n?
If intractable
Approximate, use heuristics, or restrict the input.
The input size is your compass: n ≤ 20 invites exponential methods (bitmask, backtracking); n ≤ 10⁴ tolerates O(n²); n ≤ 10⁶ wants O(n log n) or better; huge n demands near-linear or streaming algorithms.
The master cheat sheet
Every headline algorithm from the course, at a glance:
| Problem | Best-known time | Technique |
|---|---|---|
Sort (comparison) | O(n log n) | Merge / heap / quick |
Sort (integer) | O(n + k) | Counting / radix |
Search (sorted) | O(log n) | Binary search |
k-th smallest | O(n) expected | Quickselect |
Shortest path (≥0) | O((V+E) log V) | Dijkstra |
Shortest path (any) | O(V·E) | Bellman-Ford |
All-pairs paths | O(V³) | Floyd-Warshall (DP) |
Minimum spanning tree | O(E log V) | Kruskal / Prim (greedy) |
Max flow | O(V·E²) | Edmonds-Karp |
Bipartite matching | O(E√V) | Hopcroft-Karp / flow |
0/1 knapsack | O(n·W) | Dynamic programming |
Edit distance / LCS | O(n·m) | Dynamic programming |
String search | O(n + m) | KMP / Z / Rabin-Karp |
Primes ≤ n | O(n log log n) | Sieve of Eratosthenes |
Convex hull | O(n log n) | Monotone chain |
NP-hard (e.g. TSP) | Exponential / approx. | B&B, DP, approximation |
Where to go next
You now hold the core algorithmic toolkit: analysis, the great paradigms, graph algorithms, and the theory of hardness. From here, deepen with advanced data structures (segment trees, Fenwick trees, link-cut trees — see our Data Structures course), competitive programming practice, or specialized fields like computational geometry, flows & matchings, and approximation theory. But the real skill isn't memorizing algorithms — it's recognizing which paradigm a new problem wants. That instinct is what this course was built to grow.
Recap & quick check
Key takeaways
- Approximation algorithms run in polynomial time with a provable ratio (e.g. 2× optimal).
- Heuristics and local search (annealing, genetic) trade guarantees for practical quality.
- For NP-hard problems on small inputs, exact methods (B&B, bitmask DP, FPT) still work.
- Choose an algorithm by input size: n≤20 exponential, ≤10⁴ quadratic, ≤10⁶ near-linear.
- Master skill: recognize which paradigm a new problem calls for.
Quick check
1. What does a 2-approximation algorithm guarantee?
2. Why does simulated annealing sometimes accept worse moves?
3. For n ≤ 20, which approach becomes viable?
4. What's the single most valuable algorithmic skill?
That's the whole journey — from what an algorithm is to the frontier of what computers can do efficiently. Congratulations on completing The Complete Algorithms Course. Now go build something fast. 🚀