50 minutes. Self-marked against the rubric. 14 marks. In the full course this counts toward the labs and cases share (15% of the course grade). Write your answers in the boxes, then open the model answer and tick each mark you earned honestly. Nothing is sent or stored.
Scenario (invented)
A school office (invented) wants to check a class list for duplicate names. Method P compares every pair of names. Method S first sorts the list and then compares each name with the next one, which takes n − 1 comparisons after sorting. For this lab, treat the sort as costing about n × n ÷ 2 comparisons.
Tasks
Task 1 (4 marks)
Use n × (n − 1) ÷ 2 to count the comparisons of method P for n = 10, n = 100 and n = 1,000.
Private: nothing you type here is sent or stored.
Task 2 (3 marks)
Method P takes 4,950 comparisons at n = 100. Estimate its cost at n = 200 and state the growth rate.
Private: nothing you type here is sent or stored.
Task 3 (4 marks)
Using the lab assumption, compute the total cost of method S (sort cost plus n − 1) for n = 100, and compare it with method P at n = 100.
Private: nothing you type here is sent or stored.
Task 4 (3 marks)
State what limits this comparison, and what you would measure before recommending a method for a real school.
Private: nothing you type here is sent or stored.
Rubric and model answer
Task 1: count pairs (4 marks)
Model: n = 10: 10 × 9 ÷ 2 = 45. n = 100: 100 × 99 ÷ 2 = 4,950. n = 1,000: 1,000 × 999 ÷ 2 = 499,500.
Task 2: predict doubling (3 marks)
Model: the growth is quadratic, so doubling n roughly quadruples the cost: about 4 × 4,950 = 19,800. (The exact value is 19,900.)
Task 3: method S (4 marks)
Model: S: 100 × 100 ÷ 2 = 5,000, plus 99 gives 5,099. P: 4,950. At n = 100 the two are close and P is slightly cheaper.
Task 4: recommend (3 marks)
Model: the sort cost was an assumption and the numbers are invented. Real class lists are small, so either method is fine; I would measure the real list sizes and the real sort used, and choose the simpler method unless lists grow into the thousands.
Marks so far: 0 of 14