Computer Science

1. 1.

   Trace this pseudocode: total <- 0; FOR i <- 1 TO 4 inclusive: total <- total + i*i; OUTPUT total. State the output and the time complexity if the upper limit is n.

   [3 marks] · no calculator

   Answer explanation

   Draft walkthroughs are based on marking guidance, not independently verified derivations.

   1. The assignment replaces total with its old value plus the current square.
   2. Include i = 4: 1^2 + 2^2 + 3^2 + 4^2 = 30.
   3. The loop grows linearly with n even though the numerical sum grows faster; output size is not iteration count.

   Marking points

   • Successive totals are 1, 5, 14 and 30.
   • The output is 30.
   • There are n constant-time iterations, so time complexity is O(n).

   Examiner tip: Do not confuse the square in the arithmetic with quadratic algorithmic complexity.

2. 2.

   Define f(n): IF n = 0 RETURN 1; ELSE RETURN n*f(n - 1). For integer n >= 0, find f(4), explain the base case and state the extra stack-space complexity.

   [4 marks] · no calculator

   Answer explanation

   Draft walkthroughs are based on marking guidance, not independently verified derivations.

   1. Expand the recursive calls until f(0), then return upward through the pending multiplications.
   2. Returning 0 at the base case would multiply the entire result by zero; 1 is the multiplicative identity.
   3. Each unfinished multiplication keeps a stack frame alive. This is not tail recursion because work remains after the recursive call.

   Marking points

   • f(4) = 4 x 3 x 2 x 1 x 1 = 24.
   • The base case f(0) = 1 stops further recursion.
   • Each call reduces n towards zero, so valid inputs terminate.
   • There are O(n) simultaneous stack frames without tail-call optimisation.

   Examiner tip: A base case must be reachable. Inputs outside the specified nonnegative integer domain need validation.

3. 3.

   A tutoring app has one remaining seat. Two users both read seats = 1, then each confirms a booking and writes seats = 0. Explain the fault and propose a database-level solution that prevents overbooking.

   [4 marks] · no calculator

   Answer explanation

   Draft walkthroughs are based on marking guidance, not independently verified derivations.

   1. The two reads happen before either write, so both users believe the seat is available. Merely refreshing the UI cannot guarantee correctness.
   2. An atomic operation makes checking and changing availability indivisible. Exactly one update can change 1 to 0.
   3. Keep the successful decrement and booking insert in one transaction so an insert failure cannot consume the seat without a booking.

   Marking points

   • A race condition lets both decisions use the same stale availability.
   • The final count of zero hides the fact that two bookings were created.
   • Use a transaction with row locking or an atomic conditional decrement where seats > 0.
   • Only create/confirm a booking if the guarded update succeeds, committing both changes together; otherwise reject or retry safely.

   Examiner tip: A transaction alone is not enough unless its locking, isolation or conditional-update behaviour actually prevents the race.

Original, unofficial practice questions from SubjectScout — not official past-paper questions.