Algorithms

Sample questions

Original practice questions written in the style of the exam.

1. Question 13 marks

   Carry out the first pass of a bubble sort to arrange the list below into ascending order.

   23	17	31	12	25	9

   Write down the list after the first pass, and state the number of comparisons and the number of swaps made.

   Mark scheme

   • List after pass 1: 17, 23, 12, 25, 9, 31 (1)
   • 5 comparisons (1)
   • 4 swaps (1)
2. Question 25 marks

   Eleven boxes, with the heights (in cm) below, are to be stacked in piles of height at most $20\,\text{cm}$.

   8	7	14	9	6	9	5	15	6	7	8

   (a) Calculate a lower bound for the number of piles needed.

   (b) Use the first-fit decreasing algorithm to allocate the boxes to piles.

   (c) Explain whether your answer to (b) is optimal.

   Mark scheme

   • (a) $\dfrac{94}{20} = 4.7$, so the lower bound is 5 piles (1)
   • (b) M1 Sorted into decreasing order: 15, 14, 9, 9, 8, 8, 7, 7, 6, 6, 5 (1)
   • M1 First-fit applied, each item in the first pile with room (1)
   • A1 Piles: [15, 5], [14, 6], [9, 9], [8, 8], [7, 7, 6] (1)
   • (c) 5 piles equals the lower bound, so the solution is optimal (1)