Final Exam Model Paper 10

• i.Any program that stops after more than an hour: a long calculation, or one that waits for an hour and a minute. His halts says False, but it would have stopped.
• ii.If halts(contrary, contrary) says True, contrary loops for ever, so it doesn’t stop; if it says False, contrary stops at once. Either answer is made wrong by contrary itself, and contrary can be written from any halts in a few lines. So no program decides, for every program and input, whether it stops: the halting problem is undecidable.
• iii.Three answers instead of two: “it stops”, “it doesn’t stop”, or “I can’t tell”. Such checkers are useful, and often right; what none can do is never say “I can’t tell”.

• i.With Rs 800: age 3 → 0 (normal); 4 → 0 and 5 → 400 (the boundary at 5); 11 → 400 and 12 → 800 (the boundary at 12); 59 → 800 and 60 → 400 (the boundary at 60).
• ii.Ages 3 and 4 give 400.0, not 0: age < 12 is checked first and is true for every child, so age < 5 is never reached. And every half fare is a float, 400.0, not a whole number of rupees (Rs 755 would give 377.5). The others give the right amount.
• iii.Check the smallest group first, and use whole-number division:

def fare(full, age):    """The fare in rupees: free under 5, half from 5 to 11, half from 60 on, full otherwise."""    if age < 5:        return 0    elif age < 12:        return full // 2    elif age >= 60:        return full // 2    return full  tests = [    ((800, 3), 0),      # normal: a small child    ((800, 4), 0),      # boundary: the oldest free age    ((800, 5), 400),    # boundary: the youngest half fare    ((800, 11), 400),   # boundary: the oldest half fare for children    ((800, 12), 800),   # boundary: the youngest full fare    ((800, 59), 800),   # boundary: the oldest full fare    ((800, 60), 400),   # boundary: the youngest half fare for elders]for args, want in tests:    got = fare(*args)    print("ok  " if got == want else "FAIL", args, "gave", got, "wanted", want)

ok   (800, 3) gave 0 wanted 0ok   (800, 4) gave 0 wanted 0ok   (800, 5) gave 400 wanted 400ok   (800, 11) gave 400 wanted 400ok   (800, 12) gave 800 wanted 800ok   (800, 59) gave 800 wanted 800ok   (800, 60) gave 400 wanted 400

(A company might round a half fare of an odd amount up instead; the requirement should say which.)

• i.A bug against the requirement: thank the reviewer, add a test for a booking ending on the day another starts, fix the comparison so the test passes, and reply that it is fixed.
• ii.A matter of taste, but a clear name helps every reader: rename it (it costs little), or explain briefly why n is clear enough there. Either way, answer it.
• iii.This comment is about the person, not the code, and doesn’t help. Don’t take it personally or answer in the same tone: ask calmly which part of the code they mean and what they would change, so the review can go back to the code.

• i.The change went to every server at once, so nothing was left working as before; and the payment service retried at once, again and again, so the retries multiplied the load on the servers that were still working: a cascading failure.
• ii.Any three: a staged rollout (a few servers first, watched, then more); cells, so a bad change reaches only some users; exponential backoff with jitter for the retries; a circuit breaker that stops calling after too many failures; a quick way to undo every change.
• iii.It is blameless: it asks how the system let one mistake do so much harm, not whom to punish. If people are blamed, they hide mistakes, and the weaknesses stay; here the fix is in the system (staged rollouts, backoff), so the same mistake can’t do the same harm again.

• i.Farmers without a smartphone or mobile data, who can’t read well or type, who don’t know the app, or who farm where the signal is weak: often the poorest, the oldest, many women farmers, and remote districts.
• ii.Districts where farmers are online would look like they have the most disease and get the most help, while a disease spreading where few use the app would go unseen: help goes to those who already have the most.
• iii.Add data that doesn’t depend on the app: reports from the extension workers and agriculture offices, a random sample of farms visited in every district, and phone calls (not only typing) or local-language voice questions; and compare questions per farmer using the app, not raw counts.

The data shows the two go together; it doesn’t show that towers cause better results. Districts with more towers tend to be more urban, richer and easier to reach, with more schools, teachers, roads and electricity, and families who can pay for tuition: these confounders could raise pass rates and bring towers at the same time. Better results might even bring towers (richer districts attract companies). Phones and the internet might help students a little, but this data can’t say how much.
To find out whether better phone access raises results, the government would need a randomized comparison, such as giving internet access to schools chosen by chance and comparing their results with others, or at least comparing districts alike in wealth and roads. A recommendation to build towers “to improve education” goes beyond the evidence; towers may be worth building for other reasons.

• i.L = 11: 77 mod 26 = 25, Z. A = 0: 0, A. K = 10: 70 mod 26 = 18, S. E = 4: 28 mod 26 = 2, C. LAKE becomes ZASC.
• ii.7 × 15 = 105 = 4 × 26 + 1, so 15 is the inverse of 7, mod 26. X = 23: 345 mod 26 = 7, H; E = 4: 60 mod 26 = 8, I; G = 6: 90 mod 26 = 12, M; A = 0: A; Z = 25: 375 mod 26 = 11, L. XEGAZ is HIMAL.
• iii.13 shares a factor (13) with 26, so it has no inverse: different letters encrypt to the same one (B = 1 and D = 3 both become 13, N, since 39 mod 26 = 13), and N could not be decrypted.

• Official documentation, written by a tool’s makers, usually has a tutorial (to start), a reference (every function, exactly), how-to guides (recipes for common jobs), and release notes or a changelog (what changed in each version, including what breaks).
• Ways to keep learning, any two: build something slightly too hard for you; read other people’s code, such as open-source projects; explain what you learned (a note, a help answer); use AI as a tutor, not a substitute, checking it against the documentation; join others in a club, a meetup or an online community.

i. From the start (0), it can reach up to 120 km: the farthest station within reach is S3 (110). From S3 it can reach 230: the farthest is S5 (200). From S5 it can reach 320, past the end (290). So it stops at S3 and S5: 2 stops.

ii. With no stops, 290 km is more than 120. With one stop at a station s, the bus needs s ≤ 120 to get there and 290 − s ≤ 120, so s ≥ 170, to finish. No station is both at most 120 and at least 170 km from the start, so one stop is impossible: 2 is the fewest.

iii. Compare the greedy plan with any other plan, stop by stop. The greedy first stop is the farthest the bus can reach, so it is at least as far along as the other plan’s first stop. From a stop at least as far along, the bus can reach at least as far, so the greedy second stop is at least as far along as the other’s second, and so on. The greedy plan is never behind, so whenever the other plan can reach the end after some number of stops, the greedy one can too. Choosing the farthest station can’t spoil anything that comes after.

iv. Stopping at the farthest station might mean charging at an expensive one, when a cheaper one a little earlier, or an extra stop at a cheap one, would cost less. The reason in iii was about the number of stops, not the price, so it no longer holds. Use dynamic programming (the cheapest way to reach each station is the cheapest, over every station within 120 km before it, of reaching that station plus its price), or think of the stations as places in a weighted graph, with a road wherever one station can reach another, and use Dijkstra’s algorithm to find the cheapest way to the end.

i. Ward A: 20 ÷ 400 = 5% of searches found goods; Ward B: 4 ÷ 50 = 8%. Searches in Ward B found goods more often, not less. Ward A has more finds only because it had 8 times as many searches: it was near the post. The model learned where the rangers searched, not where wildlife crime happens: the past decisions are in the data. Following it sends even more searches to Ward A, which finds more there, which makes the next model rank Ward A higher still: a feedback loop that confirms itself, while Ward B, perhaps the bigger problem, goes unwatched.

ii. Ward A’s households: searched again and again, though 95% of searches there find nothing: 380 innocent households in the past five years, an intrusion into their homes and privacy and a loss of dignity, and a feeling of being treated as suspects for living near the road. The park and its wildlife: conservation depends on buffer-zone communities’ cooperation (they report poachers and fires); unfair searches lose their trust, and real poachers elsewhere are missed.

iii. One well-argued case: Not as it is.

• Get data that isn’t shaped by past searches: a small number of searches spread at random across all wards for a time, together with other evidence (informants’ reports, camera traps, seized goods traced back), so that the rate of crime in each ward can be compared fairly.
• Measure by ward: the share of searches that find something, in each ward, before and after any change.
• Keep people deciding: a model may suggest, but a ranger’s officer decides each search, records the reason, and the households have a way to complain.
• Involve the community: tell the buffer-zone committees what is used and why; an impact assessment and an entry in a public register before it is used, checks every year for the feedback loop, and a way to stop.

A route into a square comes either from the square to the north or from the one to the west, so the number of routes to a square is the sum of the numbers for those two (and 0 on a rock). Filling the table row by row works each square out once.

import random ORCHARD = [    "....#.",    ".#....",    "...#..",    "#.....",    "..#...",]   # . an open square, # a rock  def count_routes(grid):    """How many routes go from the top-left square to the bottom-right one, moving only east or south."""    rows, cols = len(grid), len(grid[0])    ways = [[0] * cols for r in range(rows)]    for r in range(rows):        for c in range(cols):            if grid[r][c] == "#":                ways[r][c] = 0            elif r == 0 and c == 0:                ways[r][c] = 1            else:                from_north = ways[r - 1][c] if r > 0 else 0                from_west = ways[r][c - 1] if c > 0 else 0                ways[r][c] = from_north + from_west    return ways[rows - 1][cols - 1]  def try_every(grid, r=0, c=0):    """Count the routes by following every one of them."""    if r == len(grid) or c == len(grid[0]) or grid[r][c] == "#":        return 0    if r == len(grid) - 1 and c == len(grid[0]) - 1:        return 1    return try_every(grid, r + 1, c) + try_every(grid, r, c + 1)  def test_one_square():    assert count_routes(["."]) == 1  def test_open_two_by_two():    assert count_routes(["..", ".."]) == 2  def test_rock_at_the_start():    assert count_routes(["#.", ".."]) == 0  def test_worked_by_hand():    # by hand: the rock in the middle leaves only the two routes round the edge    assert count_routes(["...", ".#.", "..."]) == 2  def test_same_as_following_every_route():    random.seed(1)    for trial in range(200):        rows, cols = random.randint(1, 6), random.randint(1, 6)        grid = ["".join(random.choice("...#") for c in range(cols)) for r in range(rows)]        assert count_routes(grid) == try_every(grid), grid  passed = failed = 0for name, test in list(globals().items()):    if name.startswith("test_"):        try:            test()            print("PASS", name)            passed += 1        except AssertionError as problem:            print("FAIL", name, problem)            failed += 1print(passed, "passed,", failed, "failed") print("Routes through the orchard:", count_routes(ORCHARD))print("Without the rocks:", count_routes(["......"] * 5))

PASS test_one_squarePASS test_open_two_by_twoPASS test_rock_at_the_startPASS test_worked_by_handPASS test_same_as_following_every_route5 passed, 0 failedRoutes through the orchard: 17Without the rocks: 126

The first run:

PASS test_two_halvesPASS test_too_littleFAIL test_ten_small_scoops gave FalseFAIL test_three_scoops gave False2 passed, 2 failed

Line 6 compares two floats with ==. A computer stores numbers in binary, and 0.1, 0.2 and 0.7 can’t be written exactly in binary (as one third can’t be written exactly in decimals), so each is stored as the nearest binary fraction. Adding them, the tiny errors add up: ten scoops of 0.1 make 0.9999999999999999, which is not equal to 1.0. 0.5 and 0.25 are exact in binary, which is why the two tests that passed did. The tests match the requirement, so the code is wrong: compare with a small tolerance (or count in whole grams).

import math  def packet_full(scoops):    """True when the scoops of tea, in kg, make exactly 1 kg."""    total = 0    for scoop in scoops:        total = total + scoop    return math.isclose(total, 1.0)  def test_two_halves():    assert packet_full([0.5, 0.5]) is True  def test_too_little():    assert packet_full([0.5, 0.25]) is False  def test_ten_small_scoops():    assert packet_full([0.1] * 10) is True, f"gave {packet_full([0.1] * 10)}"  def test_three_scoops():    assert packet_full([0.7, 0.2, 0.1]) is True, f"gave {packet_full([0.7, 0.2, 0.1])}"  passed = failed = 0for name, test in list(globals().items()):    if name.startswith("test_"):        try:            test()            print("PASS", name)            passed += 1        except AssertionError as problem:            print("FAIL", name, problem)            failed += 1print(passed, "passed,", failed, "failed")

PASS test_two_halvesPASS test_too_littlePASS test_ten_small_scoopsPASS test_three_scoops4 passed, 0 failed

reviews = [    "rn 0 0", "en 1 1", "en 0 1", "en 0 0", "rn 0 1", "en 0 0", "en 0 0", "rn 0 0", "en 0 0", "en 0 1",    "en 1 0", "en 1 1", "rn 0 0", "en 0 0", "rn 1 0", "en 0 0", "en 1 1", "rn 1 1", "rn 1 0", "rn 0 1",    "en 0 0", "rn 0 0", "en 0 0", "en 1 1", "rn 1 0", "en 1 1", "rn 0 0", "rn 0 0", "rn 0 0", "en 0 0",    "en 0 0", "rn 0 0", "rn 1 0", "rn 0 0", "rn 1 0", "rn 1 1", "en 0 0", "en 1 1", "en 0 0", "en 0 0",    "rn 1 1", "en 0 0", "rn 0 0", "en 1 1", "en 1 1", "en 0 0", "en 1 1", "en 0 0", "en 0 0", "en 0 0",]  def measure(name, languages):    """Count the outcomes for the reviews in these languages."""    tp = fp = fn = tn = 0    for review in reviews:        language, complaint, flagged = review.split()        if language not in languages:            continue        if complaint == "1" and flagged == "1":            tp += 1        elif complaint == "1":            fn += 1        elif flagged == "1":            fp += 1        else:            tn += 1    print(f"{name:13} TP {tp:2}  FP {fp}  FN {fn}  TN {tn:2}  precision {tp / (tp + fp):.0%}  recall {tp / (tp + fn):.0%}")  measure("All", ["en", "rn"])measure("English", ["en"])measure("Roman Nepali", ["rn"])

All           TP 12  FP 4  FN 6  TN 28  precision 75%  recall 67%English       TP  9  FP 2  FN 1  TN 18  precision 82%  recall 90%Roman Nepali  TP  3  FP 2  FN 5  TN 10  precision 60%  recall 38%

One limit: “The model found only 3 of the 8 complaints written in Nepali in Roman letters, against 9 of 10 in English, so read the Roman Nepali reviews yourself: most complaints there are missed.” Guests who write in Roman Nepali are often the domestic tourists many homestays depend on.

• i.Every route into a square arrives from exactly one of the two squares before it, north or west, so the routes split into two groups that don’t overlap: those through the north square and those through the west one. Adding their counts counts every route once. Following every route walks each one separately, and their number grows very fast with the size of the orchard (126 even for this small one, and about 3 × 10¹⁶ for an open grid of 30 × 30), while the table works out each square once: 30 squares here.
• ii.0.5 and 0.25 are exact in binary (a half and a quarter), so adding them gives exactly 1.0 or 0.75 with no error; only numbers like 0.1 that binary can’t store exactly show the bug.
• iii.It mixes the two languages: 90% of English complaints are found but only 38% of Roman Nepali ones. Owners would think they see two-thirds of all complaints, while most complaints in Roman Nepali are missed. I would collect and label many more Roman Nepali reviews, train and test the model on them, and report its results by language.