Computer Science

1. 1.

   Trace a linear search for 7 in [4, 9, 7, 2], scanning left to right and stopping at the first match. State zero-based index and comparison count.

   [3 marks] · no calculator

   Answer explanation

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

   1. Start at index zero and advance only after a mismatch. The match at the third element stops the search, so the final element is not compared.

   Marking points

   • Values compared are 4, 9 and 7.
   • Returned index = 2.
   • There are 3 equality comparisons.

   Examiner tip: Distinguish position three from zero-based index two.

2. 2.

   Explain the precondition for binary search and why applying it directly to [8, 2, 9, 1] can miss an existing value.

   [3 marks] · no calculator

   Answer explanation

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

   1. Binary search's efficiency rests on a proof that all values in one half are too small or too large. An unsorted list lacks that property, making the elimination logically unjustified.

   Marking points

   • The sequence must be ordered consistently with the comparison.
   • Each comparison eliminates a half based on that ordering.
   • In an unsorted sequence the discarded half can contain the target.

   Examiner tip: Random access helps implementation speed but does not replace the sorted-order precondition.

3. 3.

   Binary-search [3, 7, 11, 15, 19, 23, 27] for 23 with inclusive bounds and mid = floor((low+high)/2), zero-based indexing. Record midpoint indices until found.

   [3 marks] · no calculator

   Answer explanation

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

   1. Initially low=0 and high=6. Since 15 is too small, discard indices through three; the midpoint of four through six is five and matches immediately.

   Marking points

   • First midpoint = 3, value 15.
   • Then low = 4 and midpoint = 5, value 23.
   • Found at index 5 after 2 midpoint comparisons.

   Examiner tip: Updating low to mid instead of mid+1 can prevent progress.

4. 4.

   Perform insertion sort on [5, 2, 4, 1], inserting each next item into the sorted prefix. Give the array after each outer pass.

   [3 marks] · no calculator

   Answer explanation

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

   1. Save the next item, shift larger prefix elements right, then place it in the gap. Each pass grows the sorted prefix by one while preserving the unprocessed suffix.

   Marking points

   • After inserting 2: [2, 5, 4, 1].
   • After inserting 4: [2, 4, 5, 1].
   • After inserting 1: [1, 2, 4, 5].

   Examiner tip: Report outer-pass states, not just the final sorted list.

5. 5.

   An algorithm runs FOR i=1 TO n and inside it FOR j=1 TO i, performing one operation per inner iteration. Derive operation count and time complexity; evaluate whether doubling n exactly quadruples the count.

   [4 marks] · no calculator

   Answer explanation

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

   1. The inner bound depends on i, so the iteration space is triangular, not n by n. Compare the exact polynomial at n and 2n before taking its large-n leading-term approximation.

   Marking points

   • Count = 1 + 2 + ... + n.
   • Count = n(n+1)/2.
   • Time is Theta(n^2).
   • The ratio is 2(2n+1)/(n+1), approaching 4 but not exactly 4 for finite positive n.

   Examiner tip: Asymptotic scaling is not an exact finite-input equality.

6. 6.

   Prove that a left-to-right algorithm storing the largest value seen returns the maximum of a nonempty array. Include initialisation, maintenance and termination, and explain why initialising largest to zero is unsafe.

   [4 marks] · no calculator

   Answer explanation

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

   1. The invariant states exactly what the stored value means after each processed element. Starting with an actual member establishes it, comparing one new member preserves it, and exhausting the array proves the postcondition.

   Marking points

   • Initialise largest to the first element; it is the maximum of the first-element prefix.
   • For each next value, replace largest only if the value is greater, preserving the prefix-maximum invariant.
   • At termination the prefix is the whole array, so largest is the overall maximum.
   • Zero initialisation fails for an all-negative array because zero may not be an element.

   Examiner tip: A correctness proof needs the nonempty precondition as well as a loop description.

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