Final Exam Model Paper 5

• i.O(n): one loop, one step for each house.
• ii.O(log n): each time round, the part of the list still to search is halved, so even a million houses need only about 20 rounds.
• iii.O(n), though it is a loop inside a loop: the inner loop always runs 12 times, whatever n is, so the work is 12 × n steps, and a fixed number like 12 is dropped in big O.

i. It changes a global variable, total (line 5), and it prints (line 6).
ii.

def day_total(sales):    """The total of a day's sales: a list of (price, quantity) pairs."""    return sum(price * quantity for price, quantity in sales)  print(day_total([(120, 3), (25, 2), (450, 1)]))print(day_total([]))

8600

iii. Its answer depends only on its argument: call it with a list worked out by hand, compare, and it is done. There is nothing to set up or reset first (such as total left over from an earlier test), and calling it twice gives the same answer.

• i.Corrective: it fixes a fault, something the app should already do but doesn’t.
• ii.Adaptive: the app is changed to fit a change around it (the new server and its Python), though nothing in the app was wrong before.
• iii.Perfective: it makes a working app better, with a feature its users asked for.

• i.Each phone keeps sending, so the slow server gets ever more requests, many of them for payments already waiting: a retry storm. The extra load keeps it slow, or makes it fail, long after the first problem is over.
• ii.Each try waits twice as long as the one before (1 s, 2 s, 4 s, 8 s…), so the load from tries again falls quickly and the server has room to recover.
• iii.Phones that failed together would otherwise try again together, at the same moments, in waves. Jitter, a small random addition to each wait, spreads their tries out.

• i.Small shops, street sellers and stalls that never registered are left off the list, and their year may have been quite different.
• ii.Only 180 of 500 answered. Shopkeepers who answer the phone on a weekday morning may be those with fewer customers, or those keen to talk about a good year; those too busy, or doing badly, may not answer. If those who answer differ from those who don’t, the 70% is biased, and a bigger sample of the same kind doesn’t fix it.
• iii.Choose shops at random from a fuller list (for example, by walking every market street in chosen areas, unregistered shops included), call at different times or visit in person, go back to those who didn’t answer, and report how many answered.

The evidence doesn’t support it. The 4 marks is one estimate, and its 95% interval runs from −2 to +10: it includes 0, and even differences in favor of the old way. Chance alone, in which students happened to be in which class, could give a gap of 4, so the data can’t show that the method helps (or that it doesn’t).
Besides, the two classes weren’t chosen at random: they had their own teachers, times of day and students, and any of these (a confounder) could explain the gap, so even a clear difference couldn’t be put down to the method.
A fairer test: try it in many classes, with chance deciding which classes use the new method, the test and the measure decided in advance, and report the difference with its interval. Change every class only if the interval is clearly above 0 and the gain is worth the work.

• i.The powers of 2, mod 19, each the last one doubled: 2¹ = 2, 2² = 4, 2³ = 8, 2⁴ = 16, 2⁵ = 32 ≡ 13, 2⁶ ≡ 26 ≡ 7, 2⁷ ≡ 14. So a = 7, after 7 tries.
• ii.The key is Bᵃ = 15⁷ mod 19: 15² = 225 ≡ 16 (225 − 209); 15⁴ ≡ 16² = 256 ≡ 9 (256 − 247); 15⁷ = 15⁴ × 15² × 15 ≡ 9 × 16 × 15 = 2,160 ≡ 13 (2,160 − 2,147). The shared key is 13.
• iii.Eve’s only method is trying the powers one by one (the discrete logarithm problem). With p = 19 there are at most 18 to try; with a prime hundreds of digits long there are more than there are atoms in the universe, and no fast method is known. Nisha and Kamal, who each know their own secret, need only a few hundred multiplications by repeated squaring.

• Moravec’s paradox: things that are hard for people, like long arithmetic or chess, are often easy for computers, while things a small child does without thinking, like seeing, walking and picking up a cup, are very hard for them.
• Example: a program beat the world chess champion in 1997, but a robot that can walk into an unfamiliar kitchen and make a cup of tea is still very hard to build.
• Narrow AI is good at one kind of task (reading digits, translating, playing Go); artificial general intelligence would learn and do almost any task a person can.

i.

Quickest delays: Ward 1 2 ms, Ward 3 3 ms, Ward 2 5 ms, Ward 4 6 ms, Ward 5 9 ms.

ii. 9 ms, M → Ward 2 → Ward 5 (Ward 5 came from Ward 2, Ward 2 from M).

iii. From M the quickest link is to Ward 1 (2); from Ward 1, to Ward 3 (1); from Ward 3, to Ward 4 (3, quicker than Ward 5’s 10); from Ward 4, to Ward 2 (6, quicker than Ward 5’s 9); from Ward 2, to Ward 5 (4). M → Ward 1 → Ward 3 → Ward 4 → Ward 2 → Ward 5: 2 + 1 + 3 + 6 + 4 = 16 ms, nearly twice the quickest.

iv. The trainee chooses by one link at a time, without counting the delay already spent or where the route leads, so a cheap first link (M – Ward 1) can lead far from the goal. Dijkstra’s algorithm chooses by the whole delay from M: the nearest waiting office can’t be reached more quickly some other way, because any other way passes through an office already waiting at least as far away, and more links can only add delay. That holds only if no link has a negative delay, which is true of delays, distances and fees.

i.

• 0.3: precision 36 ÷ (36 + 160) = 36 ÷ 196 = 18%; recall 36 ÷ 40 = 90%.
• 0.5: precision 30 ÷ (30 + 40) = 30 ÷ 70 = 43%; recall 30 ÷ 40 = 75%.
• 0.7: precision 20 ÷ (20 + 5) = 20 ÷ 25 = 80%; recall 20 ÷ 40 = 50%.

ii. Smartphone app: 22 of 1,470 normal accounts flagged, 1.5%; recall 25 ÷ 30 = 83%. Basic phone: 18 of 490, 3.7%; recall 5 ÷ 10 = 50%. A basic-phone user with an honest account is about two and a half times as likely to be frozen, and their account is half as well protected from fraud: worse on both counts. Basic-phone users are often older or live far from a branch, so a freeze costs them most. The model probably learned mostly from app users’ data.

iii. One well-argued case (other conclusions earn marks with good reasons): Not automatic freezing; a check by a person, with a different threshold for each action.

• The cost of each mistake. A freeze is a punishment for an honest owner: no money for days and a trip to a branch with documents. At 0.5, 40 honest owners are frozen to catch 30 frauds (more than half the freezes are wrong); at 0.3, 160. Only at 0.7 are most flags right (80%), but then half the fraud gets through.
• Two actions, two thresholds. Above 0.7, hold the payment and call the owner at once (precision 80%); between 0.3 and 0.7, send the account to a fraud officer to look at before anything happens, or ask the owner to confirm the payment by a call or code. That catches most fraud (recall up to 90%) while few honest owners are stopped without a person checking.
• The gap first. Before using it for basic-phone users, collect and label more of their accounts and retrain, then measure by group again; until then, no account is frozen on the model alone. Owners are told why and can get a quick review by phone (appeal), the numbers are checked by group every month (fraud changes: drift), and there is a way to switch it off.

import itertoolsimport random REQUESTS = [    ("Coding club", 7, 9),    ("Robotics club", 8, 12),    ("Typing practice", 9, 10),    ("Web design", 10, 12),    ("Grade 6 Scratch", 11, 13),    ("Chess club", 12, 14),    ("Photo editing", 13, 15),    ("Teacher training", 14, 16),]  def most_sessions(requests):    """The most sessions that fit in the lab, one at a time: always the one that finishes earliest."""    chosen = []    free_from = None    for name, start, end in sorted(requests, key=lambda r: r[2]):        if free_from is None or start >= free_from:            chosen.append(name)            free_from = end    return chosen  def best_count(requests):    """The most sessions that fit, found by trying every set of requests (slow, but sure)."""    for size in range(len(requests), 0, -1):        for group in itertools.combinations(requests, size):            times = sorted((start, end) for name, start, end in group)            if all(times[i][1] <= times[i + 1][0] for i in range(len(times) - 1)):                return size    return 0  def test_empty():    assert most_sessions([]) == []  def test_long_first_session():    # starting earliest would take the long one and fit only 1    assert most_sessions([("Long", 7, 15), ("A", 8, 9), ("B", 9, 10)]) == ["A", "B"]  def test_back_to_back():    assert most_sessions([("A", 7, 8), ("B", 8, 9)]) == ["A", "B"]  def test_matches_best():    random.seed(1)    for trial in range(200):        requests = []        for i in range(6):            start = random.randint(7, 15)            requests.append((str(i), start, start + random.randint(1, 3)))        assert len(most_sessions(requests)) == best_count(requests), f"{requests}"  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(most_sessions(REQUESTS))print("Best possible:", best_count(REQUESTS))

PASS test_emptyPASS test_long_first_sessionPASS test_back_to_backPASS test_matches_best4 passed, 0 failed['Coding club', 'Typing practice', 'Web design', 'Chess club', 'Teacher training']Best possible: 5

The greedy choice fits 5 sessions, and trying every set confirms that 5 is the most. best_count is sure but slow (it may try every one of the 2ⁿ sets), so it is used only to test the fast method on small lists.

The first run:

PASS test_one_studentFAIL test_class gave AaravPASS test_low_marks2 passed, 1 failed

Binita has 10, the highest, but Aarav’s 9 wins. The marks split from each line are text, not numbers, so line 9 compares them as text, character by character: "9" > "10", because the character 9 comes after the character 1. The other tests passed only because all their marks have one digit. Turn each mark into a number before comparing:

QUIZ = "Aarav,9\nBinita,10\nChirag,7\nDiksha,8"  def top_student(text):    """The name with the highest mark; each line is name,mark (marks out of 10)."""    best_name, best_mark = None, None    for line in text.split("\n"):        name, mark = line.split(",")        mark = int(mark)                 # a number, not text        if best_mark is None or mark > best_mark:            best_name, best_mark = name, mark    return best_name  def test_one_student():    assert top_student("Aarav,9") == "Aarav"  def test_class():    assert top_student(QUIZ) == "Binita", f"gave {top_student(QUIZ)}"  def test_low_marks():    assert top_student("Chirag,7\nDiksha,8") == "Diksha"  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_studentPASS test_classPASS test_low_marks3 passed, 0 failed

truth  = "--D--D----D--DD-DD--D----D-----D---D---D-D--D-D--D---D------"said   = "-----DD------DD-D---D----D---------D--DD----D----D---D-----D"script = "NRRNRRNRNNNRRRRRRNNRNNNNRRRNRNNNRNNRNRRRRNRNRRNNRNNNRNRNNNRR"  def measure(name, which):    """Counts the outcomes for the pairs whose names are written in `which`."""    tp = fp = fn = tn = 0    for real, model, s in zip(truth, said, script):        if s 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:11} TP {tp:2}  FP {fp}  FN {fn}  TN {tn:2}  precision {precision:.0%}  recall {recall:.0%}")  measure("All", "NR")measure("Roman", "R")measure("Devanagari", "N")

All         TP 11  FP 3  FN 6  TN 40  precision 79%  recall 65%Roman       TP  8  FP 2  FN 1  TN 19  precision 80%  recall 89%Devanagari  TP  3  FP 1  FN 5  TN 21  precision 75%  recall 38%

One limit: “The model found 8 of the 9 double registrations written in Roman letters, but only 3 of the 8 written in Devanagari (38%); and it was tested on only 17 double registrations, too few to be sure.” Names in Devanagari can be spelled in more than one accepted way, which the model may not have learned. Until it does better, the secretary should check the Devanagari records by hand.

• i.Each request is either in a set or not, so 8 requests have 2⁸ = 256 sets, and 60 have 2⁶⁰, about 10¹⁸: at a billion sets a second, more than 30 years. So it is useless for a real term. But it is sure, and on small lists it is quick, so it is the method known to be right that the fast greedy choice is tested against, on many random lists: the evidence that greedy really works.
• ii.All their marks have one digit, and for one-digit numbers comparing as text gives the same order as comparing as numbers. Only a test with 10 shows the bug: tests must include values where the code could go wrong (here, more digits).
• iii.Most pairs are not double registrations, so accuracy is mostly about them; it hides that 5 of the 8 Devanagari double registrations were missed, each one an allowance paid twice. Measure each script apart, test on more Devanagari pairs, find why (spellings), improve and test again, and check those records by hand meanwhile.