Algorithms for Hard Problems: Grade 12 Computing

Roads with lengths: weighted graphs

In Grade 10 you stored a graph as a dictionary of neighbors and searched it one ring at a time with breadth-first search. That search counts roads. But nobody planning a journey counts roads: they want the fewest kilometers, or the fewest hours. Grade 10 ended there, with a graph that has a number on every edge: a weighted graph. Each edge’s number is its weight: a length, a time, a fare, whatever the question is about.

Here are some of Nepal’s main highways between eleven towns, with their lengths. The lengths are road distances between the town centers along the highways named, measured on OpenStreetMap’s map of Nepal (the Rajpath’s from its published length) and rounded to the nearest 5 km; the real roads have many more towns and turnings on them.

Road	Highway	Length (km)
Kathmandu – Dhulikhel	Araniko Highway	30
Kathmandu – Mugling	Tribhuvan Rajpath, then Prithvi Highway	110
Kathmandu – Hetauda	Tribhuvan Rajpath	130
Mugling – Pokhara	Prithvi Highway	90
Mugling – Bharatpur	Narayangadh–Mugling road	35
Bharatpur – Hetauda	East–West Highway	75
Bharatpur – Butwal	East–West Highway	120
Hetauda – Pathlaiya	East–West Highway	40
Pathlaiya – Birgunj	Tribhuvan Rajpath	25
Pathlaiya – Bardibas	East–West Highway	100
Dhulikhel – Bardibas	BP Highway (through Sindhuli)	160
Pokhara – Tansen	Siddhartha Highway	120
Tansen – Butwal	Siddhartha Highway	40

Two ways to store it

A program needs this as data, and Grade 10’s question still decides how: what will the program do most often? A route search stands at a town and asks, again and again, “which towns can I drive to from here, and how far is each?”

So the best structure is again a dictionary of neighbors, but now each town’s value is not a list of names. It is a second dictionary, from each neighbor to the road’s length. A dictionary inside a dictionary:

roads = {    "Mugling": {"Kathmandu": 110, "Pokhara": 90, "Bharatpur": 35},    "Pokhara": {"Mugling": 90, "Tansen": 120},    ...}

roads["Mugling"] gives Mugling’s neighbors with their lengths, and roads["Mugling"]["Pokhara"] the length of one road, 90 km, each in one lookup. This is still called an adjacency list, a weighted one.

The other way is a table (an adjacency matrix), with a row and a column for every town, the length where two towns are joined by a road, and a dash where they aren’t:

	Kathmandu	Dhulikhel	Mugling	Pokhara	Bharatpur
Kathmandu	0	30	110	–	–
Dhulikhel	30	0	–	–	–
Mugling	110	–	0	90	35
Pokhara	–	–	90	0	–
Bharatpur	–	–	35	–	0

This is only five of the eleven towns. The whole table has 11 × 11 = 121 cells, and only 26 of them hold a road (each road twice, once in each direction). A table is quick for one question, “how long is the road from A to B?”, and is easy to read on paper, which is why road atlases print one. But for a country’s thousands of junctions, nearly every cell would be a dash. For searching, the dictionary wins, as it did in Grade 10.

Keep the data in a file, one road a line, and let a program build the dictionary, so that no road is ever written at only one end:

highways.csv

Kathmandu,Dhulikhel,30Kathmandu,Mugling,110Kathmandu,Hetauda,130Mugling,Pokhara,90Mugling,Bharatpur,35Bharatpur,Hetauda,75Bharatpur,Butwal,120Hetauda,Pathlaiya,40Pathlaiya,Birgunj,25Pathlaiya,Bardibas,100Dhulikhel,Bardibas,160Pokhara,Tansen,120Tansen,Butwal,40

def add_road(graph, a, b, km):    if a not in graph:        graph[a] = {}    if b not in graph:        graph[b] = {}    graph[a][b] = km    graph[b][a] = km roads = {}with open("highways.csv", encoding="utf-8") as f:    for line in f:        a, b, km = line.strip().split(",")        add_road(roads, a, b, int(km)) print(roads["Mugling"])print("Mugling to Pokhara:", roads["Mugling"]["Pokhara"], "km")print("Is there a road from Pokhara to Birgunj?", "Birgunj" in roads["Pokhara"])

Output

{'Kathmandu': 110, 'Pokhara': 90, 'Bharatpur': 35}Mugling to Pokhara: 90 kmIs there a road from Pokhara to Birgunj? False

Line 11 splits each line into its three parts, and int(km) turns the length from text into a number, so it can be added up later. add_road puts the road in both towns’ dictionaries, at both ends.

A weighted graph is stored as roads = {"A": {"B": 7, "C": 2}, "B": {"A": 7}, "C": {"A": 2}}. What is roads["A"]["C"]?

Pick an answer to see why.

A program stores the 5,000 villages of a district and the trails between them, most villages with two to four trails. Which is the best way to store them for finding routes?

Pick an answer to see why.

The shortest route: Dijkstra’s algorithm

Grade 10 gave you the idea. Pour water at the start and let it run out along every road at the same speed. It reaches near places first and far places later, and the first moment it reaches any place, it has come along the shortest way there. A search that copies the water must visit places in order of their distance from the start: always the nearest place it hasn’t visited yet.

By hand

Keep three things on paper:

for every town reached so far, the shortest distance found so far and the town it came from (Grade 10’s came_from);
the waiting list: towns reached but not yet visited, with their distances;
the towns already visited. Once a town is visited, its distance is final.

The algorithm, called Dijkstra’s algorithm:

Write the start with distance 0. It is the only town waiting.
While towns are waiting:
1. Take the waiting town with the smallest distance, and visit it. Its distance is now final. If it is the goal, stop.
2. For each road out of it, to a town not yet visited: add the road’s length to this town’s distance. If that is shorter than the distance written for the other town (or it has none yet), write the new distance, and write that it came from this town. It is now waiting, if it wasn’t already.
Follow the came-from notes back from the goal, as in Grade 10, to read the route.

Step 2.2 is the heart of it: a town’s distance can go down while it waits, when a shorter way to it turns up. That is called relaxing a road (the town’s distance relaxes to a smaller value).

Press Next step to visit one town at a time. Each town shows the shortest distance found so far; the waiting list is under the map, nearest first. Watch Tansen’s number when Butwal is visited. Tap any other town to make it the goal instead.

Waiting, nearest first:

Kathmandu 0

Towns visited: 0
Waiting: 1
Route to Tansen: –

Kathmandu is waiting, at 0 km. The goal is Tansen. Press Next step, or tap another town to make it the goal.

In Dijkstra’s algorithm, which town is visited next?

Pick an answer to see why.

Why nearest first is right

When the nearest waiting town is taken, say Pokhara at 200 km, could there still be a shorter way to it that the search hasn’t found? Any other way to Pokhara would have to leave the visited towns through some waiting town, and every waiting town is already at least 200 km away, the nearest of them being Pokhara itself. The rest of that way can only add more kilometers. So no other way can be shorter, and Pokhara’s 200 is final.

That argument needs one thing to be true: no road has a negative length. Kilometers, hours and fares are never negative, so for routes it always holds.

In Python, with a priority queue

The waiting list needs two operations: add a town with its distance, and take the nearest. That is exactly a priority queue, and Grade 11’s Data Structures built one as a heap, where both take only about log₂ n steps. Python’s heapq keeps a heap in a list; we push pairs (distance, town), and heappop always gives back the smallest distance.

One small problem: when a town’s distance goes down (Tansen, from 320 to 305), a heap can’t easily find the old entry to change it. So the program simply pushes the town again with its new distance, and when the old, longer entry comes out of the heap later, it notices the town is already visited and skips it.

import heapq def add_road(graph, a, b, km):    if a not in graph:        graph[a] = {}    if b not in graph:        graph[b] = {}    graph[a][b] = km    graph[b][a] = km roads = {}with open("highways.csv", encoding="utf-8") as f:    for line in f:        a, b, km = line.strip().split(",")        add_road(roads, a, b, int(km)) def shortest_route(graph, start, goal):    best = {start: 0}            # shortest distance found so far    came_from = {start: None}    done = set()                 # towns whose distance is final    waiting = [(0, start)]       # a heap of (distance, town)    while len(waiting) > 0:        km, place = heapq.heappop(waiting)        if place in done:            continue             # an old, longer entry: skip it        done.add(place)        print("visit", place, km)        if place == goal:            route = []            while place is not None:                route.append(place)                place = came_from[place]            route.reverse()            return km, route        for nxt, road_km in graph[place].items():            new_km = km + road_km            if nxt not in best or new_km < best[nxt]:                best[nxt] = new_km                came_from[nxt] = place                heapq.heappush(waiting, (new_km, nxt))    return None print(shortest_route(roads, "Kathmandu", "Tansen"))

Output

visit Kathmandu 0visit Dhulikhel 30visit Mugling 110visit Hetauda 130visit Bharatpur 145visit Pathlaiya 170visit Bardibas 190visit Birgunj 195visit Pokhara 200visit Butwal 265visit Tansen 305(305, ['Kathmandu', 'Mugling', 'Bharatpur', 'Butwal', 'Tansen'])

The visits are the rows of your hand table, in the same order. Each part of the hand method is a data structure: best and came_from are dictionaries, done is a set (Python’s collection of things with no order and no repeats, which answers place in done at once, like a dictionary’s keys), and waiting is the heap. Lines 34–38 are step 2.2, relaxing each road. graph[place].items() gives each neighbor together with its road’s length.

Python compares the pairs in the heap by their first item, the distance, and on a tie by the second, the town’s name. From Pokhara, for example, Hetauda and Kathmandu are both 200 km away, and Hetauda, H, comes out before Kathmandu, K (exercise b. at the end of the unit).

How much work?

With the heap, each road is looked at twice (once from each end), each push or pop takes about log₂ n steps for a heap of n entries, and so the work grows only a little faster than the size of the map. Without a heap, finding the nearest waiting town means looking through every waiting town at every visit; for a map of a million junctions that is around a million looks a visit, a million visits: a million million looks. Choosing the right data structure turns a search that would take days into one that takes moments. Grade 12’s next unit, The Limits of Computing, gives this kind of comparison its proper name and notation.

A story from computing

Twenty minutes on a café terrace

In 1956 Edsger Dijkstra, a programmer in his mid-twenties at the Mathematical Centre in Amsterdam, needed a problem to show off its new computer, the ARMAC, to visitors who knew nothing about computers. He chose finding the shortest road between two Dutch cities, on a map of 64 cities. “One morning I was shopping in Amsterdam with my young fiancée,” he remembered, “and tired, we sat down on the café terrace to drink a cup of coffee and I was just thinking about whether I could do this, and I then designed the algorithm for the shortest path.” He worked it out without pencil and paper, in about twenty minutes. It was published in 1959, in three pages, and its ideas are now in every map app and in many of the routers that carry the internet’s messages.

An older man with gray hair, glasses and a gray beard, in a checked shirt and a red sweater, looking to one side — **Figure 1.1** Edsger Dijkstra in 2002, the year he died. He won the Turing Award, computing’s highest prize, in 1972. Photo: Hamilton Richards, CC BY-SA 3.0

In the hand search, Tansen was given 320 km when Pokhara was visited. Why didn’t the search stop and answer 320?

Pick an answer to see why.

Aiming at the goal: A*

Dijkstra’s algorithm spreads out evenly in every direction, like the water. Looking for Tansen, in the far west, it visited Dhulikhel, Bardibas and Birgunj, all to the east and south, because they were near Kathmandu. A person reading a map wouldn’t waste a moment on them: they know Tansen lies to the west.

The fix is to give the search that knowledge. For each town, add an estimate of the distance still left to the goal. The easiest estimate that a computer can always work out is the straight-line distance, as the crow flies, from the towns’ positions on the map. Then visit, not the town nearest the start, but the one with the smallest

$\text{distance so far} + \text{estimate of the distance left}$

the town that seems to be on the shortest whole journey. Towns behind you get a large estimate and wait; towns towards the goal go first. This search is called A* (said “A star”). The estimate is called a heuristic: a rule of thumb that guides a search without being exactly right.

A town as a grid of streets, each square 100 m. The search starts at the green square and looks for the red one. Press Search and watch which squares it visits. Then switch the estimate and search again. Tap squares to add or remove buildings (dark), and see how each search finds its way round them.

Estimate:

Squares visited: 0
Route: –
Shortest?: –

Press Search.

What you should see

The estimate must never be too high

A* is sure to find the shortest route when the estimate never says the distance left is more than it really is. The straight line is safe: no road between two towns can be shorter than the straight line between them.

(One more condition matters for the program below, which never visits a town twice: going along any road, the estimate must not drop by more than the road’s length. The straight line meets this too, for the same reason: walking 40 km can bring you at most 40 km closer to the goal.)

Why does it matter? Suppose the estimate is three times the straight line. Then towns near the goal look wonderfully close and everything else looks terribly far, so the search rushes along the first road that heads the right way, reaches the goal, and stops, before it has checked the roads that looked worse but were shorter. An estimate that is too low only makes A* look at more towns, like Dijkstra’s algorithm (whose estimate is 0, the lowest of all); an estimate that is too high can make it give a wrong answer.

The same highways, from Kathmandu to Tansen. Choose an estimate, then press Finish, and compare the towns visited and the route found. Each waiting town shows its distance so far + its estimate; the smallest total goes next.

Estimate:

Waiting, smallest total first:

Kathmandu 0 + 175

Towns visited: 0
Waiting: 1
Route to Tansen: –

Kathmandu is waiting: 0 km so far + 175 estimate. The goal is Tansen. Press Next step.

What you should see

A* in Python: one function, any estimate

Dijkstra’s algorithm and A* are the same program except for the number the heap is ordered by. So write the search once, and pass the estimate in as a function: estimate(place) gives the estimate for any town. Dijkstra’s algorithm is then A* with an estimate that always says 0. This is procedural abstraction: the part that differs becomes a parameter, and one function does the work of three.

import heapq def add_road(graph, a, b, km):    if a not in graph:        graph[a] = {}    if b not in graph:        graph[b] = {}    graph[a][b] = km    graph[b][a] = km roads = {}with open("highways.csv", encoding="utf-8") as f:    for line in f:        a, b, km = line.strip().split(",")        add_road(roads, a, b, int(km)) # straight-line km from each town to Tansento_tansen = {"Kathmandu": 175, "Dhulikhel": 199, "Mugling": 99, "Pokhara": 57,             "Bharatpur": 88, "Hetauda": 154, "Pathlaiya": 164, "Birgunj": 162,             "Bardibas": 251, "Butwal": 20, "Tansen": 0} def find_route(graph, start, goal, estimate):    best = {start: 0}    came_from = {start: None}    done = set()    waiting = [(estimate(start), 0, start)]    while len(waiting) > 0:        guess, km, place = heapq.heappop(waiting)        if place in done:            continue        done.add(place)        if place == goal:            route = []            while place is not None:                route.append(place)                place = came_from[place]            route.reverse()            return km, route, len(done)        for nxt, road_km in graph[place].items():            new_km = km + road_km            if nxt not in best or new_km < best[nxt]:                best[nxt] = new_km                came_from[nxt] = place                heapq.heappush(waiting, (new_km + estimate(nxt), new_km, nxt))    return None def no_estimate(place):    return 0 def straight_line(place):    return to_tansen[place] def too_high(place):    return 3 * to_tansen[place] for name, estimate in [("Dijkstra", no_estimate), ("A*", straight_line), ("Too high", too_high)]:    km, route, visited = find_route(roads, "Kathmandu", "Tansen", estimate)    print(name, km, "km,", visited, "towns visited:", " → ".join(route))

Output

Dijkstra 305 km, 11 towns visited: Kathmandu → Mugling → Bharatpur → Butwal → TansenA* 305 km, 8 towns visited: Kathmandu → Mugling → Bharatpur → Butwal → TansenToo high 320 km, 4 towns visited: Kathmandu → Mugling → Pokhara → Tansen

The heap now holds three things for each entry: the total it is ordered by, the distance so far, and the town (lines 23 and 39). The straight-line distances were worked out from each town’s latitude and longitude, and rounded down, so they can never be too high.

The last line of the program is a small experiment: the same test, three algorithms, measured two ways, by the length of the route (is it right?) and by the towns visited (how much work?). That is how computer scientists compare algorithms. On eleven towns, A* saves 3 visits. On a country’s million junctions, an even spread visits places for hundreds of kilometers in every direction, and aiming at the goal saves far more.

A tall robot on wheels: a box-shaped base, a column of electronics, and a camera and range finder on top, with labels pointing to its parts — **Figure 1.2** Shakey the robot in 1972, with its parts labeled: a television camera and a range finder on top, the electronics in the box below, and wheels and bump detectors at the bottom. Shakey is now in the Computer History Museum in California. Photo: SRI International, CC BY-SA 3.0

What a map app adds

A map app is A*, or a cousin of it, on a giant weighted graph: every junction a node, every stretch of road an edge, weighted by the time it takes to drive, worked out from the road’s length and type and from how fast phones on it are moving now. It also does a great deal of work before anyone asks: it finds the important long roads and stores shortcuts between far-apart junctions, so a search from Ilam to Mahendranagar never looks at the lanes of every town on the way. The ideas are the ones in this section; the size and the tricks are what make it answer in under a second.

An A* search uses an estimate that is sometimes higher than the real distance left. What can go wrong?

Pick an answer to see why.

Greedy choices

Give change from a Rs 1,000 note for a bill of Rs 215. The change is Rs 785. A shopkeeper doesn’t try every mix of notes and coins. She takes the biggest note that fits, Rs 500, leaving 285; the biggest that fits that, Rs 100, leaving 185; another 100, leaving 85; then 50, 20, 10 and 5. Seven pieces, and no smaller number of notes and coins makes Rs 785.

An algorithm that, at every step, takes the choice that looks best right now, and never goes back on it, is a greedy algorithm. Greedy algorithms are fast and easy to write. The question is always: is the best-looking step now also part of the best answer overall?

def greedy_change(amount, coins):    given = []    for coin in sorted(coins, reverse=True):        while amount >= coin:            given.append(coin)            amount = amount - coin    return given nepal = [1, 2, 5, 10, 20, 50, 100, 500, 1000]print(greedy_change(1785, nepal))print(greedy_change(40, nepal))print(greedy_change(40, nepal + [25]))

Output

[1000, 500, 100, 100, 50, 20, 10, 5][20, 20][25, 10, 5]

The last line asks: what if a Rs 25 note were in everyday use? (Nepal did print one, in 1997, for the silver jubilee of King Birendra’s coronation, but only a few, and few people have ever paid with one.) Then the greedy method pays Rs 40 as 25 + 10 + 5, three pieces, when 20 + 20 is only two. Taking the 25 looked best, and it was a mistake that no later step could undo.

For Nepal’s notes and coins in everyday use (1, 2, 5, 10, 20, 50, 100, 500 and 1,000 rupees, as of 2026), the greedy method always gives the fewest; you will test that with a program soon. But that is a property of these particular values, not of the method. Change the values and greedy can fail.

Each square is an amount from 1 to 100. Choose a set of coins. A red square is an amount where taking the biggest coin first does not give the fewest coins. Tap a square to compare the greedy change with the best.

Coins:

Greedy (biggest first): 25 + 10 + 5 (3)
The fewest: 20 × 2 (2)

Values: 1, 2, 5, 10, 20, 25, 50, 100

Rs 40: greedy gives 25 + 10 + 5, 3 coins, but the best is 20 × 2, only 2. Greedy fails at 10 amounts from 1 to 100.

What you should see

Greedy that works

Sometimes the greedy choice is provably right. You have already met one: Dijkstra’s algorithm is greedy. At every step it takes the nearest waiting town and never changes its mind about it, and the argument in “Why nearest first is right” shows that this is never a mistake, as long as no road is negative.

Another: the school hall can be booked for one event at a time, and seven clubs have asked for it on Saturday, each for its own hours. To fit in as many events as possible, take the request that finishes earliest, then the next that starts after it finishes earliest, and so on. Finishing earliest leaves the most time for everything after it, so no other first choice could let more events fit.

Coins are 1, 6 and 10. What does the greedy method give for 12, and is it the fewest?

Pick an answer to see why.

Dynamic programming: remembering answers

How do you find the fewest coins when greedy can’t be trusted? Think the way Grade 11 Unit 2 taught: find a smaller copy of the problem inside it.

To pay 6 with coins of 1, 3 and 4, the first coin is a 1, a 3 or a 4. After it, what is left is a smaller amount: 5, 3 or 2, and it must be paid with the fewest coins too. So

$\text{fewest}(6) = 1 + \text{the smallest of } \text{fewest}(5),\ \text{fewest}(3),\ \text{fewest}(2)$

and with nothing left to pay, 0 coins. That is a recursive function at once:

def fewest(amount, coins):    if amount == 0:        return 0    best = None    for coin in coins:        if coin <= amount:            n = fewest(amount - coin, coins) + 1            if best is None or n < best:                best = n    return best print(fewest(6, [1, 3, 4]))print(fewest(15, [1, 2, 5, 10, 20, 25]))

Output

It tries every first coin, so it can’t be fooled the way greedy is. But watch it work.

Step through fewest(6) with coins of 1, 3 and 4. Each circle is a call, with the amount left in it. Count how many times fewest(2) and fewest(1) are worked out.

Step 1 / 49

The program asks for the fewest coins that make 6, with coins of 1, 3 and 4. fewest(6) tries the coin of 1 first, which leaves 5: it calls fewest(5) and waits.

Calls made: 1
Open now: 1
Most open at once: 1

Open calls, newest on top

fewest(6)

gives back 2waiting for fewest(5)waiting for fewest(3)waiting for fewest(2)waiting for fewest(4)waiting for fewest(1)gives back 1waiting for fewest(0)gives back 0running

def fewest(amount, coins):    if amount == 0:        return 0    best = None    for coin in coins:        if coin <= amount:            n = fewest(amount - coin, coins) + 1            if best is None or n < best:                best = n    return best print(fewest(6, [1, 3, 4]))

Output

What you should see

This is the stairway of Grade 11’s Recursion again: a recursion whose branches ask the same questions over and over. For 15 rupees with six kinds of coin, the program above makes 4,535 calls. For 40 rupees it makes about three thousand million calls (3,024,604,418, counted by a program); it runs for many minutes on a fast computer, though there are only 41 different questions, fewest(0) to fewest(40).

Remember each answer

The fix is to remember. Keep a dictionary, known, from each amount to its answer. Before working an amount out, look it up; after working it out, write it down. Then every question is worked out once, and every later call is a lookup.

def fewest(amount, coins, known):    if amount == 0:        return 0    if amount in known:        return known[amount]    best = None    for coin in coins:        if coin <= amount:            n = fewest(amount - coin, coins, known) + 1            if best is None or n < best:                best = n    known[amount] = best    return best print(fewest(6, [1, 3, 4], {}))print(fewest(40, [1, 2, 5, 10, 20, 25], {}))print(fewest(99, [1, 2, 5, 10, 20, 25, 50, 100], {}))

Output

Two new lines, 4–5 and 12, and fewest(40) takes a moment instead of many minutes. (For a really big amount, the calls would go deeper than Python’s recursion limit, about 1,000; the table below has no such limit.)

The same fewest(6), now with known. Watch the calls that end at once because their answer is already written down.

Step 1 / 29

The same program with one change: a dictionary, known, in which each answer is written down once it is worked out. It starts empty. fewest(6) tries the coin of 1 first and calls fewest(5).

Calls made: 1
Open now: 1
Most open at once: 1

Open calls, newest on top

fewest(6)

gives back 2waiting for fewest(5)waiting for fewest(3)waiting for fewest(2)waiting for fewest(4)waiting for fewest(1)gives back 1waiting for fewest(0)gives back 0running

def fewest(amount, coins, known):    if amount == 0:        return 0    if amount in known:        return known[amount]    best = None    for coin in coins:        if coin <= amount:            n = fewest(amount - coin, coins, known) + 1            if best is None or n < best:                best = n    known[amount] = best    return best print(fewest(6, [1, 3, 4], {}))

Output

What you should see

Remembering the answers of a function so it never works the same one out twice is called memoization (from “memo”, a note to remember something by). Solving a problem by breaking it into smaller problems that overlap (the same small question is needed by many bigger ones), solving each small problem once, and building the answer from theirs, is called dynamic programming.

Working upwards: a table

There is a second way to do dynamic programming, with no recursion at all. Every answer needs only answers for smaller amounts. So work upwards: fill a list best, where best[a] is the fewest coins for amount a, starting from best[0] = 0, then 1, 2, 3… When you reach a, everything smaller is already in the list. A second list, last, remembers which coin gave each best answer, so you can read off the coins themselves, the way came_from gave the route.

def fewest_coins(amount, coins):    best = [0] + [None] * amount     # best[a]: fewest coins that make a    last = [None] * (amount + 1)     # last[a]: the coin that does it    for a in range(1, amount + 1):        for coin in coins:            if coin <= a and best[a - coin] is not None:                if best[a] is None or best[a - coin] + 1 < best[a]:                    best[a] = best[a - coin] + 1                    last[a] = coin    if best[amount] is None:        return None                  # it can't be made at all    given = []    a = amount    while a > 0:        given.append(last[a])        a = a - last[a]    return given print(fewest_coins(6, [1, 3, 4]))print(fewest_coins(40, [1, 2, 5, 10, 20, 25, 50, 100]))print(fewest_coins(1785, [1, 2, 5, 10, 20, 50, 100, 500, 1000]))print(fewest_coins(3, [2, 5]))

Output

[3, 3][20, 20][5, 10, 20, 50, 100, 100, 500, 1000]None

None in a list means “not worked out”, or here, “can’t be made”: 3 can’t be paid with coins of 2 and 5, and the function says so instead of crashing. For Rs 1,785 it does about 1,785 × 9 small steps, and it works for any set of coins.

Testing greedy against the best

Now you can evaluate the greedy method properly. You have a method known to be right, so let a program compare the two on every amount, and list where greedy gives more coins:

def greedy_change(amount, coins):    given = []    for coin in sorted(coins, reverse=True):        while amount >= coin:            given.append(coin)            amount = amount - coin    return given def fewest_coins(amount, coins):    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:                if best[a] is None or best[a - coin] + 1 < best[a]:                    best[a] = best[a - coin] + 1    return best[amount] def greedy_fails(coins, up_to):    fails = []    for amount in range(1, up_to + 1):        if len(greedy_change(amount, coins)) > fewest_coins(amount, coins):            fails.append(amount)    return fails print(greedy_fails([1, 2, 5, 10, 20, 50, 100, 500, 1000], 1000))print(greedy_fails([1, 2, 5, 10, 20, 25, 50, 100], 100))

Output

[][40, 41, 42, 43, 44, 90, 91, 92, 93, 94]

For Nepal’s values, no amount up to Rs 1,000 fails. (A program can’t test every amount there is, but mathematicians have shown that for any set of coins that includes a 1, if greedy never fails below the sum of the two largest values, it never fails at all. For Nepal’s values that means below 1,500, and the faster program in the next “Try it” checks exactly that far.) With a Rs 25 note added, it fails ten times in the first hundred, the red squares of the widget.

A story from computing

A name chosen to hide the mathematics

Richard Bellman, an American mathematician working for the RAND Corporation, developed dynamic programming in the early 1950s, for planning decisions made one stage after another. Years later, in his autobiography, he wrote that he chose the name to protect his work: the Secretary of Defense, Charles Wilson, whose department paid for RAND’s work, “had a pathological fear and hatred of the word research”, so Bellman wanted a name no one could object to. “Programming” then meant planning, as in a program of events, not writing code; and “dynamic”, he said, was a word impossible to use in a bad sense. The story can’t be quite true as he told it: Bellman’s first paper using the name came out in 1952, and Wilson only became Secretary of Defense in 1953. But the name stuck.

Which problem is a good fit for dynamic programming?

Pick an answer to see why.

How autocorrect measures the distance between words

You type “recieve” and your phone offers “receive”. To do that, it needs a measure of how different two words are: “receive” is very close to what you typed, “recipe” further, “banana” very far.

A good measure counts the fewest small changes that turn one word into the other. Allow three kinds of change, each costing 1:

insert a letter (“Pokhra” → “Pokhara”, insert a);
delete a letter (“bhat” → “bat”, delete h);
change one letter into another (“bat” → “cat”).

The fewest such edits that turn one word into another is their edit distance (also called the Levenshtein distance). “Pokhra” and “Pokhara” are 1 apart. “recieve” and “receive” are 2 apart: change the i to e and the e to i.

A table of smaller problems

How can a program find the fewest edits, among all the ways to edit? Look for smaller copies, as with coins. Compare the last letters of the two words.

If they are the same, keep it: the distance is the distance between the two words without their last letters.
If not, the last edit was one of three: delete the first word’s last letter, insert the second word’s last letter, or change one into the other. Each leaves a smaller pair of words, plus 1 edit. Take the smallest.

The smaller pairs are always beginnings of the two words, so the problems overlap heavily. Put them in a table: a row for each beginning of the first word (with the empty beginning first), a column for each beginning of the second. The cell in row i, column j holds the distance between the first i letters of one word and the first j letters of the other. Fill it row by row:

The first row and column count up 0, 1, 2…: turning nothing into j letters takes j inserts.
Every other cell is the smallest of: the cell above + 1 (delete), the cell to the left + 1 (insert), and the cell diagonally above-left + 0 if the two letters are the same or + 1 if not (keep or change).
The answer is in the bottom-right cell.

Type a word as it was typed and the word that was meant, or keep the example (English or Nepali, up to 8 characters). Press Next cell to fill the table one cell at a time, and read under it which three cells it came from; press Fill all to finish. The shaded path shows the edits, read from the top-left corner to the bottom-right.

Typed: Meant:

Cells worked out: 0 / 36
Edit distance: –

The first row and column are filled already: turning nothing into j letters takes j inserts, and i letters into nothing takes i deletes. Press Next cell.

What you should see

In Python

def edit_distance(a, b):    # d[i][j]: the fewest edits to turn the first i letters of a    # into the first j letters of b    d = []    for i in range(len(a) + 1):        d.append([0] * (len(b) + 1))    for i in range(len(a) + 1):        d[i][0] = i                      # delete all i letters    for j in range(len(b) + 1):        d[0][j] = j                      # insert all j letters    for i in range(1, len(a) + 1):        for j in range(1, len(b) + 1):            if a[i - 1] == b[j - 1]:                change = 0            else:                change = 1            d[i][j] = min(d[i - 1][j] + 1,           # delete a letter of a                          d[i][j - 1] + 1,           # insert a letter of b                          d[i - 1][j - 1] + change)  # keep it, or change it    return d[len(a)][len(b)] print(edit_distance("bhat", "bat"))print(edit_distance("recieve", "receive"))print(edit_distance("Pokhra", "Pokhara"))print(edit_distance("बिद्यालय", "विद्यालय"))print(len("विद्यालय"), list("विद्यालय"))print(edit_distance("kitten", "sitting"))

Output

12118 ['व', 'ि', 'द', '्', 'य', 'ा', 'ल', 'य']3

The table is a list of lists (Grade 9’s nested lists): d[i][j] is row i, column j. For two words of 8 letters, it fills 9 × 9 = 81 cells, each from three others: the work grows with the length of one word times the length of the other, however many ways there are to edit.

Look at the Nepali line. A common slip, बिद्यालय for विद्यालय, is 1 edit, because Python sees Nepali text as Unicode characters (Grade 9), and to Python a vowel sign like ि and the halant ् are characters of their own: विद्यालय is 8 characters, though it looks like four letters joined together. So the same program measures Nepali words with no change. Whether that is the best measure for Nepali is a fair question: a mistake in a vowel sign (ि for ी) and a whole wrong letter (ब for व) both count 1.

A spell-checker

A spell-checker keeps a list of correct words. For a word not in the list, it suggests the words closest to it:

def edit_distance(a, b):    d = []    for i in range(len(a) + 1):        d.append([0] * (len(b) + 1))    for i in range(len(a) + 1):        d[i][0] = i    for j in range(len(b) + 1):        d[0][j] = j    for i in range(1, len(a) + 1):        for j in range(1, len(b) + 1):            change = 0 if a[i - 1] == b[j - 1] else 1            d[i][j] = min(d[i - 1][j] + 1, d[i][j - 1] + 1, d[i - 1][j - 1] + change)    return d[len(a)][len(b)] def suggest(word, words, most=2):    found = []    for w in words:        dist = edit_distance(word, w)        if dist <= most:            found.append((dist, w))    found.sort()    return [w for dist, w in found] english = ["the", "they", "then", "there", "their", "three", "tree", "free", "receive", "believe", "friend", "fried"]nepali = ["विद्यालय", "विद्यार्थी", "पुस्तक", "शिक्षक", "कक्षा", "परीक्षा", "गणित", "विज्ञान"] print(suggest("teh", english))print(suggest("freind", english))print(suggest("recieve", english))print(suggest("परिक्षा", nepali))print(suggest("सिक्षक", nepali))print(suggest("बिद्यार्थि", nepali))

Output

['the', 'then', 'they', 'tree']['fried', 'friend']['believe', 'receive']['परीक्षा']['शिक्षक']['विद्यार्थी']

change = 0 if … else 1 is Python’s short way to write the four-line if of the program before. found.sort() sorts the pairs by distance first, then alphabetically. The Nepali suggestions are all right: परिक्षा for परीक्षा and सिक्षक for शिक्षक are common slips.

Now evaluate it as a user would. “teh” gives “the” first: good. But “freind” gives “fried” before “friend”, and “recieve” gives “believe” first, since both are 2 edits away and b comes before r. Distance alone isn’t enough. Two improvements, each a small change to the design:

Count swapping two letters next to each other as one edit, not two (the most common typing slip). Then “freind” and “recieve” are each 1 edit from the right word. (This measure is called the Damerau–Levenshtein distance, after Frederick Damerau, who counted typing errors in 1964.)
Among words at the same distance, prefer the more common word: keep the list with how often each word is used, and sort by that second.

In the edit-distance table, a cell is filled from the cell above, the cell to the left and the cell diagonally above-left. Why does that work?

Pick an answer to see why.

A trek through 20 villages

Back to the health worker. Her base village and 19 others must all be visited, each once, before she returns to base, and she wants to walk as little as possible. This is the traveling salesperson problem: given some places and the distance between every two of them, find the shortest round trip that visits each place exactly once. (It was first called the traveling salesman problem; the name comes from the salesmen who traveled from town to town.) A delivery van with thirty parcels, a school bus picking up children, a robot drilling holes in a circuit board: all face it.

Try every route?

The obvious method: list every possible order, add up each one’s length, keep the shortest. It is certainly right. How long does it take?

From the base there are 19 villages to go to first, then 18 for the second, 17 for the third, down to 1: 19 × 18 × 17 × … × 1 orders, which is written 19! (“19 factorial”, Grade 11’s Recursion worked it out). Each round trip is counted twice, once each way round, so there are 19! ÷ 2 different round trips.

import math def how_long(seconds):    if seconds < 1:        return "under a second"    if seconds < 60 * 60:        return f"{seconds:,.0f} seconds"    days = seconds / (60 * 60 * 24)    if days < 365:        return f"{days:,.0f} days"    return f"{days / 365:,.0f} years" for villages in [5, 10, 15, 20, 25]:    treks = math.factorial(villages - 1) // 2    seconds = treks / 1_000_000_000      # a billion treks a second    print(f"{villages} villages: {treks:,} round trips, {how_long(seconds)}")

Output

5 villages: 12 round trips, under a second10 villages: 181,440 round trips, under a second15 villages: 43,589,145,600 round trips, 44 seconds20 villages: 60,822,550,204,416,000 round trips, 2 years25 villages: 310,224,200,866,619,719,680,000 round trips, 9,837,145 years

Even on a computer that checked a billion round trips every second, 20 villages would take about two years, and 25 villages nearly ten million years. Each village more multiplies the work: the 21st multiplies it by 20. A computer a thousand times faster only buys you about two more villages.

No fast method is known

Surely someone has found a cleverer way? Cleverer ways exist. Dynamic programming, for one, cuts 20 villages down to a few hundred million steps, and specialists’ programs have found the best round trip through tens of thousands of places. But every method known that is sure to find the best round trip for every map can, on some maps, take work that grows explosively, roughly doubling or worse with each place added. Nobody has found a method that is always fast, and nobody has proved that none exists. This is one of the most famous open questions in mathematics; the next unit, The Limits of Computing, explains what “fast” means exactly and why a million-dollar prize waits for the answer.

Good enough: heuristics

A health worker can’t wait for a proof. So people do what A* did with its estimate: use a heuristic, a quick rule that usually gives a good answer, though not always the best. Two simple ones:

Nearest next: from where you are, walk to the nearest village not yet visited; when all are visited, go home. This is greedy, and fast: for 20 villages, a few hundred distances to compare.
Uncross: in the best round trip, the path never crosses itself. If two legs cross, joining their ends the other way makes the trip shorter, because the two diagonals of a four-sided field are together longer than two of its opposite sides. So look at every pair of legs, and wherever reversing the stretch between them makes the trip shorter, reverse it. Repeat until no reversal helps. (This is called 2-opt.)

The base is the square. Tap the villages in the order you would visit them; the trek goes back to base by itself at the end. Then press Nearest next to see the greedy route, and Uncross to improve whichever route is drawn. With 9 villages (the base and 8 others), Try every route finds the best of all 20,160 round trips. Then switch to 20 villages (the base and 19 others), where nobody can try them all.

Map:

This trek: –
Best: –
Round trips: 20,160

Tap the villages in the order you would visit them, starting from the base, or press Nearest next.

What you should see

How good is good enough?

A heuristic gives no guarantee. So measure it: on small maps, where trying every route is possible, compare its answer with the best, on many maps, and look at the average and the worst. Here is that experiment, on 50 random maps of 7 villages and a base:

import itertools, math, random def length(trek, spots):    total = 0    for i in range(len(trek) - 1):        total = total + math.dist(spots[trek[i]], spots[trek[i + 1]])    return total def try_every_route(spots):    best = None    for order in itertools.permutations(range(1, len(spots))):        trek = [0] + list(order) + [0]        if best is None or length(trek, spots) < length(best, spots):            best = trek    return best def nearest_next(spots):    trek = [0]    left = list(range(1, len(spots)))    while len(left) > 0:        here = spots[trek[-1]]        nxt = min(left, key=lambda v: math.dist(here, spots[v]))        trek.append(nxt)        left.remove(nxt)    return trek + [0] def uncross(trek, spots):    better = True    while better:        better = False        for i in range(1, len(trek) - 2):            for j in range(i + 1, len(trek) - 1):                new = trek[:i] + trek[i:j + 1][::-1] + trek[j + 1:]                if length(new, spots) < length(trek, spots) - 1e-9:                    trek = new                    better = True    return trek random.seed(1)maps = 50nearest_extra = []uncross_extra = []for m in range(maps):    spots = [(random.uniform(0, 20), random.uniform(0, 20)) for v in range(8)]    best = length(try_every_route(spots), spots)    nn = nearest_next(spots)    nearest_extra.append(length(nn, spots) / best - 1)    uncross_extra.append(length(uncross(nn, spots), spots) / best - 1) print("Maps of 7 villages and a base:", maps)print(f"Nearest next:   on average {100 * sum(nearest_extra) / maps:.1f}% longer than the best; at worst {100 * max(nearest_extra):.1f}%")print(f"Then uncrossed: on average {100 * sum(uncross_extra) / maps:.1f}% longer than the best; at worst {100 * max(uncross_extra):.1f}%")print("Uncrossing found the best round trip on", sum(1 for e in uncross_extra if e < 1e-9), "maps of", maps)

Output

Maps of 7 villages and a base: 50Nearest next:   on average 9.5% longer than the best; at worst 28.7%Then uncrossed: on average 0.4% longer than the best; at worst 6.0%Uncrossing found the best round trip on 38 maps of 50

A few new pieces of Python: each village is a pair of numbers, its position on the map, in the list spots, and the base is number 0; math.dist gives the straight-line distance between two positions; itertools.permutations gives every order of the villages, one at a time; lambda v: math.dist(here, spots[v]) is a small function written in one line, which min uses to compare the villages by their distance from here (like key=mutual.get in Grade 10); and trek[i:j + 1][::-1] is the stretch from leg i to leg j, reversed. random.seed(1) makes the “random” maps the same at every run, so you get exactly these numbers; change it, and the experiment runs on 50 other maps.

The result is the kind of evidence you can act on: nearest next alone is about 10% worse than the best on average, and can be nearly 30% worse; uncrossing after it is usually within a fraction of a percent. On 8 places this was easy to check. It says nothing certain about 20 villages, but it is a good reason to expect a good trek.

Today · checked October 2026

The biggest round trips ever solved

In 1954 George Dantzig, Ray Fulkerson and Selmer Johnson found, and proved, the shortest round trip through 49 cities of the United States, one in each of the 48 states of the time and Washington, DC. They worked it out on 42 of the cities, mostly by hand: the other seven lie on the road from Washington to Boston, and the best round trip through the 42 turned out to use that road, so it passed through all seven. In 2004 David Applegate, Robert Bixby, Vašek Chvátal, William Cook and Keld Helsgaun proved the shortest tour through all 24,978 towns and villages of Sweden, and in 2006 one through 85,900 points of a computer chip, still the largest solved, using a program called Concorde and years of computer time. Their method is clever, but it is still not sure to be fast on every map. Bill Cook’s pages at the University of Waterloo keep the records.

A delivery company plans routes for 40 stops a day with “nearest next, then uncross”. Which is the honest description of its routes?

Pick an answer to see why.

Designing an algorithm

You have now met four families of algorithms, and a professional facing a new problem asks which family it belongs to:

Family	The idea	In this unit	Sure to give the best?
Graph search	visit places in a chosen order, remembering what was found	Dijkstra’s algorithm, A*	yes, with no negative weights (and, for A*, an estimate never too high)
Greedy	take the best-looking step now, never go back	change from Nepal’s notes; booking the hall	only when there is a reason it can’t go wrong
Dynamic programming	solve overlapping smaller problems once each, and remember them	fewest coins, edit distance	yes
Heuristic	a quick rule that is usually good	nearest next, uncrossing	no: measure it

A way to work:

Model the problem. What are the things and the links between them? A graph? Amounts? Two words? What exactly is “best”: shortest, fewest, cheapest?
Choose the data structures by the operations the algorithm needs most: a dictionary of dictionaries for neighbors, a heap for “nearest next”, a table for smaller answers.
Find the family. Is there a smaller copy inside? Do the smaller problems overlap? Can a greedy step be proved safe? Does every known method blow up as the problem grows?
Write it clearly, with functions for the parts, so a change (an estimate, a measure of distance) is one parameter, not a new program.
Evaluate it: on cases you can check by hand (the start is the goal, nothing reachable, a tie, an amount that can’t be made); against a slower method known to be right, on many cases; and by measuring its work as the problem grows.

Project: algorithms at work

Choose one, or both. Each can be done on this page, even on a phone (press Edit under any program, change it and press Run); for a bigger map or word list, a computer is easier.

Project

Shortest routes on Nepal’s highways

Grow the map. Add at least five towns and their roads to highways.csv: for example Ilam, Biratnagar, Itahari, Dharan, Janakpur, Nepalgunj, Dhangadhi, Mahendranagar, Jumla. Find each road’s length from a map app or a printed road map, and write where it came from.
Find routes. Use find_route with no_estimate to answer three questions you care about, such as the shortest way from your district to Kathmandu, or to a relative’s town.
Test it. Check each answer by hand or against a map app. Try a town that isn’t on your map, and the start equal to the goal.
Close a road. A landslide closes one road on the route. Remove it from the graph (Grade 10’s remove_road, written for dictionaries of dictionaries) and find the new route. How much longer is it?
Measure. Write straight-line estimates for one goal (a map app or an atlas gives the straight-line distance between two places; round them down). Compare the towns visited by Dijkstra’s algorithm and A* for five starts.
Write it up, honestly: where your distances came from, what your map leaves out, and one case where the program’s “shortest route” isn’t the one a bus driver would take, and why.

Answer

Project

A spell-checker for Nepali or English

Make a word list: 100 or more correct words, from your textbooks’ word lists or a dictionary, in English or in Nepali (Unicode, not Preeti).
Collect real mistakes. Ask ten classmates to type 20 words each, quickly, without checking. Keep every misspelling, with the word that was meant.
Test suggest on every mistake. How often is the right word first? In the first three? Write it as a percentage.
Improve it, one change at a time, and measure again after each: count a swap of two neighboring letters as one edit; prefer more common words (give each word in your list a count of how often it appears in a page of your textbook); for Nepali, try counting a change between two vowel signs (ि and ी) as half an edit.
Report which change helped most, with the numbers before and after, and one kind of mistake your checker still can’t fix.

Answer

In short

A weighted graph has a number, a weight, on each edge: a length, a time, a fare. Store it as a dictionary of dictionaries (roads[a][b] is the road’s length), a weighted adjacency list, or as a table, an adjacency matrix.
Dijkstra’s algorithm visits places nearest first by distance from the start. Reaching a place gives a distance that may still go down (relaxing a road); it is final only when the place is taken as the nearest. It needs no negative weights. A priority queue (a heap, heapq) gives the nearest waiting place quickly.
A* visits the place with the smallest distance so far + an estimate of the distance left (a heuristic, such as the straight line). It finds the shortest route with fewer visits, as long as the estimate is never too high. Dijkstra’s algorithm is A* with an estimate of 0.
A greedy algorithm takes the best-looking step now and never goes back. It is fast, and right only when there is a reason: Nepal’s notes, Dijkstra’s algorithm, booking a hall. With other coins (1, 3, 4, or a Rs 25 note) it fails.
Dynamic programming solves a problem from smaller problems that overlap, each solved once: by remembering answers (memoization) or by filling a table upwards. It finds the fewest coins for any set of coins.
The edit distance between two words is the fewest inserts, deletes and changes that turn one into the other, found by filling a table, each cell from three others. Spell-checkers and autocorrect start from it.
The traveling salesperson problem (the shortest round trip through every place) has no known method that is always fast: trying every order of 20 villages means 19! ÷ 2 round trips. Heuristics such as nearest next and uncrossing (2-opt) give good answers quickly; measure them against the best on small cases, and never call their answers the best.
Design an algorithm by modeling the problem, choosing data structures by the operations needed, finding its family, writing it with clear functions, and evaluating it with test cases, against a method known to be right, and by measuring its work.

Exercise

Which is a weighted graph?

Pick an answer to see why.

Dijkstra’s algorithm has visited Kathmandu (0) and Dhulikhel (30). Mugling is waiting at 110 and Hetauda at 130. Which is certain?

Pick an answer to see why.

A* with the straight-line estimate is usually faster than Dijkstra’s algorithm because:

Pick an answer to see why.

Coins are 1, 5 and 12. Greedy pays 15 as 12 + 1 + 1 + 1. What is the fewest?

Pick an answer to see why.

What is the edit distance between “bhat” and “bhaat”?

Pick an answer to see why.

A program tries every order of 12 places to find the shortest round trip, and takes 1 second. Roughly how long would 14 places take?

Pick an answer to see why.

a.

Write the weighted graph below as a Python dictionary of dictionaries, and as a table. Roads: Biratnagar–Itahari 25 km, Itahari–Dharan 15 km, Itahari–Inaruwa 15 km, Inaruwa–Biratnagar 30 km. (The lengths are rounded; check them on a map for your project.)

Answer

b.

Use Dijkstra’s algorithm by hand to find the shortest route from Pokhara to Hetauda on this unit’s highways. Write a row for each visit, as in the worked example.

Answer

c.

Explain, in your own words, why Dijkstra’s algorithm may stop when the goal is taken from the waiting list, but not when the goal is first reached. Use Tansen as an example.

Answer

d.

What does it mean for an A* estimate to be “never too high”? Explain why straight-line distance is never too high for road journeys, and what can go wrong with an estimate that is sometimes too high.

Answer

e.

A shop sells frozen momo to take home in packs of 3, 5 and 10. A family wants exactly 16 momo, in as few packs as possible.

i.What does the greedy method (biggest pack first) do?
ii.Fill in a dynamic-programming table for 0 to 16 momo, and give the fewest packs.

Answer

f.

The recursive fewest without known is correct but slow, and with known it is fast. Explain why, using the words “overlapping” and “memoization”.

Answer

g.

Fill in the edit-distance table for “chai” (rows) and “chiya” (columns), and give the distance. What edits does it stand for?

Answer

h.

A friend’s spell-checker suggests “fried” for “freind”. Give two reasons why, and two improvements.

Answer

i.

A health worker must visit 9 villages and return to base. (i) How many different round trips are there? (ii) Describe the nearest-next heuristic, and draw (or describe) a map of a few villages where it gives a bad route. (iii) How would you find out how good “nearest next, then uncross” is?

Answer

j.

For each problem, say which kind of algorithm you would use first (graph search, greedy, dynamic programming or a heuristic) and why. (i) The fastest walk between two classrooms in a big school, each corridor with its walking time. (ii) The order in which a mobile library van visits 25 schools in a day. (iii) How many ways a 10-meter path can be paved with slabs 1 m and 2 m long. (iv) Booking the most matches on the school’s one cricket ground, each match with its own start and end time.

Answer

Worksheet to print (PDF, 5 pages) Answer key for teachers

Quiz yourself: Algorithms and programming, Grades 6–12 →

Practice every question in the book, and keep track of the ones you miss →