Module 5 · Algorithmic Paradigms
Modules 1 to 4 taught you data structures and the algorithms that live on them: two pointers on arrays, binary search on sorted data, heaps, trees, BFS and Dijkstra on graphs. Module 5 changes the question. Instead of "what can I do with a heap?", it asks "how do I invent an algorithm for a problem I have never seen?"
The answer is a small set of paradigms. A paradigm is a general strategy for designing algorithms. It is not tied to one data structure. It is a way of attacking a problem: try everything but give up early, split the problem in half, always take the locally best option, flip a coin. Most algorithms you already know are instances of one of them. Merge sort is divide and conquer. Dijkstra and Kruskal are greedy. Quicksort with a random pivot is randomized. DFS over a puzzle's states is backtracking. Module 5 makes those strategies explicit, so that you can apply them on purpose.
The module is in the DSA: Zero to Mastery course. Previous module: Module 4 · Graphs. Next: Module 6 · Dynamic Programming.
What this module covers
Five lessons and a capstone.
1. Recursion & Backtracking. Backtracking builds a solution one choice at a time and abandons ("backtracks from") a partial solution the moment it cannot be completed. You will generate permutations, combinations and subsets, solve N-Queens and Sudoku, and learn the pruning rules that turn an astronomically large search into one that finishes in milliseconds: check constraints early, try the most constrained variable first, order values well.
2. Divide & Conquer. Split the problem into smaller independent pieces of the same kind, solve each recursively, and combine the answers. You will count inversions with merge sort, find the closest pair of points in with the famous "only 7 neighbours" argument, multiply big numbers faster than the schoolbook method with Karatsuba, see why Strassen's matrix multiplication beats and why libraries rarely use it, and solve recurrences with the Master theorem.
3. Greedy Algorithms. Make the choice that looks best right now and never reconsider it. Greedy algorithms are the fastest and simplest of all, and the easiest to get wrong. You will learn the three standard ways to prove one correct (the exchange argument, "greedy stays ahead", and the cut property), apply them to interval scheduling, Huffman coding and minimum spanning trees, and see the counterexamples where greedy fails — the doorway to dynamic programming.
4. Bit Manipulation. Work directly on the binary representation of integers. A 64-bit word is a set of up to 64 small items that you can union, intersect and test in one machine instruction. You will use bitmasks to represent subsets, attacked columns and Sudoku candidates; that is what makes the capstone's solvers fast, and it is the state representation behind Bitmask DP in Module 6.
5. Randomized Algorithms. Let the algorithm flip coins. A random pivot makes quicksort's bad cases unlikely for every input instead of rare over random inputs. Random hashing defeats adversaries. Random sampling estimates what is too expensive to count. You will meet Las Vegas algorithms (always correct, random running time) and Monte Carlo algorithms (bounded time, small chance of a wrong answer), randomized quickselect, reservoir sampling, Miller–Rabin and random restarts.
Capstone. Build a Sudoku and N-Queens Solver Engine. One generic backtracking engine, three Sudoku solvers (naive, bitmask candidates, and "most constrained cell first"), a benchmark that shows a thousand-fold difference between them, a greedy-versus-DP study of coin systems where the greedy cashier fails, and randomized restarts that tame N-Queens' heavy-tailed running times. It uses every lesson in the module.
How the paradigms relate
All five paradigms are refinements of the same starting point: brute force, which lists every candidate answer and checks each one. Brute force is always correct and almost always too slow. Each paradigm is a different way to avoid looking at most of the candidates.
flowchart TD
BF["Brute force: list every candidate, check each"] --> BT["Backtracking: build candidates step by step, prune dead branches early"]
BT --> DC["Divide and conquer: split into independent subproblems, combine"]
BT --> GR["Greedy: follow one branch only, proved safe"]
BT --> DP["Dynamic programming: subproblems repeat, so solve each once"]
DC --> DP
GR -->|"greedy fails? fall back to"| DP
BM["Bit manipulation: compact state for all of them"] -.-> BT
BM -.-> DP
RA["Randomization: random choices beat worst cases"] -.-> DC
RA -.-> BT
Read it top to bottom:
- Brute force → backtracking. Instead of generating complete candidates and then checking them, build each candidate one decision at a time and check constraints as you go. A partial Sudoku with two 5s in a row is already dead, so all of its completions are skipped. The search space is a tree of decisions; backtracking walks it depth-first and cuts dead branches.
- Backtracking → divide and conquer. Sometimes the decisions split the problem into pieces that do not interact. Sorting the left half of an array tells you nothing about the right half. Then you do not need to search at all: solve each piece once and combine. The recursion tree is still there, but every node is visited exactly once and every node is useful.
- Backtracking → greedy. Sometimes you can prove that one particular choice at each step is always safe, so the search tree collapses to a single path. Greedy algorithms are backtracking with a proof that you never need to backtrack.
- Backtracking or divide and conquer → dynamic programming. Sometimes the subproblems are not independent: the same subproblem appears again and again in the recursion tree (the Fibonacci tree is the classic picture). Then you store each answer the first time you compute it. Dynamic programming is recursion plus memory, and Module 6 is entirely about it.
- Bit manipulation is not a strategy for splitting a problem; it is a way to represent the state of the search (which columns are used, which digits are still possible, which cities are visited) so compactly that checking and updating it costs one instruction.
- Randomization is an ingredient you add to any of them: a random pivot in divide and conquer, a random value order in backtracking, random restarts in local search.
The table below compares them on the same axes. "Subproblems" means the smaller problems the paradigm creates.
| Paradigm | Subproblems | Explores | Typical cost | Correctness argument |
|---|---|---|---|---|
| Brute force | none — whole candidates | every candidate | exponential or factorial | trivially correct |
| Backtracking | one partial solution per node | the decision tree, minus pruned branches | exponential worst case, often fast in practice | completeness: every pruned branch provably contained no solution |
| Divide & conquer | independent, same shape, smaller by a constant factor | each subproblem once | polynomial, via a recurrence | induction on size + correct combine step |
| Greedy | one, after a committed choice | a single path | usually (a sort) | exchange argument or "stays ahead" |
| Dynamic programming | overlapping | each distinct subproblem once | (number of states) × (work per state) | induction over a fill order; optimal substructure |
| Randomized | any of the above | any of the above | expected or with high probability bounds | probability: expectation, tail bounds |
Which paradigm? A decision table
When you face a new problem, read its shape. This table maps common shapes to the first paradigm worth trying. It is a starting point, not a law; the lessons explain the exceptions.
| If the problem says or has… | Try first | Why | Example |
|---|---|---|---|
| "list all", "generate every", "find any valid arrangement" | Backtracking | The output itself is exponential, so nothing faster exists | Permutations, N-Queens, Sudoku |
| Hard constraints, small input ( or so), no obvious structure | Backtracking with pruning (or bitmask DP if states repeat) | Exponential is acceptable at this size; pruning makes it practical | Word search, graph colouring with few colours |
| The input splits into halves whose answers combine cheaply | Divide & conquer | Recurrence with small | Merge sort, inversion counting, closest pair |
| Arithmetic on huge numbers or matrices | Divide & conquer (Karatsuba, Strassen, FFT) | Trading one multiplication for several additions pays off recursively | Big-integer libraries |
| Pick a subset or order to maximise or minimise something, and one choice is obviously "safest" | Greedy — but prove it | Sort once, scan once | Interval scheduling, Huffman codes, MST |
| Optimisation where greedy has a counterexample | Dynamic programming | Overlapping subproblems, optimal substructure | Coin change with arbitrary coins, 0/1 knapsack |
| "count the number of ways", "minimum cost to reach" over a sequence, grid or subset | Dynamic programming | The same sub-question is asked from many directions | Grid DP, String DP |
| Sets of at most ~64 small items; flags; parity; "XOR of all" | Bit manipulation | Set operations become single instructions | Subset enumeration, single-number problems |
| An adversary could feed you the worst case; or exact answers are too expensive | Randomized | Random choices make every input behave like an average one | Random pivot, hashing with a random seed, sampling, Bloom filters |
| A search sometimes finishes instantly and sometimes runs forever | Randomized restarts | Heavy-tailed run times: a fresh random start beats waiting | SAT solvers, large N-Queens |
| The answer is a number and "is achievable?" is monotone | Binary search on the answer (a decrease-and-conquer variant) | Each test halves the range | Binary search |
Two habits make this table work. First, always write the brute force (it takes two minutes and becomes your test oracle, as Testing & Debugging Algorithms prescribes). Second, when you are tempted by greedy, look for a counterexample for five minutes before you code it. If you cannot find one, try to prove the exchange argument. If you find one, you are probably looking at a DP.
Why in this order
The order follows what each lesson needs from the earlier ones.
- Backtracking first, because it is recursion over a tree of choices, and every other paradigm is easiest to understand as a special case of that tree: divide and conquer visits it without searching, greedy follows one path, dynamic programming merges identical nodes. It also continues directly from DFS in Module 4: backtracking is DFS on an implicit graph of partial solutions.
- Divide and conquer second, because it reuses recursion but adds the one tool backtracking lacks: a way to analyse recursive running time (recurrences and the Master theorem). You met merge sort in Module 2; here it becomes a design technique you can apply to geometry and arithmetic.
- Greedy third, because its proofs (exchange arguments) are the first proofs in the course that are not plain induction, and because its failures motivate Module 6. You have already used greedy algorithms without the name: Dijkstra, Prim and Kruskal in Module 4.
- Bit manipulation fourth, as a toolkit. It is short, and by now you have search problems whose state (a set of used columns, a set of candidate digits) is begging to be packed into an integer.
- Randomized algorithms last, because they modify the earlier paradigms (random pivots, random restarts) and need the expected-value reasoning that is easiest once you have seen the deterministic versions fail on bad inputs.
- The capstone puts backtracking, bitmasks, a greedy-vs-DP comparison and randomization into one program.
flowchart TD
M4["Module 4 · Graphs (DFS)"] --> BT["Recursion & Backtracking"]
M2["Module 2 · Merge sort, quickselect"] --> DC["Divide & Conquer"]
BT --> DC
BT --> GR["Greedy"]
DC --> GR
BT --> BM["Bit Manipulation"]
DC --> RA["Randomized Algorithms"]
BT --> RA
BM --> CAP["Capstone: solver engine"]
GR --> CAP
RA --> CAP
CAP --> M6["Module 6 · Dynamic Programming"]
Arrows mean "read this first". Bit manipulation can be read at any point after backtracking.
Prerequisites
From Module 0: Recursion & Induction (every page in this module is recursive and every proof is an induction) and Complexity Analysis, especially its section on recurrences and the Master theorem. From Module 2: Merge Sort & Inversion Counting, Quick Sort and Quickselect, which are the first divide-and-conquer and randomized algorithms you met. From Module 4: DFS and Minimum Spanning Trees.
As in earlier modules, every canonical implementation is given in Python, Java, C++ and TypeScript, and each one checks itself with assertions.
Lessons
| # | Lesson | After it you will be able to… | Minutes |
|---|---|---|---|
| 1 | Recursion & Backtracking | Write the choose–explore–unchoose template, generate permutations/combinations/subsets, solve N-Queens and Sudoku, and prune with constraint checks and variable ordering | 60 |
| 2 | Divide & Conquer | Design a split–solve–combine algorithm, solve its recurrence with the Master theorem, count inversions, find the closest pair in , and multiply with Karatsuba | 70 |
| 3 | Greedy Algorithms | Recognise greedy-shaped problems, prove a greedy rule with an exchange argument, and produce the counterexample when it fails | 60 |
| 4 | Bit Manipulation | Use AND/OR/XOR/shifts fluently, enumerate subsets of a mask, and pack search state into integers | 45 |
| 5 | Randomized Algorithms | Tell Las Vegas from Monte Carlo, compute expected running times, and use random pivots, sampling and restarts | 50 |
| — | Capstone: Sudoku & N-Queens Solver Engine | Build a generic backtracking engine with bitmask constraint propagation and MRV, benchmark three solvers, and analyse greedy-vs-DP and randomized restarts | 240 |
Lesson time totals about 285 minutes, roughly 5 hours, plus 4 hours for the capstone and about as much again for the practice ladders. Ten days at an hour a day is realistic.
How to study this module
Draw the recursion tree. For every algorithm in this module, draw the tree of recursive calls for a small input (four to eight elements). For backtracking, mark the branches that are pruned. For divide and conquer, write the work done at each level next to the level; summing the levels is the Master theorem. For greedy, note that the tree is a single path. When a tree has two identical nodes, write "DP" next to them.
Prove before you trust. Greedy algorithms in particular look obviously right and are often wrong. For each greedy rule on the greedy page, try to break it with a small input before you read the proof. Keep the counterexamples; interviewers ask for them.
Measure, do not guess. Pruning and heuristics change running times by factors of a thousand, and asymptotic notation does not show it. The capstone asks you to count search nodes, not just seconds, because node counts are the same in every language and explain the seconds.
Climb the ladders. Every lesson has a "brute force → better → optimal" ladder and a practice ladder of 10–15 problems, easy to hard. Do the first half now and come back for the rest after Module 6; several hard problems are solved most cleanly by combining a paradigm from this module with DP.
Do the capstone. It is where the paradigms meet: a backtracking engine whose speed comes from bitmasks and a greedy variable-ordering heuristic, a coin-change study where greedy loses to DP, and randomized restarts that fix what pure backtracking cannot.
Start with Recursion & Backtracking, then follow the table in order. Previous module: Graphs. Next module: Dynamic Programming. Course map: DSA: Zero to Mastery.