Dynamic programming in depth
A method in five questions: state, choices, recurrence, base case and order. Coins where greedy fails, rebuilding the solution, packing a token budget, the likeliest path behind noisy readings, and what it costs.
What it covers6
Why it matters
The lesson on algorithms showed memoization and one dynamic program, edit distance. That is enough to recognize the idea and not enough to use it on a problem nobody has solved for you. This lesson teaches the method: five questions that turn "try every possibility" into a table you can fill in. It matters well beyond coding interviews. Word error rate, the alignment inside a speech recognizer, the value of a state in reinforcement learning, and choosing which passages fit in a prompt are all dynamic programs.
What you'll be able to do
- Design a dynamic program from five questions: state, choices, recurrence, base case and order
- Fill a table by hand and walk back along recorded choices to the answer itself
- Plot calls against size for plain recursion and a memo, and read the growth
- Pack a prompt to a token budget, and decode a likeliest path, with a table
Show the answer
2 coins
Two coins of 3. The natural method, taking the biggest coin that fits, starts with a 4 and is then forced to finish with two 1s: three coins. A rule that takes the best-looking step each time is called greedy, and here it is wrong. This lesson is about what to do when greedy can't be trusted.
The idea: Five questions that turn recursion into a table
This part rests on Searching, sorting and dynamic programming, where memoization and edit distance showed a recursive function answered from a table, and on Sequences and Σ, where a total was built term by term. Start with a rule that sounds right and is wrong.
A sensible rule that gives the wrong answer
With real coins, taking the biggest one that fits always gives the fewest coins. That is a property of the coin values, and it isn't a law. With coins of 1, 3 and 4, the rule fails.
The safe alternative is to try everything. Whatever the best answer is, it has a last coin. If that coin is a 3, the rest is the best way to make the amount minus 3. So try each coin as the last one, solve the smaller amount, and keep the best. That is a recursive function of three lines.
COINS = [1, 3, 4] def greedy(amount): """Take the biggest coin that fits, again and again.""" used = [] for coin in sorted(COINS, reverse=True): while amount >= coin: amount -= coin used.append(coin) return used calls = 0 def fewest(amount): """Try every coin as the last one, and keep the best. Correct, and very slow.""" global calls calls += 1 if amount == 0: return 0 return 1 + min(fewest(amount - coin) for coin in COINS if coin <= amount) for amount in (6, 10, 14): print("amount", str(amount).rjust(2), "| greedy uses", greedy(amount), "=", len(greedy(amount)), "coins | the fewest possible:", fewest(amount)) print() for amount in (10, 20, 25): calls = 0 fewest(amount) print("amount", amount, "| calls made:", format(calls, ","))
For 6, 10 and 14, greedy uses one coin more than necessary each time. The recursive function gets all three right.
The second table is the catch. To work out the answer for 10, the function calls itself 168 times. For 20 it takes 20,736 calls, and for 25, 229,970. Every extra unit multiplies the work by about one and a half. At that rate an amount of 100 would take longer than anyone would wait.
The waste is easy to see once you look for it. Making 25 means making 24, 22 and 21. Making 24 means making 23, 21 and 20. The answer for 21 has now been asked for twice, and each time it is worked out from nothing, all the way down. There are only 26 different amounts between 0 and 25. The function solves the same 26 problems hundreds of thousands of times.
Show the answer
Memory, to store each answer it has worked out
Memoization keeps a note of every answer the first time it is computed, and returns the note on later calls. The price is the memory for those notes. For the coin problem that is one number for each amount, which is a very good trade against hundreds of thousands of repeated calls.
Five questions, and a table
Dynamic programming is the cure, and it comes down to answering five questions about a problem.
- What is a state? The smallest description of a subproblem. Here: the amount still to make.
- What are the choices at a state? Here: which coin to use.
- What is the recurrence? The rule that gives a state's answer from smaller states: fewest(a) = 1 + the smallest of fewest(a − coin), over the coins that fit.
- What is the base case? fewest(0) = 0.
- In what order are states needed? Smaller amounts before larger ones.
With those answered there are two ways to write the code, and both appear below. Top-down: keep the recursion and add a memo. Bottom-up: make a list, and fill it in the order from question 5, with no recursion at all.
COINS = [1, 3, 4] calls, memo = 0, {} def fewest(amount): """The same recursion, with a note of every answer already worked out.""" global calls if amount in memo: return memo[amount] calls += 1 memo[amount] = 0 if amount == 0 else 1 + min( fewest(amount - coin) for coin in COINS if coin <= amount) return memo[amount] print("top-down, with a memo: amount 25 needs", fewest(25), "coins | calls that did any work:", calls) def table(coins, amount): """Bottom-up: fill in the answers from 0 upward, so each one only needs answers already in the list.""" best = [0] + [None] * amount for a in range(1, amount + 1): for coin in coins: if coin <= a and best[a - coin] is not None and ( best[a] is None or best[a - coin] + 1 < best[a]): best[a] = best[a - coin] + 1 return best best = table(COINS, 14) print() print("amount:", " ".join(str(a).rjust(2) for a in range(15))) print("coins: ", " ".join(str(b).rjust(2) for b in best)) print("with coins of 5 and 7 only: amount 12 needs", table([5, 7], 12)[12], "| amount 11:", table([5, 7], 11)[11])
With a memo, the amount of 25 takes 26 calls that do any work: one for each amount from 0 to 25. It took 229,970 without.
The bottom-up table shows every answer at once. Amount 6 needs 2 coins. Amount 5 needs 2 as well, a 4 and a 1. To fill in one entry the code looks back 1, 3 and 4 places, takes the smallest value it finds there, and adds one.
The last line covers a case worth planning for. With coins of 5 and 7, the amount 12 needs 2 coins, and 11 can't be made at all. The table holds None there, and the code skips states that are impossible.
best = [0, 1, 2, 1, 1] # the fewest coins for amounts 0 to 4 print(1 + min(best[5 - 1], best[5 - 3], best[5 - 4]))
Show the answer
2
The last coin is a 1, a 3 or a 4, leaving 4, 2 or 1 to make. Those need 1, 2 and 1 coins. The smallest is 1, and one more coin makes 2: a 4 and a 1, or a 1 and a 4. The new entry needed only three lookups, whatever it took to compute the earlier ones.
Each amount reads the entries 1, 3 and 4 places back. Smaller amounts are filled first, so the answers it needs are always there.
Write a sentence or two, then compare it with a good answer in the lesson.
In Python: Memos, tables and the walk back
Part 1 gave the method. Now write the code, plot what the memo saves, and recover the answer itself.
Fewest coins, bottom-up
Write fewest_coins(coins, amount): the fewest coins from coins (each usable any number of times) that add up to exactly amount, or None if it can't be made. Fill a list from 0 up to amount. Don't use recursion: the tests include an amount of 20,000.
def fewest_coins(coins, amount): return None print(fewest_coins([1, 3, 4], 6), fewest_coins([5, 7], 11))
Plot the saving
The cell below counts the calls plain recursion makes for the fewest-coins problem against the calls a memo makes, for amounts 5 to 20. The counts are exact, so the lines show growth cleanly: plain recursion curves up, the memo is a near-straight line.
from academy import measure COINS = [1, 3, 4] def plain_calls(amount): calls = 0 def fewest(a): nonlocal calls calls += 1 if a == 0: return 0 return 1 + min(fewest(a - c) for c in COINS if c <= a) fewest(amount) return calls def memo_calls(amount): calls, memo = 0, {} def fewest(a): nonlocal calls if a in memo: return memo[a] calls += 1 memo[a] = 0 if a == 0 else 1 + min(fewest(a - c) for c in COINS if c <= a) return memo[a] fewest(amount) return calls measure({"plain": plain_calls, "memo": memo_calls}, [5, 8, 11, 14, 17, 20], counts="comparisons", xlabel="amount")
Show the answer
The memo's calls grow by about 3; plain recursion's multiply
The memo does work once per amount, so three more amounts means three more calls. Plain recursion redoes the same subproblems along many routes, so its count multiplies.
The answer itself, not just its size
The table says that 14 takes 4 coins. It doesn't say which 4. Usually that is the part you wanted.
The fix is small and it works for every dynamic program. Whenever a state's best answer is found, also record which choice produced it. When the table is full, start at the final state and walk backward, following the recorded choices.
COINS = [1, 3, 4] def table(coins, amount): best, last = [0] + [None] * amount, [None] * (amount + 1) for a in range(1, amount + 1): for coin in coins: if coin <= a and best[a - coin] is not None and ( best[a] is None or best[a - coin] + 1 < best[a]): # also note WHICH coin gave the best answer best[a], last[a] = best[a - coin] + 1, coin return best, last def rebuild(last, amount): """Walk back through the notes: take the recorded coin, move to the smaller amount, repeat.""" coins = [] while amount > 0: coins.append(last[amount]) amount -= last[amount] return coins best, last = table(COINS, 14) print("amount: ", " ".join(str(a).rjust(2) for a in range(15))) print("fewest: ", " ".join(str(b).rjust(2) for b in best)) print("last coin:", " ".join(str(c if c else "-").rjust(2) for c in last)) print() for amount in (6, 10, 14): print("amount", str(amount).rjust(2), "->", rebuild(last, amount))
The new row, last coin, holds the coin that gave each amount its best answer. For 14 it is a 3.
To rebuild the coins for 14: the note says 3, so take a 3 and move to 11. The note at 11 says 3, so take another and move to 8. The note at 8 says 4, which leads to 4, and the note there says 4, which leads to 0. The coins are 3, 3, 4 and 4.
The walk back takes one step for each coin in the answer. All the searching was done while the table was filled, and one extra list was enough to keep its result.
There can be several equally good answers, such as 4 + 4 + 3 + 3 in another order, or 4 + 1 against 1 + 4. The walk returns one of them: whichever the code happened to record. If you need a particular one, say the earliest or the one with the fewest distinct coins, that preference has to be built into the comparison that fills the table.
Show the answer
The choice that gave each state its best score
One recorded choice for each state is enough. From the final state, each recorded choice leads to the earlier state it came from, and following them back spells out the whole solution. Storing a complete solution at every state would also work, and would cost far more memory.
The cheapest path across a grid
Write cheapest_path(grid). grid is a list of rows of costs. Start at the top-left cell, move only right or down, and finish at the bottom-right. Return the lowest possible total of the cells visited, including the first and the last. The state is a cell, and the recurrence is: its cost plus the cheaper of the totals for the cell above and the cell to the left. Return 0 for an empty grid.
def cheapest_path(grid): return 0 print(cheapest_path([[1, 9, 1], [1, 9, 1], [1, 1, 1]]))
Write a sentence or two, then compare it with a good answer in the lesson.
In AI and ML engineering: Packing a prompt and decoding a path
The map shows where cost lives. Two of its steps are dynamic programs: choosing which passages fit a prompt, and decoding the likeliest sequence.
A state with two parts: packing a context window
Here is a problem from a retrieval system. A search step has found seven passages for a question. Each has a length in tokens and a relevance score, and there are 800 tokens of room left in the prompt. Which passages should go in, to carry the most total relevance?
Two greedy rules suggest themselves: highest score first, and best score for each token first. For the dynamic program, ask the five questions again.
- State: which passages have been decided, and how much room is left. Two numbers: (i, b).
- Choices: leave passage i out, or put it in.
- Recurrence: best(i, b) is the larger of best(i − 1, b), and best(i − 1, b − cost) + score.
- Base case: with no passages, the best score is 0.
- Order: passage by passage.
# Passages a search step found for one question: # (name, length in tokens, how relevant it scored). CHUNKS = [("pricing table", 520, 9.0), ("refund policy", 300, 6.0), ("shipping times", 280, 5.5), ("warranty", 260, 5.0), ("store hours", 90, 1.5), ("careers page", 400, 1.0), ("returns form", 230, 4.4)] BUDGET = 800 # tokens of room left in the prompt def pack(chunks, budget, step=10): """best[i][b]: the highest total score using only the first i chunks, with b units of room (1 unit = `step` tokens).""" n, room = len(chunks), budget // step best = [[0.0] * (room + 1) for i in range(n + 1)] for i in range(1, n + 1): cost, score = chunks[i - 1][1] // step, chunks[i - 1][2] for b in range(room + 1): # choice 1: leave chunk i out best[i][b] = best[i - 1][b] if cost <= b and best[i - 1][b - cost] + score > best[i][b]: # choice 2: put it in, with less room for the rest best[i][b] = best[i - 1][b - cost] + score chosen, b = [], room # walk back: was chunk i put in? for i in range(n, 0, -1): if best[i][b] != best[i - 1][b]: chosen.append(i - 1) b -= chunks[i - 1][1] // step return chosen[::-1], (n + 1) * (room + 1) def greedy(order): """Go through the chunks in the given order, taking each one that still fits.""" room, chosen = BUDGET, [] for i in order: if CHUNKS[i][1] <= room: chosen.append(i) room -= CHUNKS[i][1] return sorted(chosen) def show(name, chosen): print(name.ljust(27), "| tokens", sum(CHUNKS[i][1] for i in chosen), "| total score", round(sum(CHUNKS[i][2] for i in chosen), 1), "|", ", ".join(CHUNKS[i][0] for i in chosen)) everything = range(len(CHUNKS)) show("highest score first", greedy(sorted(everything, key=lambda i: -CHUNKS[i][2]))) show("best score per token first", greedy(sorted(everything, key=lambda i: -CHUNKS[i][2] / CHUNKS[i][1]))) chosen, cells = pack(CHUNKS, BUDGET) show("dynamic programming", chosen) print() print("cells in the table:", cells, "| possible sets of 7 chunks:", 2 ** len(CHUNKS))
Highest score first takes the pricing table, which uses 520 tokens, and has room for one more passage: a total of 14.5. Best score per token first does worse, 13.0, and leaves 130 tokens unused. The dynamic program finds a set neither rule considered: three medium passages, for 15.4.
Greedy rules go wrong here for the same reason as with the coins. An early choice that looks good uses up room that a better combination needed.
The walk back is in the last lines of pack. From the final cell, it asks at each passage whether the score changed when that passage became available. If it did, the passage was put in.
The last line is a fair warning. The table has 648 cells, and seven passages have only 128 possible sets, so trying them all would have been less work. The next part shows where that changes.
print((7 + 1) * (800 // 10 + 1), 2 ** 7)
Show the answer
648 128
There are 8 rows and 81 columns: 648 cells. Each passage is either in or out, so 7 passages have 2⁷ = 128 possible sets. For a problem this small, brute force is cheaper. The table's size grows in step with the number of passages, while the number of sets doubles with each one.
What it costs, and when it doesn't fit
The cost of a dynamic program can be read from the five questions: the number of states, times the choices at each. Memory is the number of states.
def coins_table(coins, amount): best = [0] + [None] * amount for a in range(1, amount + 1): for coin in coins: if coin <= a and best[a - coin] is not None and ( best[a] is None or best[a - coin] + 1 < best[a]): best[a] = best[a - coin] + 1 return best print("coins: states = amount + 1, choices at each = number of coins") for amount in (1000, 100000): answer = coins_table([1, 3, 4], amount)[amount] print(" amount", format(amount, ",").rjust(7), "| steps of work:", format((amount + 1) * 3, ",").rjust(7), "| answer:", format(answer, ","), "coins") print() print("packing: states = (chunks + 1) x (units of room + 1), 2 choices at each") print("chunks | room | 1 unit = | cells in the table | sets to try by brute force") for chunks, budget, step in ((7, 800, 10), (40, 800, 10), (40, 8000, 10), (40, 8000, 1)): unit = str(step) + (" token" if step == 1 else " tokens") cells = (chunks + 1) * (budget // step + 1) print(str(chunks).rjust(6), "|", format(budget, ",").rjust(7), "|", unit.ljust(10), "|", format(cells, ",").rjust(18), "|", format(2 ** chunks, ","))
For the coins, an amount of 100,000 takes about 300,000 steps. Plain recursion could not finish an amount of 100.
For packing, the comparison with brute force turns around quickly. With 40 passages there are 3,321 cells and more than a trillion possible sets.
The last two rows show the table's weakness. Its width is the size of the budget, counted in whatever unit you choose. With 8,000 tokens of room counted one token at a time, the table has 328,041 cells, a hundred times the number at 10 tokens a unit. A dynamic program over a quantity grows with the size of the number. Rounding costs to coarser units is the usual remedy, at a small cost in exactness.
Three conditions decide whether the method fits at all.
- Subproblems overlap. If none is ever asked for twice, there is nothing to save.
- Best answers are built from best answers. The best way to make 14 contains a best way to make 11.
- The state is small. For the shortest route through 30 cities, visiting each once, the state must say which cities have been visited, and there are over a billion such sets.
One practical note: Python stops at about a thousand nested calls, so large tables are filled bottom-up, not by recursion.
Show the answer
The shortest route that visits each of 30 cities once
For the route, a subproblem has to record which cities have already been visited, and 30 cities have over a billion subsets, so the table is too large to fill. The other three have small states: two positions in the words, an amount, or a count of items and the room left.
A cached recursion over a vocabulary
Tokenizing a word into the fewest pieces from a vocabulary is a dynamic program: the state is how much of the word is left, and the choices are the vocabulary pieces it starts with. functools.cache is the top-down table, one line.
from functools import cache VOCAB = {"un", "break", "able", "unbreak", "a", "b", "e", "k", "l", "n", "r", "u"} @cache def fewest_tokens(text): if not text: return 0 options = [1 + fewest_tokens(text[len(t):]) for t in VOCAB if text.startswith(t)] return min(options) print(fewest_tokens("unbreakable")) print(fewest_tokens.cache_info().misses, "distinct suffixes worked out")
Real tokenizers use a different method (byte pair merges), but this table is the idea behind choosing the cheapest way to cover a text. Beam search and constrained decoding uses the same table-and-walk-back shape to pick the likeliest sequence of words.
Worked example: the likeliest story behind noisy readings
A classic dynamic program in machine learning finds the best path through a chain of hidden states. A machine is either ok or failing, and it rarely switches. A sensor reads low or high each minute, and is often wrong. From 40 readings, what most likely happened? The state is (minute, condition), the choices are the two conditions a minute earlier, and the score is a log probability. It is known as the Viterbi algorithm.
import math, random # A machine is "ok" or "failing". It rarely changes. # Each minute a sensor reads "low" or "high", and it is noisy. STATES = ("ok", "failing") START = {"ok": 0.9, "failing": 0.1} # chance of each next state STAY = {"ok": {"ok": 0.95, "failing": 0.05}, "failing": {"ok": 0.10, "failing": 0.90}} # chance of each reading READS = {"ok": {"low": 0.8, "high": 0.2}, "failing": {"low": 0.3, "high": 0.7}} rng = random.Random(3) state, truth, readings = "ok", [], [] for minute in range(40): if minute: state = "ok" if rng.random() < STAY[state]["ok"] else "failing" truth.append(state) readings.append("low" if rng.random() < READS[state]["low"] else "high") def best_path(readings): """score[s]: the log chance of the likeliest history that ends in state s now. One pass forward, one walk back.""" score = {s: math.log(START[s]) + math.log(READS[s][readings[0]]) for s in STATES} came_from = [] for reading in readings[1:]: new, back = {}, {} for s in STATES: # the best state to have come from before = max(STATES, key=lambda p: score[p] + math.log(STAY[p][s])) new[s] = (score[before] + math.log(STAY[before][s]) + math.log(READS[s][reading])) back[s] = before score = new came_from.append(back) path = [max(STATES, key=lambda s: score[s])] for back in reversed(came_from): path.append(back[path[-1]]) return path[::-1] def line(items): return "".join("#" if item in ("failing", "high") else "." for item in items) def judge(name, guess): print(name.ljust(22), line(guess), "| minutes right:", sum(a == b for a, b in zip(guess, truth)), "of 40", "| changes of mind:", sum(a != b for a, b in zip(guess, guess[1:]))) print("sensor readings ", line(readings), " (# is a high reading)") print("what really happened ", line(truth), " (# is failing)") judge("each reading alone", ["failing" if r == "high" else "ok" for r in readings]) judge("likeliest whole path", best_path(readings)) print("possible paths:", format(2 ** 40, ","), "| scores computed:", 2 * 40) import matplotlib.pyplot as plt alone = ["failing" if r == "high" else "ok" for r in readings] guess = best_path(readings) rows = [("sensor: high", readings, "high"), ("truth: failing", truth, "failing"), ("each reading alone", alone, "failing"), ("whole path", guess, "failing")] fig, ax = plt.subplots(figsize=(7, 2.6)) for k, (name, seq, mark) in enumerate(rows): level = [3 - k + 0.6 * (x == mark) for x in seq] ax.step(range(40), level, where="mid", label=name) ax.set_yticks([]) ax.set_xlabel("minute") ax.set_title("Readings, the truth and two ways to guess it") ax.legend(loc="upper left", fontsize=7, ncol=2)
The second line is what really happened. Counting minutes from 0, the machine began failing at minute 27, recovered for one minute, failed again, and was back to normal for the last two. Judging each reading alone gets 30 of 40 minutes right and changes its mind 16 times, raising the alarm at minutes 5, 6, 13, 18 and 20, when nothing was wrong. The dynamic program gets 36 of 40 right and changes its mind once. It is not smoothing by a rule of thumb. For each minute and each condition it keeps the score of the likeliest history ending there, built from the two scores a minute earlier, and a recorded choice lets it walk back from the end, as in the coin problem. Two scores a minute for 40 minutes is 80 numbers, in place of a search through over a trillion possible paths. Its answer is the likeliest path under the model's assumptions, which is not always the truth: it reports the failure one minute early, and misses both the brief recovery and the return to normal at the end, since a machine that rarely switches is unlikely to have done so four times. With other random runs, a short failure that produced few high readings can be missed completely.
Show the answer
It scores whole histories, and a brief switch of state is unlikely
Each path's score includes the chance of every change of state along it. Since the machine rarely switches, a path that flips to failing for one minute and back pays for two unlikely changes, and loses to a path that treats the reading as noise. Several high readings in a row are another matter: then a real change becomes the likelier story.
Goes deeper in
- Beam search and constrained decoding: beam search and decoding, the Viterbi idea at model scale.
- Searching for solutions: finding best routes with a priority queue.
- Recognition and synthesis as a pipeline: word error rate, the edit-distance table on speech.
- Markov chains: chains of states, like the machine that rarely switches.
Write a sentence or two, then compare it with a good answer in the lesson.
Practice what you just read
- 8 code examples you can edit and run
- a practice exercise that checks your code
- a 5-question quiz
- 12 review cards for spaced repetition
Try a quiz question
What makes plain recursion slow on a problem such as fewest coins, and what does dynamic programming change?
Before this lesson
Where this lesson leads.
575 lessons in thirteen phases. 176 are free without an account, and a free account opens the rest. See every lesson.
Phase 7 · about 48 hours of study
Software engineering
How software is built, from bits to tested, well-designed programs
59 lessons 1 free
- Iterators and generators FreeThe iteration protocol, yield, lazy pipelines and itertools, in small memory.45 min
- Context managersSetup and cleanup that always run: with, contextlib, transactions and atomic writes.35 min
- Closures and decoratorsFunctions that remember, wrap and extend other functions.40 min
- Exceptions in depthError hierarchies, chaining, notes, exception groups and warnings.40 min
- Pattern matchingmatch and case: literal, sequence, mapping and class patterns with guards.35 min
- Text, bytes and encodingsstr and bytes, UTF-8, decoding errors, normalization and base64.35 min
- Binary filesBytes as numbers, endianness, struct records, file signatures and checking uploads.45 min
- Testing your codeAutomated tests that prove code works and keep it working.45 min
- Testing with pytestFixtures, parametrize, mocks, temporary files and coverage.45 min
- Testing numeric and random codeClose enough for floats, seeds and what they fix, properties that hold for any input, a gradient check and overfit-one-batch.40 min
- Debugging systematicallyFind any bug with a method instead of guesswork.35 min
- Readable code and refactoringWrite code people can understand, and improve it safely.35 min
- Code style and toolsPEP 8, formatters, linters and type checkers, and how they fit together.35 min
- Types and data modelingType hints, dataclasses and checking data at the edges of a program.35 min
- Typing in depthGenerics, protocols, TypedDict, Literal and narrowing, checked by mypy.45 min
- Classes in depthProperties, alternative constructors, abstract base classes and tuned dataclasses.40 min
- Make your classes feel built inSpecial methods for printing, equality, ordering, arithmetic and containers.45 min
- Software designModules, interfaces and dependencies that keep big programs changeable.45 min
- LoggingLoggers, levels, handlers and configuration, without leaking secrets.40 min
- How computers run codeBits, memory, the processor, and what really happens when Python runs.40 min
- Arrays in memoryBuffers, dtypes, shapes and strides: why a transpose is free, and which operations copy.40 min
- Algorithm complexityCount the work code does, and see why some programs stop scaling.40 min
- Concurrency and asyncDo many things at once: processes, threads and the event loop.45 min
- Performance and profilingMeasure before you optimize, then fix the part that matters.45 min
- Profiling numeric code and a training loopWhere a training step spends its time, Amdahl's rule by hand, and cProfile on a loop with a slow batch function.40 min
- Reading C, C++, CUDA and RustPointers and loops in C, references and templates in C++, one-thread-per-element CUDA kernels, and Rust's Option, Result and ownership.30 min
- Core data structuresArrays, linked lists, stacks, queues and the hash table behind every dict.45 min
- Heaps and priority queuesA list read as a tree: the best k of a million without sorting, and where top-k hides in AI work.35 min
- Recursion, trees and graphsFunctions that call themselves, and the shapes most real data takes.45 min
- Searching, sorting and dynamic programmingThe classic algorithms, and the ideas behind them.45 min
- Dynamic programming in depthA method in five questions: state, choices, recurrence, base case and order. Coins where greedy fails, rebuilding the solution, packing a token budget, the likeliest path behind noisy readings, and what it costs.45 min
- Binary search trees and traversalsInsert, search and delete in a sorted tree, walk it four ways, and see why balance and B-trees matter.45 min
- Patterns for coding problemsTwo pointers, counting with dictionaries, prefix sums and sliding windows: O(n) answers to classic problems.45 min
- Project: a spell checker, three waysA sorted list, a hash set and a trie, measured for speed and memory, with suggestions.45 min
- Searching for solutionsBacktracking with pruning, Dijkstra's algorithm and A*, ending with an optimal sliding-puzzle solver.45 min
- Project: an unbeatable game opponentGame state and rules, minimax with a cache, and an exhaustive test that proves it never loses.45 min
- Databases and SQLStore, query and join data with the language every database speaks.40 min
- SQL for analysisSubqueries, CASE, common table expressions, outer joins and window functions on real order data.45 min
- Designing a databaseFrom one big table to related tables: keys, constraints, many-to-many and a loader that is safe to rerun.40 min
- Databases with an ORMSQLAlchemy models, sessions, relationships, transactions and the N+1 problem.45 min
- Changing a database safelyNumbered migrations in transactions, required columns and backfills, and expand-and-contract changes.40 min
- Secure codingInjection, escaping, secrets and passwords: the mistakes attackers look for.40 min
- Projects, packaging and CILay out a real project, pin its dependencies and test it on every push.35 min
- Config files: YAML and TOMLWrite YAML and TOML that parse as you meant, dodge the type traps, and validate what you load.25 min
- Command-line programsargparse subcommands, stdin, exit codes and testable main functions.40 min
- Packaging your codepyproject.toml, the src layout, versions, entry points and wheels.45 min
- Pipes and text tools in the shellgrep, wc, sort, uniq, head and cut, chained with pipes to answer questions about logs and data.25 min
- JSON on the command line: curl and jqCall APIs with curl, fail on HTTP errors, and pull values out of JSON with jq paths and select.25 min
- Shell scripts that fail safelyTurn commands into scripts with variables, set -euo pipefail and clear exit codes, and know when to switch to Python.25 min
- Reading and writing XMLElementTree, attributes and text, namespaces, building XML safely, and untrusted input.35 min
- Project: a word-guessing gamePlan a game with a flowchart, then build it from tested functions and one input loop.40 min
- Project: a card game of 21Turn written rules into functions, and make randomness testable.40 min
- Project: a drinks kioskA program with state and commands, built with functions, then refactored into classes.45 min
- Project: a flashcard trainerCards from a file, review boxes, and progress saved between runs.45 min
- Project: a price-watch alert botAn API client, alert rules, digest emails and a state file, so reruns never repeat.45 min
- Project: Pack Train, an arcade gameA grid game on the turtle canvas: game state as classes, a timer loop, key handlers and a saved best score.45 min
- Project: a private password-breach checkHash locally, send five characters, match locally: k-anonymity, safe logging and failure handling.40 min
- Capstone: a command-line appDesign, build and test a complete program with a database.45 min
- Capstone: ship a small model libraryA typed, tested and profiled package with a train and an eval command, a YAML config, logging and a wheel.45 min
Never trained an AI? Teach a small one to write, right in your browser. It takes about 20 seconds and needs no account. Teach it to write