Final Exam Model Paper 6

• i.No. The test says “not prime” only when it has found a witness: a number a for which the calculation comes out a way it never does for a prime. That is proof.
• ii.Each round that finds no witness cuts the chance of being fooled to a quarter or less, so after 10 rounds it is at most 1 in 4¹⁰ = 1 in 1,048,576, about one in a million. (20 rounds would make it less than one in a million million.)
• iii.The square root of a 300-digit number has about 150 digits, so dividing would take about 10¹⁵⁰ tries: no computer could ever finish. Each Miller–Rabin round takes only a few hundred multiplications, even for a 300-digit number.

rules = [    (("reach", "?a", "?b"), [("trail", "?a", "?b")]),    (("reach", "?a", "?c"), [("trail", "?a", "?b"), ("reach", "?b", "?c")]),    (("high", "?a", "?b"), [("reach", "?a", "?b"), ("height", "?b", "?h"), ("<", 3500, "?h")]),]

The second rule is recursive, like the book’s ancestor: one trail, then anywhere that can be reached from there. With the engine of Unit 3:

# Facts: trails up the valley (each written once, going up) and heights in meters, roundedfacts = {    ("trail", "Chame", "Pisang"), ("trail", "Pisang", "Ngawal"), ("trail", "Pisang", "Manang"),    ("trail", "Ngawal", "Manang"), ("trail", "Manang", "Yak Kharka"), ("trail", "Yak Kharka", "Thorong Phedi"),    ("height", "Chame", 2670), ("height", "Pisang", 3200), ("height", "Ngawal", 3660),    ("height", "Manang", 3540), ("height", "Yak Kharka", 4050), ("height", "Thorong Phedi", 4450),} rules = [    (("reach", "?a", "?b"), [("trail", "?a", "?b")]),    (("reach", "?a", "?c"), [("trail", "?a", "?b"), ("reach", "?b", "?c")]),    (("high", "?a", "?b"), [("reach", "?a", "?b"), ("height", "?b", "?h"), ("<", 3500, "?h")]),]  def match(pattern, fact, found):    if len(pattern) != len(fact):        return None    found = dict(found)    for p, f in zip(pattern, fact):        if isinstance(p, str) and p.startswith("?"):            if found.setdefault(p, f) != f:                return None        elif p != f:            return None    return found  def solve(body, found):    if not body:        yield found        return    first, rest = body[0], body[1:]    if first[0] in ("!=", "<"):        a, b = (found.get(x, x) for x in first[1:])        if (a != b) if first[0] == "!=" else (a < b):            yield from solve(rest, found)        return    for fact in list(facts):        more = match(first, fact, found)        if more is not None:            yield from solve(rest, more)  while True:    new = set()    for head, body in rules:        for found in solve(body, {}):            new.add(tuple(found.get(x, x) for x in head))    if new <= facts:        break    facts |= new  def ask(*pattern):    return sorted(m["?who"] for f in facts if (m := match(pattern, f, {})))  print("From Chame you can reach:", ask("reach", "Chame", "?who"))print("Places that lead to Manang:", ask("reach", "?who", "Manang"))print("Above 3,500 m from Pisang:", ask("high", "Pisang", "?who"))

From Chame you can reach: ['Manang', 'Ngawal', 'Pisang', 'Thorong Phedi', 'Yak Kharka']Places that lead to Manang: ['Chame', 'Ngawal', 'Pisang']Above 3,500 m from Pisang: ['Manang', 'Ngawal', 'Thorong Phedi', 'Yak Kharka']

• i.Keep the library’s copyright line and license with it, and list it, with its version and license (in a file such as requirements.txt and the README). A permissive license asks little more.
• ii.The GPL is copyleft: whoever shares a program built from it must share that program’s source code too, under the same license. Since they will share the source anyway, they can use it, but their app must then be licensed under the GPL.
• iii.Photos: someone else’s photos may not be used unless their license allows it: find the license, credit the photographer and source, or ask permission, or take their own photos. AI function: test it with normal, boundary and erroneous data and review every line like a teammate’s code, then record that an AI wrote the first draft (in the commit message and the README).

• i.A majority of five: 3 copies.
• ii.Kathmandu (two copies) and Pokhara are 3, a majority, so they go on booking. Biratnagar and Nepalgunj are only 2, so they refuse (“please try again later”) until the link is back, then catch up. That is right for seats: if both sides sold seats, the same seat could be sold twice, and two passengers would turn up for it. The airline chooses consistency over availability.
• iii.With four copies, a break can split them two and two: neither side is a majority, so nobody can book anywhere. With an odd number, one side of any split always keeps a majority; five copies can lose any two and still carry on.

• i.It picks 40 farms’ harvests from the sample, with replacement, so some farms come in twice and some not at all, and works out their average: a stand-in for another random sample of 40.
• ii.“The farms’ paddy harvest was about 4.1 tonnes per hectare (95% interval 3.7 to 4.5), from 40 farms chosen at random.”
• iii.No. The interval measures only chance: how much another random sample of the same size would vary. Farms beside the highway may differ from the rest (better roads to fertilizer and markets, irrigation along the road), and that bias misses in one direction; the interval would be just as narrow, round a possibly wrong answer.

The conclusion goes beyond the evidence. p = 0.4 means that with only six plots, chance alone gives a difference this big about four times in ten, so the test can’t tell whether the spray made the difference. That is not the same as showing no difference: a test this small has very low power, and can find only a very big difference. The 7 points may be real; the test was simply too small to tell. “We found no difference” from a small test is not evidence that there is none.
She should plan a bigger trial in advance: decide the measure (yield lost) and how many plots are needed to find a difference of the size that would matter to farmers (aiming for about 80% power), choose the sprayed plots at random again, and report the difference with its 95% interval, not just “works” or “doesn’t”.

• i.n = 7 × 13 = 91; φ(n) = (7 − 1)(13 − 1) = 6 × 12 = 72.
• ii.1 + 72 = 73: not a multiple of 5. 1 + 2 × 72 = 145 = 5 × 29. So d = 29 (check: 5 × 29 = 145 = 2 × 72 + 1).
• iii.3 shares a factor, 3, with φ(n) = 72. Then 3 × d is always a multiple of 3, but 1 + a multiple of 72 never is (it leaves 1 when divided by 3), so no private power exists: e must share no factor with φ(n).

• The European Union: one law, by risk. The AI Act covers all AI: some uses are banned, and “high-risk” uses (jobs, education, credit, public services) must be tested, use good data, keep records and have human oversight, checked by regulators with heavy fines.
• India: guidelines and the laws it already has. Principles that companies follow on their own, its existing laws on data, consumers, copyright and crime applied to AI, and a new law only where a gap is found.
• For Nepal: from the EU, the idea of levels of risk, with strict rules only for uses that decide about people’s lives; from India, a channel for reporting harm from AI, records of AI incidents, or labels on AI-made content, without a heavy new office.

i. Price per kg: dried apples 8,000 ÷ 10 = 800; walnuts 9,000 ÷ 15 = 600; kidney beans 12,000 ÷ 40 = 300; flour 2,000 ÷ 10 = 200.
Take dried apples (10 kg), then walnuts (25 kg so far); kidney beans would make 65 kg, too heavy, so skip them; flour fits (35 kg). The load: dried apples, walnuts and flour, 35 kg, Rs 19,000, with 25 kg of the mule’s load unused.

ii. Kidney beans (Rs 12,000, 40 kg), then walnuts (55 kg); dried apples or flour would make 65 kg, too heavy. Kidney beans and walnuts, 55 kg, Rs 21,000.

iii. With four sacks there are 2⁴ = 16 sets. The ones that fit (D dried apples, W walnuts, B beans, F flour):

The other three (D + W + B 65 kg, W + B + F 65 kg, all four 75 kg) are too heavy. The best is dried apples, kidney beans and flour: exactly 60 kg, Rs 22,000, more than either greedy method found. Taking the walnuts, which looked good on both rules, left no room for the beans with the dried apples.

iv. Each kind is either taken or not, so there are 2⁵⁰ packings, about 1.1 × 10¹⁵ (a thousand million million). At a billion a second that is about 1.1 million seconds, about 13 days, and each kind more doubles it. Dynamic programming does far better (the book’s snack-packing problem in “Which family?”): the best load from the first k kinds with w kg of room left is the better of “take kind k” and “leave it”, each built from the best for the first k − 1 kinds; the same smaller questions come up again and again (they overlap), so each is worked out once and remembered. With whole kilograms, that is only 50 × 61 small questions.

i. TP = 85, FN = 15, FP = 60, TN = 340.

• Precision = 85 ÷ (85 + 60) = 85 ÷ 145 ≈ 59%: of the leaves it calls blighted, only about 3 in 5 are.
• Recall = 85 ÷ (85 + 15) = 85 ÷ 100 = 85%: it finds 85 of every 100 blighted leaves.
• F1 = 2 × 0.586 × 0.85 ÷ (0.586 + 0.85) = 0.997 ÷ 1.436 ≈ 69%.

ii. Newer phones: precision 57 ÷ (57 + 24) = 57 ÷ 81 ≈ 70%, recall 57 ÷ 60 = 95%. Older phones: precision 28 ÷ (28 + 36) = 28 ÷ 64 ≈ 44%, recall 28 ÷ 40 = 70%. Farmers with older phones get worse answers both ways: it misses 3 in 10 of their blighted plants, and more than half of its “spray today” warnings to them are false. They are often the poorer farmers, who can least afford either a lost crop or a wasted spray. The overall numbers hid this.

iii. One well-argued case (other conclusions earn marks with good reasons): Not as it is; perhaps later, as advice checked by people.

• The cost of each mistake. A miss is costly: late blight can spread through a field in days, and a missed leaf can cost the harvest, so recall matters a great deal. But a false alarm is not free here, as it might be for a warning: it tells a farmer to spray fungicide, which costs money, exposes the person spraying (often without protective clothing), leaves residues on tomatoes sold in the market, and harms soil and water. With precision 59%, and 44% on older phones, many farmers would spray for nothing, and the app tells them to act, not just to look.
• First: collect and label many more photos from older phones, retrain, and test again for each kind of phone (and each season and variety) before any recommendation; a lower threshold for older phones would catch more blight but bring still more false alarms, so it isn’t the fix.
• How to use it: the app should say “may be blight: check these signs, or send the photo to the officer” rather than “spray today”, with the officer or a trained farmer leader confirming before spraying (human review); farmers told what it was tested on and how often it is wrong; results checked each season by phone type after release (drift), with a way to report mistakes and a way to stop recommending it. A model card from the company, with these numbers, should come first.

import heapqimport math POS = {"Bhairahawa": (0, 0), "Lumbini": (-20, -3), "Butwal": (8, 22), "Sunwal": (-6, 19),       "Devdaha": (20, 20), "Tansen": (6, 40), "Rampur": (26, 52), "Ridi": (-14, 55),       "Bartung": (-4, 46), "Jhumsa": (14, 60)}ROADS = [("Bhairahawa", "Lumbini", 22), ("Bhairahawa", "Butwal", 25), ("Bhairahawa", "Sunwal", 24),         ("Lumbini", "Sunwal", 30), ("Butwal", "Sunwal", 16), ("Butwal", "Devdaha", 14),         ("Butwal", "Tansen", 28), ("Sunwal", "Bartung", 38), ("Tansen", "Bartung", 15),         ("Tansen", "Rampur", 35), ("Bartung", "Ridi", 20), ("Tansen", "Ridi", 34),         ("Devdaha", "Rampur", 45)] graph = {place: {} for place in POS}for a, b, km in ROADS:    graph[a][b] = km    graph[b][a] = km  def find_route(start, goal, estimate):    """(km, route, places visited) for the shortest route, or None if there is none."""    best = {start: 0}    came_from = {start: None}    done = set()    waiting = [(estimate(start, goal), 0, start)]    while waiting:        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]            return km, route[::-1], 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, goal), new_km, nxt))    return None  def no_estimate(place, goal):    return 0  def straight_line(place, goal):    return math.dist(POS[place], POS[goal])  def test_start_is_goal():    assert find_route("Tansen", "Tansen", straight_line) == (0, ["Tansen"], 1)  def test_no_road():    assert find_route("Butwal", "Jhumsa", straight_line) is None  def test_worked_by_hand():    # by hand: through Sunwal and Butwal is 30 + 16 + 28 = 74; through Bhairahawa 75    km, route, visited = find_route("Lumbini", "Tansen", straight_line)    assert km == 74 and route == ["Lumbini", "Sunwal", "Butwal", "Tansen"], f"{km} {route}"  def test_same_as_dijkstra_everywhere():    for a in POS:        for b in POS:            fast = find_route(a, b, straight_line)            sure = find_route(a, b, no_estimate)            if sure is None:                assert fast is None, f"{a} to {b}"            else:                assert fast[0] == sure[0], f"{a} to {b}: {fast[0]} km, not {sure[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") for name, estimate in [("Dijkstra", no_estimate), ("A*", straight_line)]:    km, route, visited = find_route("Ridi", "Bhairahawa", estimate)    print(f"{name}: {km} km, {visited} places visited: {' → '.join(route)}")

PASS test_start_is_goalPASS test_no_roadPASS test_worked_by_handPASS test_same_as_dijkstra_everywhere4 passed, 0 failedDijkstra: 82 km, 8 places visited: Ridi → Bartung → Sunwal → BhairahawaA*: 82 km, 5 places visited: Ridi → Bartung → Sunwal → Bhairahawa

Both find the same 82 km route; A* visits 5 places instead of 8, because places away from Bhairahawa get bigger totals and wait.

The first run:

PASS test_dry_nightPASS test_one_burstFAIL test_storm gave []FAIL test_no_readings gave None2 passed, 2 failed

Line 7, return heavy, is indented inside the loop, so the function returns after looking at the first reading only. The storm’s first hour had 12 mm, so it returned []; with no readings the loop never runs, the return is never reached, and the function gives None. The two tests that passed happened to need only the first reading. The tests match the requirement, so the code is wrong: move return heavy out of the loop, level with for:

def heavy_hours(readings):    """The hours with 30 mm of rain or more, in the order they came."""    heavy = []    for hour, mm in readings:        if mm >= 30:            heavy.append(hour)    return heavy  def test_dry_night():    assert heavy_hours([("01:00", 4), ("02:00", 0), ("03:00", 12)]) == []  def test_one_burst():    assert heavy_hours([("05:00", 41), ("06:00", 9)]) == ["05:00"]  def test_storm():    night = [("21:00", 12), ("22:00", 35), ("23:00", 48), ("00:00", 30), ("01:00", 6)]    assert heavy_hours(night) == ["22:00", "23:00", "00:00"], f"gave {heavy_hours(night)}"  def test_no_readings():    assert heavy_hours([]) == [], f"gave {heavy_hours([])}"  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_dry_nightPASS test_one_burstPASS test_stormPASS test_no_readings4 passed, 0 failed

truth  = "-R---RR--RR--R---R-R-RRR--R---RR-RR--RR--R-RRR-R-RR-------R-"said   = "-----RR--RR-R------RR-RR--R---RR-RR-RR---RRRRR-R-R------R-R-"season = "DDDDDMMDMDMDMDDDDMDMMMMMMDMDMDMMMMMDDMDMDDMMMMDMMMDDDDDDMDMD"  def measure(name, keep):    """Count the outcomes on the days whose season is in keep."""    tp = fp = fn = tn = 0    for real, forecast, s in zip(truth, said, season):        if s not in keep:            continue        if real == "R" and forecast == "R":            tp += 1        elif real == "R":            fn += 1        elif forecast == "R":            fp += 1        else:            tn += 1    print(f"{name:8} TP {tp:2}  FP {fp}  FN {fn}  TN {tn:2}  precision {tp / (tp + fp):.0%}  recall {tp / (tp + fn):.0%}")  measure("All", "MD")measure("Monsoon", "M")measure("Dry", "D")

All      TP 20  FP 5  FN 6  TN 29  precision 80%  recall 77%Monsoon  TP 18  FP 4  FN 2  TN  6  precision 82%  recall 90%Dry      TP  2  FP 1  FN 4  TN 23  precision 67%  recall 33%

One limit: “In the dry season the model forecast only 2 of the 6 rainy days, so on most days when rain came it had said the harvest was safe to dry; and with only 6 dry-season rainy days in the test, even that number is uncertain.” The dry season is when the harvest is dried, so this is where the model matters most.

• i.A* stops when the goal is taken from the heap. If an estimate were too high, a place on the real shortest route could look worse than it is and wait, while the goal was reached and taken along a longer route. The straight line is the shortest possible path between two places, so it is never more than the road. The test ran A* and Dijkstra’s algorithm (estimate 0, sure to be right) between every two places and checked that the lengths were the same: evidence that the estimate never misled the search on this map.
• ii.The return inside the loop looks only at the first reading. In the two tests that passed, the first reading alone gave the right answer (a dry first hour, or a heavy first hour and no other), so the bug didn’t show.
• iii.Most days in the dry season are dry, so a model that always said “no rain” would still be right on most of them: accuracy is mostly about the common kind. What matters to a farmer is the rainy days, and in the dry season it missed 4 of 6. I would test it on many more dry-season days, with rain, retrain it with more of them, and measure its recall in each season apart before anyone relies on it.