Final Exam Model Paper 1

• i.**O(n²)**: a loop inside a loop, each going through the list, so it compares every pair, about n² ÷ 2 comparisons.
• ii.5 lakh is 100 times 5,000, so the work grows 100 × 100 = 10,000 times: 2 × 10,000 = 20,000 seconds, about 5½ hours.
• iii.A faster computer divides the time by a fixed number, here 2 (about 2¾ hours), while the work grows with the square of the list: ten times more numbers again would take a hundred times longer. Only a better algorithm changes how the work grows (for example, keeping the numbers seen in a set, O(n)).

from functools import reduce gardens = [("Kanyam", 1200), ("Fikkal", 450), ("Soktim", 800), ("Mai Pokhari", 300)]big = list(filter(lambda g: g[1] >= 500, gardens))names = list(map(lambda g: g[0], big))total = reduce(lambda a, b: a + b, [kg for name, kg in gardens])print(big)print(names)print(total)

[('Kanyam', 1200), ('Soktim', 800)]['Kanyam', 'Soktim']2750

(reduce(lambda total, g: total + g[1], gardens, 0) is also right.)

One good answer: i. A pilot changeover: one branch uses the new program first (keeping its ledgers alongside for the first weeks), then the others, so problems hurt one branch only, and its staff then help train the rest. (Parallel running in every branch is also a good choice: every balance is checked against the ledger, and any difference shows a mistake.)

• ii.With a direct changeover the ledgers stop the day the program starts: if the program has a bug or the balances were entered wrongly, members’ money is wrong and there is nothing to fall back on or compare with.
• iii.Pilot: the other four branches wait longer for the new program, and for a while the branches work in two different ways. (Parallel: every transaction is entered twice, which is double work for busy staff.)

• i.It should be 10,000 + 2,000 + 500 = Rs 12,500; it is Rs 10,500: the Rs 2,000 deposit has vanished.
• ii.A lost update: both transactions read the same balance before either wrote, and each wrote its own result, so the later write overwrote the earlier one.
• iii.The first counter locks the record before reading it; the second must wait until the first commits and lets the lock go. Then it reads 12,000 and writes 12,500.

• i.The sample is self-selected: only people who read that website and chose to answer, often those who feel strongly, so it is biased. Parents without the internet, or who don’t read that site, are left out.
• ii.No. A bigger sample shrinks the chance error, but bias misses in one direction, and more of the same kind of answers misses in the same direction.
• iii.The sampling error shrinks like 1 ÷ √(sample size), so halving it needs four times the sample: 1,600 parents.

The conclusion is not safe. At the 5% level, a difference this big turns up by chance about 1 time in 20 when there is nothing there; with 20 colors tested, about one is expected to look “significant” even if no color makes any difference. Picking the one that “worked” out of many is p-hacking. Besides, p = 0.04 isn’t the chance that orange works, and says nothing about whether 3% matters.
They should test orange again in a new A/B test, with the measure and the size of the test decided in advance (preregistered), and report all 20 tests, not just the one (or use a stricter limit for so many tests).

• i.n = 5 × 11 = 55; φ(n) = (5 − 1)(11 − 1) = 4 × 10 = 40.
• ii.e × d = 3 × 27 = 81 = 2 × 40 + 1, one more than a multiple of φ(n), so d = 27 undoes e = 3.
• iii.c = 8³ mod 55 = 512 mod 55. 9 × 55 = 495, and 512 − 495 = 17, so c = 17. (Decrypting, 17²⁷ mod 55 gives 8 again.)

• Intelligence: what can the system do: solve problems, learn, plan, use language? It can be tested by giving it tasks.
• Consciousness: does it experience anything, such as pain or joy? No agreed test exists.
• Responsibility: who answers for what it does, and can it be wronged? This is decided by people, in ethics and law.

i.

ii. 36 minutes. Following the notes back: Lamachaur came from Bagar, Bagar from Mahendrapul, Mahendrapul from Srijana Chowk, Srijana Chowk from Lakeside: Lakeside → Srijana Chowk → Mahendrapul → Bagar → Lamachaur. (The road straight from Mahendrapul to Lamachaur looked shorter, 39 minutes, but going round by Bagar is 3 minutes quicker.)

iii. Greedy takes the biggest that fits, 5, leaving 3, then 1, 1, 1: 4 coupons (5 + 1 + 1 + 1).

iv. For each amount, try each coupon that fits: that coupon, plus the best for what is left.

v. For 8 the last coupon is a 4, leaving 4, whose last coupon is a 4, leaving 0: 2 coupons, 4 + 4, half as many as greedy.

i. TP = 24, FN = 16, FP = 36, TN = 324.

• Accuracy = (24 + 324) ÷ 400 = 348 ÷ 400 = 87%
• Precision = 24 ÷ (24 + 36) = 24 ÷ 60 = 40%: 2 in 5 flagged students really dropped out.
• Recall = 24 ÷ (24 + 16) = 24 ÷ 40 = 60%: it catches 3 in 5 of those who drop out.

ii. Bazaar wards: 12 ÷ (12 + 3) = 80%. Remote wards: 12 ÷ (12 + 13) = 48%. In the remote wards, where 25 of the 40 dropouts were, it misses more than half of the students who leave: those most in need are the ones it helps least. The overall 60%, and still more the 87% accuracy, hid this gap. The likely cause is the data: fewer, or poorer, records from the remote wards.

iii. One well-argued case (other conclusions earn marks with good reasons): Use it only after the gap is closed, and only to offer help.

• The cost of each mistake. A false alarm costs a teacher’s visit and some support to a family that may not need it: little harm, as long as being flagged never brings shame or a penalty. A miss costs a child’s schooling. So recall matters more than precision here, and 40% precision is acceptable.
• The gap first. As it is, the model would send most visits to the bazaar wards and leave out the remote wards’ children, making an existing inequity worse. Collect better data from the remote wards and retrain it, then measure each group again. A lower threshold for the remote wards could be a short-term step, since a false alarm costs little here, but it only moves the line on scores that are already poor, so it brings many more false alarms; it doesn’t fix the cause.
• How to use it. Teachers decide who is visited, using the flag as one piece of information with what they know (human review); families are told why they are visited, and no one is ever refused support because the model did not flag them; the results are checked each year by ward (drift), with a model card saying what it was tested on, and a way to stop using it.
• (A simpler rule, such as many days absent, could be compared first: if it does as well, it is easier to explain.)

STAMPS = [1, 7, 10, 15]  def fewest_stamps(amount):    """The fewest stamps that make amount exactly, as a list."""    best = [0] + [None] * amount     # best[a]: fewest stamps for a    last = [None] * (amount + 1)     # last[a]: the stamp that does it    for a in range(1, amount + 1):        for stamp in STAMPS:            if stamp <= a and best[a - stamp] is not None:                if best[a] is None or best[a - stamp] + 1 < best[a]:                    best[a] = best[a - stamp] + 1                    last[a] = stamp    given = []    a = amount    while a > 0:        given.append(last[a])        a = a - last[a]    return sorted(given, reverse=True)  def test_nothing():    assert fewest_stamps(0) == []  def test_one_stamp():    assert fewest_stamps(15) == [15]    assert fewest_stamps(1) == [1]  def test_greedy_would_fail():    # greedy gives 10 + 1 + 1 + 1 + 1 for 14: five stamps    assert fewest_stamps(14) == [7, 7], f"14 gave {fewest_stamps(14)}"  def test_sum_is_right():    for amount in range(0, 101):        assert sum(fewest_stamps(amount)) == amount, f"{amount} gave the wrong sum"  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("Rs 21:", fewest_stamps(21))print("Rs 49:", fewest_stamps(49))

PASS test_nothingPASS test_one_stampPASS test_greedy_would_failPASS test_sum_is_right4 passed, 0 failedRs 21: [10, 10, 1]Rs 49: [15, 10, 10, 7, 7]

Rs 21 is 3 stamps (7 + 7 + 7 is also 3, and right); greedy would give 15 and six 1s, seven stamps. Rs 49 is 5 stamps.

The first run:

PASS test_normalFAIL test_boundary 50000 gave 3000PASS test_zero2 passed, 1 failed

The boundary test fails: Rs 50,000 earns 6% (Rs 3,000) instead of 8% (Rs 4,000). The requirement says “Rs 50,000 or more”, so the test is right and the code is wrong: line 3 uses >, which leaves out 50,000 itself. Change it to >=:

def yearly_interest(balance):    """A year's interest in rupees on a savings balance."""    if balance >= 50000:        rate = 8    else:        rate = 6    return round(balance * rate / 100)  def test_normal():    assert yearly_interest(20000) == 1200    assert yearly_interest(120000) == 9600  def test_boundary():    assert yearly_interest(50000) == 4000, f"50000 gave {yearly_interest(50000)}"    assert yearly_interest(49999) == 3000  def test_zero():    assert yearly_interest(0) == 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_normalPASS test_boundaryPASS test_zero3 passed, 0 failed

truth = "--T-----T--TT----------------T-----T--------TT-----T--TT--T-"said  = "T-------T---T----------------T----TT----T---TTT----T--TT----"light = "DNNNNNDDDDDNNDNNDNDNDDDNNNNNDDNDNDNNNNDNNNDDDDDDNDDNDNDDNDND"  def measure(name, when):    """Count the outcomes for the photos taken in `when` (D, N or both)."""    tp = fp = fn = tn = 0    for real, model, l in zip(truth, said, light):        if l not in when:            continue        if real == "T" and model == "T":            tp += 1        elif real == "T":            fn += 1        elif model == "T":            fp += 1        else:            tn += 1    precision = tp / (tp + fp)    recall = tp / (tp + fn)    print(f"{name:6} TP {tp:2}  FP {fp}  FN {fn}  TN {tn:2}  precision {precision:.0%}  recall {recall:.0%}")  measure("All", "DN")measure("Day", "D")measure("Night", "N")

All    TP  9  FP 4  FN 3  TN 44  precision 69%  recall 75%Day    TP  6  FP 2  FN 0  TN 22  precision 75%  recall 100%Night  TP  3  FP 2  FN 3  TN 22  precision 60%  recall 50%

One limit: “By day the model found every tiger, but at night it missed half of them (3 of 6); and it was tested on only 12 tigers, too few to be sure of any of these numbers.” Tigers are often active at night, so night photos matter; the model needs more night photos to learn from and to be tested on.

• i.best[a] holds the fewest stamps for the amount a. Each amount is worked out from smaller amounts only (a − 1, a − 7, a − 10, a − 15), which are already in the list and already the best, so each answer is built from correct smaller answers, and each is worked out once.
• ii.By reading the requirement: it says Rs 50,000 “or more” earns 8%, so the test’s 4,000 is right and the code’s > is wrong. A test is checked against the requirement, not against what the code happens to do.
• iii.Tigers are rare in the photos (12 of 60): a model that said “no tiger” every time would still be 80% accurate. Accuracy is mostly about the common kind; precision and recall say how many tigers it finds and how far to trust its tiger photos. For the night photos: collect and label many more night photos, retrain, and test again by day and night apart.