Final Exam Model Paper 4

• i.10-B-07 fits: 10 is a <grade>, B a <section>, and 07 two digits. 9-D-12 doesn’t: D is not one of A, B or C. 9-A-5 doesn’t: <number> needs two digits.
• ii.<list> ::= <roll> | <roll> , <list>
• iii.Arithmetic’s grammar uses itself inside brackets, to any depth, so a checker must remember how many brackets are still open: no fixed number of states can. Here <list> uses itself only at the end: after each roll number the checker needs to remember nothing but where it is in one roll number, so a finite state machine with a loop back for each comma does it, such as (9|10)-[ABC]-\d\d(,(9|10)-[ABC]-\d\d)*.

applicants = [("Hari", 74, 3), ("Sita", 81, 1), ("Bal", 68, 3), ("Gita", 77, 1), ("Ram", 70, 2)]print(sorted(applicants, key=lambda a: a[1], reverse=True))print(sorted(applicants, key=lambda a: (a[2], a[0])))

[('Sita', 81, 1), ('Gita', 77, 1), ('Hari', 74, 3), ('Ram', 70, 2), ('Bal', 68, 3)][('Gita', 77, 1), ('Sita', 81, 1), ('Ram', 70, 2), ('Bal', 68, 3), ('Hari', 74, 3)]

iii. The sorting itself never changes; only the way of comparing applicants, the part that varies, is passed in as a function. Any new order (by name, by ward then age) is a new key, with no change to sorted: that is the strategy pattern, “keep what varies apart from what stays the same”.

• i.Project 1: the requirements are known exactly, written in law, and won’t change during the project, so they can be written and signed first, then designed, built and tested in order, with documents an auditor can check.
• ii.Project 2: the needs will only become clear as students try it. Short rounds (sprints), each ending with a working version that students try, let the team learn and change direction early.
• iii.The team could spend months building, to a plan written at the start, an app that students turn out not to want, and find out only at the end, when changing it is slow and costly.

• i.The queues grow without limit: everyone waits, requests time out, people press refresh, which adds more requests, and the servers may fail altogether. Nobody gets a result.
• ii.The site serves the 5,000 a second it can well, and tells the rest at once to wait, or lets them in a few at a time with their place in the line, so those served get their results quickly and nobody waits on a page that will never come. It is better to serve some people well than everyone badly.
• iii.Any one, for example: cache the results (they don’t change once published), or put them on a content delivery network’s edge servers; add servers before the day (autoscaling, tested with a load test); publish each school’s results as plain pages that need no database.

• i.The message makes no difference: each customer would have paid (or not) whichever message they got, and the difference of 40 is chance.
• ii.It dealt the 1,000 customers, with whether each paid, out again at random into two groups of 500, many times, as if the messages made no difference, and counted how often the shuffled groups differed by 40 or more either way.
• iii.If the message made no difference, a difference this big would turn up by chance only about 13 times in 1,000: rare, so the result is evidence that message B works (significant at 5%). It does not mean there is a 1.3% chance that B makes no difference (or a 98.7% chance that B works), and it says nothing about whether 8 points matters to the shop.

Removing names doesn’t make it anonymous. In a ward of a few hundred households, a mix such as caste, family size and land owned often fits only one household, which neighbors could recognize. As with Netflix’s ratings, a few facts known from elsewhere pick out a whole row. The rows then reveal private facts: income, and who has family abroad, which tells thieves and moneylenders which houses receive money from abroad.
A better plan: publish only totals for groups big enough to hide any one household (by ward, or by caste across the municipality); or add a little random noise to each total (differential privacy); give the full rows only to approved researchers who sign an agreement, on the office’s own computers; and collect and keep only the columns the study needs (data minimization), telling households what is collected and why.

• i.Trying small primes: 51 ÷ 2 doesn’t divide; 51 = 3 × 17. φ(n) = (3 − 1)(17 − 1) = 2 × 16 = 32.
• ii.One more than a multiple of 32: 33, 65, 97… 33 = 3 × 11, so d = 11 (3 × 11 = 33 = 32 + 1).
• iii.m = 13¹¹ mod 51, and 11 = 8 + 2 + 1:

• 13² = 169 ≡ 16 (169 − 153)
• 13⁴ ≡ 16² = 256 ≡ 1 (256 − 255)
• 13⁸ ≡ 1² = 1
• 13¹¹ = 13⁸ × 13² × 13 ≡ 1 × 16 × 13 = 208 ≡ 4 (208 − 204)

The message was 4. (Check: 4³ = 64, and 64 mod 51 = 13.) With a real n, hundreds of digits long, the first step, factoring, is out of reach, and so is everything after it.

Any three, for example:

• Contribute to society and to human well-being: use your skills for everyone’s good, giving more weight to those less advantaged.
• Avoid harm: think about everyone your work affects, and report signs of risk.
• Be honest and trustworthy: tell people what a system can’t do; no false claims or faked data.
• Be fair and take action not to discriminate: check that your work treats all groups fairly.
• Respect the work required to produce new ideas: credit others, and respect copyright and licenses.
• Respect privacy: collect only the data needed, for a clear purpose, and protect it.
• Honor confidentiality: keep secret what you were trusted with, unless it is evidence of breaking the law or the Code.

i. With the start fixed, the 4 branches can be visited in 4 × 3 × 2 × 1 = 24 orders, and each round trip is counted twice, once each way round: 24 ÷ 2 = 12 round trips.

ii. From Tamghas the nearest is Purtighat (5). From Purtighat: Wami Taksar 7, Isma 8, Ridi 13, so Wami Taksar. From Wami Taksar: Isma 4. Only Ridi is left (21), then home (14).
Tamghas → Purtighat → Wami Taksar → Isma → Ridi → Tamghas: 5 + 7 + 4 + 21 + 14 = 51 km.

iii. Reversing Purtighat → Wami Taksar → Isma gives Tamghas → Isma → Wami Taksar → Purtighat → Ridi → Tamghas: 7 + 4 + 7 + 13 + 14 = 45 km, 6 km shorter. Only two legs changed: Tamghas–Purtighat (5) and Isma–Ridi (21), 26 km together, became Tamghas–Isma (7) and Purtighat–Ridi (13), 20 km. Nearest next saved 2 km on its first leg and then had to cross the map, 21 km from Isma to far-off Ridi; reversing the stretch uncrosses the trip (2-opt).

iv. With only 12 round trips, the officer can try every one: write each, add up its legs, and keep the shortest. (Doing so shows 45 km is the shortest; the next best is 48 km.) For 30 branches there are 30! ÷ 2 orders, about 1.3 × 10³², far too many for any computer to try, and no fast method is known that is sure to find the best. The cooperative should use a heuristic, such as nearest next followed by uncrossing until no reversal helps, measure it on small sets of branches where trying every route is possible, and describe its route as good, not as the shortest.

i. Right: typed Nepali 90%, Roman letters 76%, voice 58%; overall (90 + 76 + 58) ÷ 300 = 224 ÷ 300 = 74.7%.
Wrong: typed Nepali 4%, Roman letters 16%, voice 34%; overall (4 + 16 + 34) ÷ 300 = 54 ÷ 300 = 18%.

ii. “I don’t know, call the helpline” costs a farmer a phone call. A wrong dose or date sounds just as sure as a right one, so farmers act on it: a double dose of pesticide can poison the person spraying and the people who eat the crop, and a wrong sowing date can lose a season; nobody may notice until the harm is done. The company’s 90% is the result for typed Nepali only: it hides that more than a third of the answers to voice messages are wrong, and voice is how many farmers who can’t type easily will ask, so the people least served are the ones who most need the help.

iii. One well-argued case (other conclusions earn marks with good reasons): Not yet.

• The harm. About 1 answer in 5 is wrong overall, and 1 in 3 for voice messages, mostly doses and dates, the facts that can hurt people and crops. And it gave way to pressure in 7 of 20 tests: anyone could share a screenshot of it “confirming” a double dose.
• What must happen first. It must answer only from the ministry’s own checked pages (the dose on each pesticide’s label, the sowing calendar), showing the page it used, and say “I don’t know” rather than guess; it must never confirm a dose other than the checked one. Then the whole test plan, with more tests of pressure, is run again, with the results by kind of question recorded with the date and version, and repeated after every change.
• How it could be used, if it passes. Labeled as a chatbot, with the checked page and the helpline’s number on every answer; checked each month on real questions, by kind; an officer responsible for it, and a way to switch it off. A checked table of doses and dates, read out by the helpline’s staff and printed for agrovet shops, may serve farmers better at almost no cost.

import heapqimport math WAREHOUSE = [    "............",    "..S.........",    "............",    "####.######.",    "............",    "............",    "..........G.",    "............",]  def find(grid, letter):    """The (row, column) of the first square holding letter."""    for r, row in enumerate(grid):        if letter in row:            return (r, row.index(letter))  def straight_line(square, goal):    return math.dist(square, goal)  def no_estimate(square, goal):    return 0  def find_path(grid, start, goal, estimate):    """A*: (moves, squares on the way, squares taken), or None if there is no way."""    best = {start: 0}    came_from = {start: None}    done = set()    waiting = [(estimate(start, goal), 0, start)]    while waiting:        guess, moves, here = heapq.heappop(waiting)        if here in done:            continue        done.add(here)        if here == goal:            path = []            while here is not None:                path.append(here)                here = came_from[here]            return moves, path[::-1], len(done)        r, c = here        for nxt in [(r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)]:            nr, nc = nxt            if 0 <= nr < len(grid) and 0 <= nc < len(grid[0]) and grid[nr][nc] != "#":                if nxt not in best or moves + 1 < best[nxt]:                    best[nxt] = moves + 1                    came_from[nxt] = here                    heapq.heappush(waiting, (moves + 1 + estimate(nxt, goal), moves + 1, nxt))    return None  def test_open_floor():    grid = ["S..", "...", "..G"]    assert find_path(grid, (0, 0), (2, 2), straight_line)[0] == 4  def test_round_a_shelf():    grid = ["S#G", ".#.", "..."]    moves, path, taken = find_path(grid, (0, 0), (0, 2), straight_line)    assert moves == 6, f"gave {moves}"    assert path[0] == (0, 0) and path[-1] == (0, 2) and len(path) == 7  def test_no_way():    grid = ["S#.", "##.", "..G"]    assert find_path(grid, (0, 0), (2, 2), straight_line) is None  def test_same_length_fewer_taken():    start, goal = find(WAREHOUSE, "S"), find(WAREHOUSE, "G")    dijkstra = find_path(WAREHOUSE, start, goal, no_estimate)    a_star = find_path(WAREHOUSE, start, goal, straight_line)    assert a_star[0] == dijkstra[0]    assert a_star[2] < dijkstra[2], f"A* took {a_star[2]}, Dijkstra {dijkstra[2]}"  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")start, goal = find(WAREHOUSE, "S"), find(WAREHOUSE, "G")for estimate in [no_estimate, straight_line]:    moves, path, taken = find_path(WAREHOUSE, start, goal, estimate)    print(f"{estimate.__name__}: {moves} moves, {taken} squares taken")

PASS test_open_floorPASS test_round_a_shelfPASS test_no_wayPASS test_same_length_fewer_taken4 passed, 0 failedno_estimate: 13 moves, 82 squares takenstraight_line: 13 moves, 49 squares taken

Both find the same 13 moves; aiming at the goal, A* takes 49 squares instead of 82, because squares away from G get larger totals and wait.

The first run:

FAIL test_sita Sita owes 250FAIL test_hari_with_a_payment Hari owes 0PASS test_not_a_customer1 passed, 2 failed

Sita should owe 1,200 + 250 = 1,450, and Hari 450 + 300 − 500 = 250. Line 7, total = 0, is inside the loop, so the total starts again from 0 at every entry: what is left at the end is only the last entry, if it is the customer’s (Sita’s 250), or 0 (Hari’s last entry isn’t last in the book). The test with no customer passed only by luck. Set the total to 0 once, before the loop:

LEDGER = [("Hari", 450), ("Sita", 1200), ("Hari", 300), ("Gopal", 800), ("Hari", -500), ("Sita", 250)]  def owed(ledger, name):    """What one customer owes: the sum of their entries (a payment is negative)."""    total = 0    for who, amount in ledger:        if who == name:            total = total + amount    return total  def test_sita():    assert owed(LEDGER, "Sita") == 1450, f"Sita owes {owed(LEDGER, 'Sita')}"  def test_hari_with_a_payment():    assert owed(LEDGER, "Hari") == 250, f"Hari owes {owed(LEDGER, 'Hari')}"  def test_not_a_customer():    assert owed(LEDGER, "Maya") == 0  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_sitaPASS test_hari_with_a_paymentPASS test_not_a_customer3 passed, 0 failed

learners = [    (84, "C", True), (45, "C", True), (58, "C", True), (28, "M", False), (55, "M", False),    (51, "M", True), (84, "C", True), (36, "C", False), (53, "C", True), (41, "C", False),    (79, "M", True), (33, "C", False), (73, "C", True), (81, "M", True), (45, "M", False),    (60, "M", True), (55, "C", True), (63, "C", True), (53, "C", True), (37, "C", True),    (53, "C", True), (36, "M", False), (45, "M", True), (45, "C", True), (52, "M", True),    (68, "M", True), (44, "M", False), (38, "M", True), (52, "M", False), (48, "M", False),    (55, "C", True), (42, "C", True), (39, "M", False), (58, "M", True), (38, "C", True),    (65, "C", True), (75, "M", True), (69, "M", True), (58, "C", True), (60, "M", True),]  def measure(name, vehicles):    """Counts the outcomes of the rule for the learners on these vehicles."""    tp = fp = fn = tn = 0    for score, vehicle, passed in learners:        if vehicle not in vehicles:            continue        flagged = score < 45                   # the rule: “will fail”        if flagged and not passed:            tp += 1        elif not passed:            fn += 1        elif flagged:            fp += 1        else:            tn += 1    precision = tp / (tp + fp)    recall = tp / (tp + fn)    print(f"{name:10} TP {tp}  FP {fp}  FN {fn}  TN {tn:2}  precision {precision:.0%}  recall {recall:.0%}")  measure("All", "MC")measure("Motorbike", "M")measure("Car", "C")

All        TP 7  FP 4  FN 4  TN 25  precision 64%  recall 64%Motorbike  TP 4  FP 1  FN 4  TN 11  precision 80%  recall 50%Car        TP 3  FP 3  FN 0  TN 14  precision 50%  recall 100%

One limit: “The rule found every car learner who failed the trial, but only 4 of the 8 motorbike learners who failed (50%): half of them had practice scores of 45 or more; and it was tried on only 11 learners who failed, too few to be sure.” Motorbike learners who fail often had passable practice scores, so the rule misses half of those the extra lessons are for. The school could try a higher cut-off and measure again, or add the riding part of the practice round to the rule.

• i.The estimate gives squares away from G larger totals, so they wait and are often never taken, while squares towards G go first. Each move goes one square, which brings the robot at most 1 square closer to G in a straight line; so the moves left are never fewer than the straight-line distance, and the estimate is never too high: A* still finds the fewest moves.
• ii.Its right answer is 0, and the broken code gives 0 whenever the last entry in the book isn’t the customer’s: it passed by luck, not because the code was right. A test can pass for the wrong reason.
• iii.Most learners passed, so accuracy is mostly about them; the rule misses half the motorbike learners who failed, the learners the extra lessons are for. Measure motorbikes and cars apart, then try other rules (a higher cut-off, the riding part of the practice round) and compare their recall on the learners who failed.