Final Exam Model Paper 2

i. KH-\d+(/A)?
ii.

An empty square means no arrow: the text is rejected at once.
iii. KH-/A: S → 1 → 2 → 3, then / has no arrow from state 3 (a digit must come first): rejected. KH-17/A: S → 1 → 2 → 3 → 4 → 4 → 5 → 6, and 6 is accepting: accepted.

One good set of tests (with a fine that meets the rule, so they can be run):

def fine(days):    if days < 0:        raise ValueError(f"days can't be negative: {days}")    return min(max(days - 14, 0) * 5, 100)  def test_normal():    assert fine(17) == 15              # 3 days late  def test_boundary():    assert fine(14) == 0               # the last free day    assert fine(15) == 5               # the first day late    assert fine(34) == 100             # 20 days late: exactly the most    assert fine(35) == 100             # one more day: still 100  def test_erroneous():    try:        fine(-1)    except ValueError:        return                         # refused, as it should be    raise AssertionError("-1 was accepted")  for test in [test_normal, test_boundary, test_erroneous]:    test()    print("PASS", test.__name__)

PASS test_normalPASS test_boundaryPASS test_erroneous

• i.Test one part alone: for example, the form refuses a date of birth in the future, or a name left empty (with a stub in place of the database).
• ii.Test two parts together where they hand data to each other: for example, a record saved by the form is found in the database with the same date, and the SMS part sends the certificate number the database gave it. Each part can pass its own tests and still disagree with the next, such as one writing dates in Bikram Sambat and the other reading them as AD.
• iii.The customer: the municipality’s officials (the ward secretaries and the registration officer), who check the finished app against the requirements they agreed, and decide whether to accept it.

• i.About 6 times, once every 10 minutes. The first request after the copy runs out is a miss: the page is built from the database and kept. The other requests in those 10 minutes are hits, served from the copy.
• ii.The copy is stale: for up to 10 minutes people see the old, lower level, while the river is rising, which is exactly when the number matters most. The site can remove (or rebuild) the copy as soon as a new reading arrives, or keep it for a shorter time.
• iii.Still about 6. However many people come, the database is read only when the copy runs out: the cache makes the database’s work independent of the number of visitors, which is why it helps most on the busiest day.

• i.For example, money and land: better-off farmers can afford a smartphone with data, and also irrigation, better seed and fertilizer, which raise their harvests. (Others: schooling; being younger; living near a town and its market.)
• ii.Reverse cause: farmers who already get good harvests earn more, so they can buy smartphones and data; the harvests could be causing the app use.
• iii.A randomized trial: choose at random which farmers (or villages) get a phone with the app and training and which don’t, then compare their harvests after a season. Random choice makes the groups alike in everything else, confounders included, so a difference can be put down to the app.

The claim is not supported. For each kind of loan, Bhojpur’s cooperative has the better record (75% against 70%, and 92% against 88%). Dhankuta looks better overall only because most of its loans are housing loans, which are repaid more often everywhere, while most of Bhojpur’s are small business loans, which are repaid less often. A total that reverses the comparison inside every group is Simpson’s paradox: the mix of loans, not the choosing, makes the difference. If anything, Dhankuta could learn from Bhojpur. A fair report compares like with like, kind of loan by kind of loan.

• i.A = 2⁵ mod 29 = 32 mod 29 = 3.
• ii.B = 2⁹ mod 29 = 512 mod 29. 17 × 29 = 493, so B = 19.
• iii.Aayush works out Bᵃ = 19⁵ mod 29: 19² = 361 ≡ 13 (361 − 348); 19⁴ ≡ 13² = 169 ≡ 24 (169 − 145); 19⁵ ≡ 24 × 19 = 456 ≡ 21 (456 − 435).

Bina works out Aᵇ = 3⁹ mod 29: 3³ = 27; 3⁶ = 27² = 729 ≡ 4 (729 − 725); 3⁹ ≡ 4 × 27 = 108 ≡ 21 (108 − 87).
Both get 21, without ever sending it. (Eve sees only 29, 2, 3 and 19.)

Any three, in order, for example:

• Information and funding (light): a grant for an AI research center, or courses in AI for teachers.
• Disclosure: a label on every AI-made video or picture.
• Impact assessment: questions a government office must answer before using an AI system to decide about people, which set the safeguards it needs.
• Licensing: only approved companies may sell AI systems for grading exams.
• A ban (heaviest): no AI system may score people’s social behavior.

(Guidelines and standards also lie between the light and heavy ends.)

i. Each cell is the smallest of: the cell above + 1, the cell to the left + 1, and the cell diagonally above-left + 0 (same letters) or + 1 (different).

ii. 2. J, U and M are kept; then A and L are in the wrong order, which costs two edits: change A to L and L to A (or delete the A, keep the L, and insert an A at the end). Swapping two letters counts as two edits in this measure.

iii. Finishing earliest is the youth club (9:00). Of those starting at 9:00 or later, the ward committee meeting finishes first (11:00). Of those starting at 11:00 or later, the drawing contest finishes first (13:00); then the savings group (13:00–15:00). Four events: youth club, ward committee meeting, drawing contest, women’s savings group.

iv. Starting earliest is the mothers’ group (7:00–12:00). Then, starting at 12:00 or later, the drawing contest (12:00–13:00), then the savings group (13:00–15:00). Only three events. The long first event blocks four others.

v. The event that finishes earliest leaves the hall free from the earliest possible moment. Whatever event another plan puts first finishes at the same time or later, so swapping it for the earliest-finishing one never makes the rest fit worse; repeating the argument at each step shows the greedy plan fits as many events as any plan can.

i. TP = 32, FN = 18, FP = 44, TN = 406.

• Accuracy = (32 + 406) ÷ 500 = 438 ÷ 500 = 87.6%
• Precision = 32 ÷ (32 + 44) = 32 ÷ 76 = 42%: fewer than half of the flagged reports were really written by AI.
• Recall = 32 ÷ (32 + 18) = 32 ÷ 50 = 64%

ii. English-medium: 18 of the 270 own reports were flagged, 6.7%; precision 21 ÷ (21 + 18) = 21 ÷ 39 = 54%. Nepali-medium: 26 of 180, 14.4%; precision 11 ÷ (11 + 26) = 11 ÷ 37 = 30%. A student from a Nepali-medium school who wrote her own report is more than twice as likely to be flagged, and 7 in 10 of the flagged reports from these students are their own work. Under the plan, they would get zero, and be thought cheats, for nothing they did. The likely cause is the data: the model learned what a person’s writing looks like mostly from fluent English writers, so the plainer English of students writing in their second language looks to it like a machine’s.

iii. One well-argued case (other conclusions earn marks with good reasons): No: not as an automatic zero.

• The cost of each mistake. Here a flag is a punishment: a zero, and an accusation of cheating. So a false alarm is costly, and precision matters: at 42% overall and 30% for Nepali-medium students, most zeros would go to students who did their own work. The 87.6% accuracy hides this, because most reports are the students’ own anyway.
• Fairness. The zeros would fall most on students writing in their second language, who did nothing different. The cure is at the cause: test the model on, and retrain it with, much more writing by students like them, and measure it by group again. A different threshold for them would only move the line on poor scores.
• How it could be used. Only as a reason to talk: a flag means the teacher asks the student, in the viva, to explain the report, its choices and its drafts; the teacher decides, the student is told why and can appeal; nobody gets zero from the model alone. Its results are checked each year by group. Better still, the college can mark the work AI can’t do for the student: the drafts, the viva, and the work done in class.

import heapq FEES = {    "Khotang": {"Bhojpur": 40, "Dhankuta": 90},    "Bhojpur": {"Khotang": 40, "Dhankuta": 35, "Ilam": 120},    "Dhankuta": {"Khotang": 90, "Bhojpur": 35, "Ilam": 60, "Jhapa": 110},    "Ilam": {"Bhojpur": 120, "Dhankuta": 60, "Jhapa": 30},    "Jhapa": {"Dhankuta": 110, "Ilam": 30},    "Kailali": {},}  def cheapest(fees, start, goal):    """The lowest total fee from start to goal, and the branches on the way, or None."""    best = {start: 0}    came_from = {start: None}    done = set()    waiting = [(0, start)]    while waiting:        cost, here = heapq.heappop(waiting)        if here in done:            continue        done.add(here)        if here == goal:            route = [goal]            while came_from[route[-1]] is not None:                route.append(came_from[route[-1]])            return cost, route[::-1]        for there, fee in fees[here].items():            if there not in best or cost + fee < best[there]:                best[there] = cost + fee                came_from[there] = here                heapq.heappush(waiting, (cost + fee, there))    return None  def test_same_branch():    assert cheapest(FEES, "Ilam", "Ilam") == (0, ["Ilam"])  def test_one_step():    assert cheapest(FEES, "Ilam", "Jhapa") == (30, ["Ilam", "Jhapa"])  def test_cheaper_round_about():    # straight from Khotang to Dhankuta costs 90; through Bhojpur, 75    assert cheapest(FEES, "Khotang", "Dhankuta") == (75, ["Khotang", "Bhojpur", "Dhankuta"])  def test_no_way():    assert cheapest(FEES, "Khotang", "Kailali") is None  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(cheapest(FEES, "Khotang", "Jhapa"))

PASS test_same_branchPASS test_one_stepPASS test_cheaper_round_aboutPASS test_no_way4 passed, 0 failed(165, ['Khotang', 'Bhojpur', 'Dhankuta', 'Ilam', 'Jhapa'])

Rs 165, through Bhojpur, Dhankuta and Ilam: cheaper than Khotang → Bhojpur → Dhankuta → Jhapa (Rs 185) or the direct link from Dhankuta (Rs 200 from Khotang).

The first run:

PASS test_one_childFAIL test_two_children gave 4000FAIL test_three_children gave 67001 passed, 2 failed

With two children the second child’s fee is missing altogether, and with three the total is 4,000 + 2,700: the second child (Rs 3,500 less 10%, Rs 3,150) is again left out. The loop on line 4 starts at 2, so it skips position 1, the second child. The first child is already in total, so the loop should start at 1:

def family_fee(fees):    """The monthly total for one family; fees lists each child's fee, the first child first."""    total = fees[0]    for i in range(1, len(fees)):        total = total + fees[i] * 0.9    return round(total)  def test_one_child():    assert family_fee([4000]) == 4000  def test_two_children():    assert family_fee([4000, 3500]) == 7150, f"gave {family_fee([4000, 3500])}"  def test_three_children():    assert family_fee([4000, 3500, 3000]) == 9850, f"gave {family_fee([4000, 3500, 3000])}"  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_one_childPASS test_two_childrenPASS test_three_children3 passed, 0 failed

truth = "---D----DD--D-D------------D-----DDDD-----D-DD-D--"said  = "---D----DD--DDD--------D--DD-----DD-D-D----D---D--"phone = "ONONONOONNNNNOONOOONNONONONONONONNNOOONNNOONOONNOO"  def measure(name, which):    """Counts the outcomes for the photos whose phone letter is in `which`."""    tp = fp = fn = tn = 0    for real, model, kind in zip(truth, said, phone):        if kind not in which:            continue        if real == "D" and model == "D":            tp += 1        elif real == "D":            fn += 1        elif model == "D":            fp += 1        else:            tn += 1    precision = tp / (tp + fp)    recall = tp / (tp + fn)    print(f"{name:9} TP {tp:2}  FP {fp}  FN {fn}  TN {tn:2}  precision {precision:.0%}  recall {recall:.0%}")  measure("All", "ON")measure("Old phone", "O")measure("New phone", "N")

All       TP 10  FP 5  FN 4  TN 31  precision 67%  recall 71%Old phone TP  3  FP 2  FN 4  TN 16  precision 60%  recall 43%New phone TP  7  FP 3  FN 0  TN 15  precision 70%  recall 100%

One limit: “The app found blast in every photo from a newer phone, but in only 3 of the 7 diseased plants photographed on an old phone (43%); and it was tested on only 50 photos, 14 of them with blast, too few to be sure of these numbers.” A farmer it misses doesn’t spray, and blast spreads to the whole field. It needs many more old-phone photos to learn from and be tested on; until then, farmers with old phones should show a doubtful plant to the agriculture officer.

• i.The search asks, again and again, “which branches can I send to from here, and for what fee?”: fees[here] answers it in one lookup, and only the links that exist are stored. A table for a cooperative’s many branches would be mostly empty squares. Each fee is written at both ends because money can move either way along a link: written only at one end, a search starting from the other branch would never see the link.
• ii.By working the totals out from the requirement: two children pay 4,000 + 3,500 × 0.9 = 7,150, which is what the test expects, so the test is right and the code is wrong.
• iii.Accuracy counts all photos together, and most plants were healthy: it hides that the app misses more than half the blast in old-phone photos. Measure each kind of phone apart, collect and label many more old-phone photos, retrain and test again, and send farmers with old phones to the agriculture officer in the meantime.