Exam practice
Every question from the end of every unit, with hints and answers to open. After you check an answer, mark how you did, and come back to the ones you didn’t get.
10 questions
Unit 1 · Algorithms for Hard Problems
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
roads = { "Biratnagar": {"Itahari": 25, "Inaruwa": 30}, "Itahari": {"Biratnagar": 25, "Dharan": 15, "Inaruwa": 15}, "Dharan": {"Itahari": 15}, "Inaruwa": {"Itahari": 15, "Biratnagar": 30},}| Biratnagar | Itahari | Dharan | Inaruwa | |
|---|---|---|---|---|
| Biratnagar | 0 | 25 | – | 30 |
| Itahari | 25 | 0 | 15 | 15 |
| Dharan | – | 15 | 0 | – |
| Inaruwa | 30 | 15 | – | 0 |
Each road appears twice in each form, once from each end.
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
| Visit | Its distance | What changes | Waiting, nearest first |
|---|---|---|---|
| Pokhara | 0 | Mugling 90, Tansen 120: new | Mugling 90, Tansen 120 |
| Mugling | 90 | Kathmandu 200, Bharatpur 125: new | Tansen 120, Bharatpur 125, Kathmandu 200 |
| Tansen | 120 | Butwal 160: new | Bharatpur 125, Butwal 160, Kathmandu 200 |
| Bharatpur | 125 | Hetauda 200: new. Butwal 245: not shorter than 160 | Butwal 160, Hetauda 200, Kathmandu 200 |
| Butwal | 160 | nothing new (Bharatpur and Tansen done) | Hetauda 200, Kathmandu 200 |
| Hetauda | 200 | the goal: stop |
Hetauda came from Bharatpur, Bharatpur from Mugling, Mugling from Pokhara: Pokhara → Mugling → Bharatpur → Hetauda, 200 km. (Kathmandu is also 200 away; ties may be taken in either order. The program, comparing names, takes Hetauda first.)
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
When the goal is first reached, the distance written for it comes from one way there, and a shorter way may still be found through a town that hasn’t been visited yet. Tansen was first reached through Pokhara at 320 km; later, visiting Butwal (265 km) found a way of 305 km. When the goal is taken from the waiting list it is the nearest waiting place, and any other way to it would have to pass through some waiting place that is already at least as far, then add more road (no road is negative). So its distance can’t go down any more, and the search can stop.
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
The estimate for any place must be no more than the real shortest distance from that place to the goal. The straight line is the shortest possible path between two points, and any road between them is at least that long, so the straight-line distance can never be more than the road distance. If an estimate is sometimes too high, places on the real shortest route can look worse than they are, and the search may reach the goal along a longer route and stop before trying them: on this unit’s map, three times the straight line led to 320 km through Pokhara instead of 305 km through Butwal.
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
i. Greedy takes a pack of 10 (leaving 6), then a pack of 5 (leaving 1), and then no pack fits the last momo: greedy fails to find any answer, though 16 can be bought.
ii. best[a] for a = 0 to 16, trying packs of 3, 5 and 10 (– means it can’t be made):
| a | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| best | 0 | – | – | 1 | – | 1 | 2 | – | 2 | 3 | 1 | 3 | 4 | 2 | 4 | 2 | 3 |
best[16] = 3: taking a 3 leaves 13, whose best is 2 (a 10 and a 3), so 16 = 10 + 3 + 3, three packs. (Taking the 10 first leaves 6 = 3 + 3: the same three packs. Taking a 5 first leaves 11, which needs 3 more: four in all.)
The recursive fewest without known is correct but slow, and with known it is fast. Explain why, using the words “overlapping” and “memoization”.
Answer
To work out fewest(a), the function needs fewest of several smaller amounts, and each of those needs fewest of smaller amounts still. The smaller problems overlap: fewest(2) is needed by fewest(3), fewest(4), fewest(5) and fewest(6). Without known, each need is worked out again from the start, with all its calls, so the number of calls grows explosively (24 calls for 6, about three thousand million for 40). With memoization, each answer is written in known the first time it is worked out and looked up every later time, so each amount is worked out once and the calls stay few (14 for 6).
Fill in the edit-distance table for “chai” (rows) and “chiya” (columns), and give the distance. What edits does it stand for?
Answer
| c | h | i | y | a | ||
|---|---|---|---|---|---|---|
| 0 | 1 | 2 | 3 | 4 | 5 | |
| c | 1 | 0 | 1 | 2 | 3 | 4 |
| h | 2 | 1 | 0 | 1 | 2 | 3 |
| a | 3 | 2 | 1 | 1 | 2 | 2 |
| i | 4 | 3 | 2 | 1 | 2 | 3 |
The distance is 3. One way: keep c and h, insert i, change a to y, change i to a (“chai” → “chiai” → “chiyi” → “chiya”). Another: keep c and h, delete a, keep i, insert y and a. Both use three edits.
A friend’s spell-checker suggests “fried” for “freind”. Give two reasons why, and two improvements.
Answer
Reasons: in plain edit distance a swap of two letters (“ei” for “ie”) counts as two edits, so “friend” is 2 away, the same as “fried” (delete the first e, change the n to e); and among words at the same distance the checker sorts alphabetically, and “fried” comes before “friend”.
Improvements: count swapping two neighboring letters as one edit (then “friend” is 1 away and comes first), and among words at the same distance prefer the one used more often, from word counts.
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
(i) With the base fixed, 9 villages can be visited in 9! = 362,880 orders, each round trip counted twice (once each way): 181,440 round trips.
(ii) From the base, go to the nearest unvisited village; from there, to the nearest unvisited one; and so on; when all are visited, go back to base. It does badly on a map like this: most villages close together on one side of the base, and one village far off in another direction. Nearest next works through the cluster, ends at its far side, and only then makes the long walk to the far village and the long walk home, often crossing its own path; visiting the far village on the way out or the way back would be shorter. A long walk at the end is the typical mark of a greedy route.
(iii) Measure it on many small maps where the best round trip can be found by trying every order: run the heuristic and the exhaustive search on each, and record how much longer the heuristic’s round trip is, in percent, on average and at worst. (On 50 random maps of 7 villages and a base, the unit’s program found 0.4% on average and 6% at worst.)
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
- i.Graph search, Dijkstra’s algorithm (or A* with the straight-line distance as the estimate): rooms are nodes, corridors weighted edges with times, never negative.
- ii.A heuristic: it is a traveling-salesperson problem with 26 places, with no known fast method; nearest next then uncrossing gives a good order, to be described as good, not best.
- iii.Dynamic programming: the ways for n m are the ways for n − 1 (a 1 m slab first) plus the ways for n − 2 (a 2 m slab first), overlapping smaller problems, the stairway of Grade 11; work upwards from 0 and 1: 89 ways for 10 m.
- iv.Greedy: always book the match that finishes earliest among those that start after the last one booked; finishing earliest leaves the most time for the rest, so this always fits the most matches.