⏱️ Duration: 75 minutes | Total: /60 marks
Show all work. Code answers must be syntactically valid Python 3. No internet, no AI tools.
K/U
/15
Thinking
/15
Comm.
/15
Applic.
/15
Part A: Knowledge & Understanding [15 marks]
1. [2 marks]
State the worst-case Big-O complexity of each:
Linear search
Binary search
Bubble sort
Merge sort
2. [3 marks]
Trace bubble sort (ascending) on [6, 3, 8, 1, 5]. Show the list state after EACH complete pass through the list.
3. [2 marks]
Trace binary search for the value 23 in the sorted list [2, 5, 8, 12, 17, 23, 29, 31, 40]. Show lo, hi, and mid at each step.
4. [2 marks]
If a list has 1,000,000 elements, approximately how many comparisons does binary search use in the worst case?
5. [3 marks]
A program does this:
for i in range(n):
for j in range(n):
for k in range(n):
do_something()
What is the Big-O complexity? Justify briefly.
6. [3 marks]
Trace selection sort (ascending) on [20, 5, 12, 3, 9]. Show the list after EACH selection (3 passes).
Part B: Thinking & Investigation [15 marks]
7. [5 marks]
Find & fix the bugs. The binary search below has three bugs. Provide the corrected function.
def binary_search(arr, target):
lo, hi = 0, len(arr)
while lo < hi:
mid = (lo + hi) / 2
if arr[mid] == target:
return False
elif arr[mid] < target:
lo = mid - 1
else:
hi = mid + 1
return -1
8. [5 marks]
Implement insertion sort from scratch in Python (ascending). Then describe in 2-3 sentences why insertion sort is O(n²) in the worst case but O(n) on a nearly-sorted list.
9. [5 marks]
A team needs to find the k-th largest mark in a list of student grades (e.g., the 5-th highest). Compare two strategies:
Sort the list (descending) and pick index k-1.
Repeat k times: scan for the maximum and remove it.
What is the Big-O of each? When would each be preferable? (3-4 sentences.)
Part C: Communication [15 marks]
10. [5 marks]
Explain the divide-and-conquer principle as it applies to merge sort. Use a small example (4-element list). Include: dividing, conquering (recursion), and combining (merging). Use diagrams or trees if helpful.
11. [5 marks]
A peer says: "Big-O notation is just academic theory — in practice, code that runs fast on my laptop is what matters." Write a clear, respectful response (3-5 sentences) explaining why algorithm analysis matters in industry, with a concrete example involving large inputs.
12. [5 marks]
Add high-quality comments to this merge function so a peer can understand each step.
def merge(left, right):
out = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
out.append(left[i])
i += 1
else:
out.append(right[j])
j += 1
out.extend(left[i:])
out.extend(right[j:])
return out
Part D: Application [15 marks]
13. [5 marks]
Write a function linear_search(arr, target) that returns the FIRST index of target in arr, or -1 if not found. Then write linear_search_all(arr, target) that returns a list of ALL indices.
14. [5 marks]
A library tracks borrowed books as a list of dicts: [{"title":..., "borrower":..., "due":...}, ...]. Write a function overdue(books, today) that returns the books due before today (a string like "2026-05-07"), sorted ascending by due date. You may use Python's built-in sorted().
15. [5 marks]
Algorithm comparison — experiment design. Describe (do not implement) an experiment to empirically verify that bubble sort is O(n²). Include:
What variables you would change.
What you would measure.
What graph you would produce.
What pattern in the graph would confirm O(n²).
One source of measurement error and how you would mitigate it.