Final Exam Model Paper 8

• i.In right it walks over 1, 1, 0, 0 (4 steps) and reads the blank (step 5), stepping back onto the last 0 in borrow. The last 0 becomes 1 (step 6), the next 0 becomes 1 (step 7), and the 1 before them becomes 0, in state done (step 8). The tape reads 1011, after 8 steps.
• ii.It subtracts 1: 1100 is twelve and 1011 is eleven. Like borrowing in subtraction by hand, every 0 at the end becomes 1 until the first 1, which becomes 0.
• iii.It turns every 0 into 1 walking left and then reads the blank before the number in state borrow. There is no rule for borrow reading a blank, so the machine is stuck (after 7 steps) and never reaches done: there is no 1 to borrow from, since 0 − 1 can’t be written as a binary number like these.

class MilkCollection:    """Tells every subscriber when a farmer's milk is recorded."""    def __init__(self):        self.listeners = []     def subscribe(self, listener):        self.listeners.append(listener)     def record(self, farmer, liters, fat):        for listener in self.listeners:            listener(farmer, liters, fat)  def sms_farmer(farmer, liters, fat):    print(f"SMS to {farmer}: {liters} L recorded today, fat {fat}%")  def quality_alert(farmer, liters, fat):    if fat < 3.5:        print(f"Quality officer: {farmer}'s milk has only {fat}% fat")  dairy = MilkCollection()dairy.subscribe(sms_farmer)dairy.subscribe(quality_alert)dairy.record("Maya Tamang", 12.5, 4.1)dairy.record("Bishnu Lama", 8.0, 3.2)

SMS to Maya Tamang: 12.5 L recorded today, fat 4.1%SMS to Bishnu Lama: 8.0 L recorded today, fat 3.2%Quality officer: Bishnu Lama's milk has only 3.2% fat

A monthly total, or a message to the buyer, can later subscribe without MilkCollection changing at all.

• i.What the app is for; how to install it and run it; how to run its tests; how to help (for example, how to propose a change); and its license.
• ii.For example:

def fat_bonus(liters, fat):    """The extra rupees for a day's milk: liters (a number) at fat (a percentage).    Gives 0 when fat is 4.0% or less."""

iii. A comment should say why, not repeat the code. For example: # The cooperative pays 10% more in the dry season (Mangsir to Jestha), as agreed in its 2082 meeting.

• i.The film comes from a server a short distance away, inside the viewer’s own internet company, not from a data center abroad: the data has less distance to travel, crosses fewer busy links, and each server has fewer viewers to serve.
• ii.Without the edge servers, each of the 200,000 viewers would pull the film across the internet company’s expensive links across the border. With them, it crosses once, to fill the cache, and the rest stays inside the country, so the company pays for less traffic abroad and its links stay free for everything else.
• iii.DNS: the CDN’s DNS servers see roughly where the question comes from and answer with the address of a nearby edge server. Or anycast: the same address is announced from many places, and the routers carry each packet to the nearest one.

• i.If the screen made no difference, chance alone would give a difference this big only about 1 time in 100. So the difference is probably real.
• ii.A p-value says nothing about how big or how useful a difference is. With 2 million users, even a tiny difference, 0.1 of a percentage point, can be significant. One more booking in every 1,000 users may not be worth the cost of the change.
• iii.The size of the difference (0.1 points, about 1 more booking per 1,000 users) with its 95% interval, and the p-value; then whether it is worth the cost.

Both claims are cherry-picked: each chooses the start that gives the answer it wants. The report starts in 2020, the year visitors fell to a third (when travel stopped worldwide), so “tripled” measures mostly the recovery from that fall, not growth. The critic starts in 2019, the last year before the fall, and ends in 2025: 61 to 62 is true, but it hides that the park regained everything it lost and was growing again by 2024–2025.
An honest summary uses the whole series: visitors grew steadily from 52,000 to 61,000 between 2016 and 2019, fell to about 20,000 in 2020, recovered to the 2019 level by 2024, and reached 62,000 in 2025, the most so far.

• i.(0 × 31 + 500) mod 97 = 500 mod 97 = 15; (15 × 31 + 1,200) mod 97 = 1,665 mod 97 = 16; (16 × 31 + 3,000) mod 97 = 3,496 mod 97 = 4; (4 × 31 + 800) mod 97 = 924 mod 97 = 51.
• ii.The third hash becomes (496 + 300) mod 97 = 796 mod 97 = 20, and the last (20 × 31 + 800) mod 97 = 1,420 mod 97 = 62. Every link checks, but the last hash is 62, not the 51 read out at the meeting, so the change is caught.
• iii.With only 97 possible hashes, an amount 97 more or less gives the same hash: 3,000 − 97 = 2,903 gives (496 + 2,903) mod 97 = 3,399 mod 97 = 4 again, so every later hash, and the last one, stays the same. SHA-256 has 2²⁵⁶ possible hashes, and nobody knows how to find two inputs with the same one, so a change can’t be hidden that way.

• The hard problem (named by the philosopher David Chalmers in 1995): science explains more and more of what a brain does, but not why any of it is felt, why seeing red feels like something at all. Nobody has solved it, so nobody can simply check whether a machine is conscious.
• Functionalism: consciousness depends on what a system does, the way information is organized and used, so a machine organized the right way could be conscious, whatever it is made of.
• Another position: consciousness needs a living body and brain (Searle and others: a simulated brain would no more feel than a simulated storm makes anything wet); or, we can’t know yet, without an agreed theory, so we should be careful in both directions.

i. J1 ends first (day 4): take it. J2 and J3 and J4 start on or before day 4: they share a day with J1. J5 (days 7 to 8) fits: take it. J6 starts on day 8, J5’s last day: it doesn’t fit. J1 and J5: Rs 16,000.

ii. J4 (Rs 13,000) first. J3, J1 and J2 share days with it (J1’s day 4), and so does J5 (day 7). J6 (days 8 to 11) fits. J4 and J6: Rs 18,000.

iii.

The most is Rs 21,000, from J3 and J5 (days 4 to 6, then 7 to 8): reading back, the 21,000 came from taking J5 with the best of J1 to J3, which was J3. Both greedy methods missed it: ending first took the small J1, which blocked J3; paying most took J4, which blocked J5.

iv. Each job is taken or not: 2³⁰, about a billion sets (1,073,741,824). The table has one row for each job, each a comparison of two numbers (plus finding the last job that ends before it starts): about 30 rows, a few hundred steps at most.

i.

• Embossed: read correctly 588 ÷ 600 = 98%. It gave a number for 588 + 6 = 594, and 6 ÷ 594 ≈ 1% were wrong.
• Hand-painted: read correctly 320 ÷ 400 = 80%. It gave a number for 320 + 40 = 360, and 40 ÷ 360 ≈ 11% were wrong: more than 1 in 9.
• So a fine sent for an older plate is about 11 times as likely to go to the wrong owner.

ii. A misread sends a fine to an innocent owner, who must prove it wasn’t them (travel to an office, lose a day’s work, or pay to make it go away): the cost falls on someone who did nothing. A plate it couldn’t read lets a driver who crossed on red go unfined, a cost to road safety but not to an innocent person. It isn’t fair: owners of older vehicles with hand-painted plates, often owners who can least afford a wrong fine, would get many more wrong fines than others for the same behavior.

iii. One well-argued case (other conclusions earn marks with good reasons): No fine without a person checking, at least for now. A wrong fine punishes an innocent person and destroys trust in the whole system; with about 1 in 9 numbers wrong for older plates, automatic fines would send many. What must be in place:

• Human review: an officer looks at the photo beside the number read before any fine is sent.
• The owner’s right to see and appeal: the fine comes with the photo, and a simple, free way to appeal.
• Fix the gap at its cause: train and test the reader on many more hand-painted plates; report its error by kind of plate, and check it again after release (new plates, dirt, rain and night photos can make it drift).
• A named office responsible for the system, and a way to stop it.

The best for a pole of n meters is the best, over every first piece, of that piece’s price plus the best for the rest. The table best keeps the answer for every shorter pole, so each is worked out once.

PRICE = {1: 20, 2: 100, 3: 170, 4: 180, 5: 240, 6: 330}   # rupees for a piece of each length, in meters  def best_cut(length):    """(most rupees, piece lengths) for a pole of a whole number of meters."""    best = [(0, [])]                       # best[n]: the best for a pole n meters long    for n in range(1, length + 1):        options = []        for piece, rupees in PRICE.items():            if piece <= n:                rest_rupees, rest_pieces = best[n - piece]                options.append((rupees + rest_rupees, [piece] + rest_pieces))        best.append(max(options))    return best[length]  def try_every(length):    """The most rupees, by trying every first piece and every way to cut the rest."""    if length == 0:        return 0    return max(rupees + try_every(length - piece) for piece, rupees in PRICE.items() if piece <= length)  def test_nothing_to_cut():    assert best_cut(0) == (0, [])  def test_one_meter():    assert best_cut(1) == (20, [1])  def test_greedy_would_fail():    # most rupees a meter first would take 3 m (Rs 170) and 1 m (Rs 20): Rs 190; two 2 m pieces give Rs 200    assert best_cut(4)[0] == 200, f"gave {best_cut(4)}"  def test_pieces_add_up():    for n in range(13):        rupees, pieces = best_cut(n)        assert sum(pieces) == n and sum(PRICE[p] for p in pieces) == rupees, f"{n} m: {pieces}"  def test_same_as_trying_every_way():    for n in range(13):        assert best_cut(n)[0] == try_every(n), f"{n} m: {best_cut(n)[0]}, not {try_every(n)}"  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") rupees, pieces = best_cut(10)print(f"A 10 m pole: Rs {rupees}, cut into {sorted(pieces, reverse=True)} m")

PASS test_nothing_to_cutPASS test_one_meterPASS test_greedy_would_failPASS test_pieces_add_upPASS test_same_as_trying_every_way5 passed, 0 failedA 10 m pole: Rs 540, cut into [3, 3, 2, 2] m

The first run:

PASS test_open_and_dryPASS test_closed_and_wetFAIL test_open_but_heavy_rain gave TrueFAIL test_closed_on_a_dry_day gave True2 passed, 2 failed

Line 3 says or, so the bus may run when either condition holds: an open road after 75 mm of rain, or a closed road on a dry day. The requirement needs both. The two tests that passed had both conditions the same (both true, or both false), where or and and agree. The tests match the requirement, so the code is wrong: or becomes and.

def can_run(road_open, rain_mm):    """True when the bus may run: the road is open and less than 50 mm of rain fell overnight."""    if road_open and rain_mm < 50:        return True    return False  def test_open_and_dry():    assert can_run(True, 12) is True  def test_closed_and_wet():    assert can_run(False, 80) is False  def test_open_but_heavy_rain():    assert can_run(True, 75) is False, f"gave {can_run(True, 75)}"  def test_closed_on_a_dry_day():    assert can_run(False, 0) is False, f"gave {can_run(False, 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_open_and_dryPASS test_closed_and_wetPASS test_open_but_heavy_rainPASS test_closed_on_a_dry_day4 passed, 0 failed

import csv with open("recordings.csv") as f:    rows = list(csv.DictReader(f))  def measure(name, places):    """Count the outcomes for the recordings made in these places."""    tp = fp = fn = tn = 0    for row in rows:        if row["place"] not in places:            continue        real, said = row["babbler"] == "yes", row["model"] == "yes"        if real and said:            tp += 1        elif real:            fn += 1        elif said:            fp += 1        else:            tn += 1    print(f"{name:7} TP {tp:2}  FP {fp}  FN {fn}  TN {tn:2}  precision {tp / (tp + fp):.0%}  recall {tp / (tp + fn):.0%}")  measure("All", ["forest", "road"])measure("Forest", ["forest"])measure("Road", ["road"])

All     TP 17  FP 5  FN 8  TN 30  precision 77%  recall 68%Forest  TP 12  FP 1  FN 2  TN 15  precision 92%  recall 86%Road    TP  5  FP 4  FN 6  TN 15  precision 56%  recall 45%

One limit: “Beside the road the model heard only 5 of the 11 recordings in which a spiny babbler sang, and almost half of its ‘babbler’ answers there were wrong, so its counts near roads can’t be trusted.” Traffic noise is a likely reason; a count from road recordings would make the birds there look rarer than they are.

• i.Trying every way calls itself for the same shorter poles again and again (the rest of a 10 m pole after a 1 m piece, and after two 1 m pieces, and so on: the same smaller problems overlap), so the work grows very fast with the length. The table works out each length once, from the ones before it: about 6 tries for each meter. For 4 m, the most a meter is the 3 m piece (about Rs 57 a meter), which leaves 1 m worth only Rs 20: Rs 190. Two 2 m pieces give Rs 200: the first choice that looked best spoiled what was left.
• ii.Those two tests had both conditions true or both false, and then or and and give the same answer. Only a test with one true and one false shows the difference.
• iii.The overall numbers mix the forest, where it works well (recall 86%), with the road, where it misses more than half the songs (recall 45%) and almost half its “babbler” answers are wrong. Beside roads its counts would be wrong both ways. I would record more by roads, train and test it on that noise, and report its results by place, checking road counts by ear until it does better.