Revision Library

revisionlibrary.co.uk

A-Level · Further Decision 1 (Algorithms, Sorting and Bin Packing)

FP.D1 Decision Maths: Algorithms, Sorting and Bin Packing

AQA 7367 · Calculator allowed · about 130 minutes

Total Marks

Name: _______________________________ Date: ____ / ____ / ______

Answer ALL questions. Show all your working.

The following list of seven numbers is to be sorted into ascending order:
58, 23, 91, 12, 67, 45, 34

(a)Perform a bubble sort on the list to sort it into ascending order. Show the list in full after each pass, and continue until you have completed one full pass in which no swaps are made.(4)

(b)State the total number of passes needed and the total number of comparisons made across all of these passes.(2)

(c)State the total number of swaps made during the whole sort, and explain why a bubble sort must include a final pass with no swaps before you can be certain the list is fully sorted.(2)

(Total for Question 1 is 8 marks)

This question compares how a bubble sort performs on the same set of six numbers arranged in two different orders.

(a)The marks (out of 60) scored by six students in a Further Maths mock exam are recorded in the order the papers were marked: 36, 14, 58, 22, 41, 9. Sort this list into ascending order using a bubble sort, showing the list in full after each pass. Continue until a pass with no swaps occurs, and state the total number of passes and the total number of swaps used.(5)

(b)The same six marks are instead given in the order 9, 14, 22, 36, 58, 41. Sort this list into ascending order using a bubble sort, showing the list after each pass, and state the number of passes needed this time.(3)

(c)By comparing your answers to parts (a) and (b), explain what this shows about the best-case and worst-case performance of a bubble sort on a list of n items.(2)

(Total for Question 2 is 10 marks)

A courier drives to eight different addresses in one shift. The distances, in miles, driven to reach each address, in the order the deliveries were planned, are:
34, 12, 55, 8, 41, 27, 63, 19

(a)Using the first item of each sublist as the pivot, perform a quicksort on this list to sort it into ascending order. At each stage, state the pivot used and the two resulting sublists (items less than the pivot, and items greater than or equal to the pivot). Continue until every sublist contains at most one item, then write out the final sorted list.(5)

(b)State the total number of comparisons used to complete the sort, given that each non-pivot item in a sublist is compared exactly once with that sublist's pivot.(2)

(c)State one advantage and one disadvantage of always choosing the first item of a sublist as the pivot, compared with other pivot-selection methods.(2)

(Total for Question 3 is 9 marks)

The following list shows the scores (out of 100) achieved by seven contestants in a coding competition:
72, 55, 89, 41, 67, 60, 78

(a)Using median-of-three pivot selection (at each stage, compare the first, middle and last items of the current sublist, and choose whichever of these three values is the median as the pivot), perform a quicksort on this list to sort it into ascending order. At each stage, state the three items compared, the pivot chosen, and the two resulting sublists. Write out the final sorted list.(5)

(b)Give one reason why choosing the pivot by the median-of-three method, rather than always using the first item of the sublist, can improve the efficiency of a quicksort, and describe a type of list for which this improvement is most noticeable.(2)

(Total for Question 4 is 7 marks)

Chidi works for a small courier company. On one shift, he must load parcels of the following weights, in kg, into delivery bins that can each hold a maximum of 10 kg:
6, 5, 4, 7, 3, 8, 2, 5

Figure (to be drawn): A row of numbered bins (crates), each labelled with capacity 10 kg, into which weights are packed in sequence.

(a)Apply the first-fit algorithm to the parcels in the order given, packing them into bins of capacity 10 kg. For each bin, show which parcels it contains. State the number of bins used.(4)

(b)Calculate the theoretical lower bound for the number of bins needed for this set of parcels, and compare it with your answer to part (a).(2)

(Total for Question 5 is 6 marks)

This question continues from question 5, using the same eight parcel weights and the same 10 kg bin capacity.

(a)Re-order Chidi's parcel weights into decreasing order of size, then apply the first-fit algorithm to this re-ordered list (this is called first-fit decreasing). Show the contents of each bin, and state the number of bins used.(3)

(b)State whether first-fit decreasing has achieved the lower bound found in question 5(b), and explain why sorting the weights into decreasing order before applying first-fit can reduce the number of bins needed, compared with using first-fit on the original order.(2)

(Total for Question 6 is 5 marks)

Freya, an art technician at a secondary school, has eight tins of paint with the following volumes, in litres, to store in crates that can each hold a maximum of 10 litres:
8, 2, 7, 3, 6, 4, 5, 5

(a)Calculate the theoretical lower bound for the number of crates needed to hold all eight tins.(2)

(b)Use a full-bin method: starting with the largest unallocated tin each time, try to find one or more other tins whose volumes sum to exactly fill the remaining space in that crate. Show the contents of each crate you form.(4)

(c)Compare your answer to part (b) with your lower bound in part (a), and state what this shows about this particular set of tin volumes.(1)

(Total for Question 7 is 7 marks)

Tomasz is helping his family move house. Some of the boxes have the following weights, in kg, and must be packed into crates that can each hold a maximum of 9 kg:
6, 5, 6, 5, 6, 6, 5, 5

(a)Calculate the theoretical lower bound for the number of boxes needed to pack these items.(2)

(b)Sort the list of weights into decreasing order and apply first-fit decreasing, packing into crates of capacity 9 kg. Show the contents of each crate, and state the number of crates used.(3)

(c)Explain why no packing method, including first-fit decreasing, can achieve the lower bound found in part (a) for this particular set of weights.(2)

(Total for Question 8 is 7 marks)

This question is about determining the order of an algorithm from timed test results.

(a)Ravi times how long Algorithm 1 takes to run on lists of different sizes, n. His results are shown below.

n = 10, time = 8 ms
n = 20, time = 32 ms
n = 40, time = 128 ms
n = 80, time = 512 ms

Use a doubling ratio test (comparing the run time each time n doubles) to estimate the order of Algorithm 1, giving your answer in the form O(n^k).(3)

(b)Ravi also tests Algorithm 2, obtaining the results below.

n = 5, time = 4 ms
n = 10, time = 32 ms
n = 20, time = 256 ms

Use the same method to estimate the order of Algorithm 2.(2)

(c)A third algorithm has order O(n). It takes 15 ms to process a list of 200 items. Estimate how long it would take this algorithm to process a list of 800 items, showing your reasoning.(2)

(Total for Question 9 is 7 marks)

The following pseudocode describes an algorithm applied to a list of n numbers:

Step 1: Let List = [a list of n numbers]
Step 2: Let Max = List(1), Min = List(1)
Step 3: For i = 2 to n
Step 4: If List(i) > Max then Max = List(i)
Step 5: If List(i) < Min then Min = List(i)
Step 6: Next i
Step 7: Let Range = Max - Min
Step 8: Output Max, Min, Range

(a)State, in your own words, what this algorithm calculates for a given list of n numbers.(1)

(b)Trace this algorithm for List = [23, 45, 12, 67, 34, 9, 58], recording the values of Max and Min after each value of i from 2 to 7 is considered. Present your working as a trace table.(3)

(c)State the values output by the algorithm for Max, Min and Range.(1)

(d)State the order of this algorithm in terms of n, the number of items in the list, and justify your answer.(2)

(Total for Question 10 is 7 marks)

This question uses known comparison-count formulas to compare the efficiency of a bubble sort and a quicksort as the size of the list, n, grows large.

(a)The number of comparisons made by a bubble sort in the worst case, on a list of n items, is given by n(n - 1)/2. Calculate the worst-case number of comparisons for (i) n = 50, (ii) n = 200, (iii) n = 1024.(3)

(b)Given that n increased by a factor of 4 between parts (a)(i) and (a)(ii), show that the ratio of your two answers is consistent with the bubble sort's worst-case order of O(n²).(2)

(c)A quicksort, on average, makes approximately n log2(n) comparisons to sort a list of n items. Calculate the approximate number of comparisons a quicksort would make, on average, to sort a list of n = 1024 items.(2)

(d)By comparing your answer to part (c) with your answer to part (a)(iii), comment on the practical significance, for large n, of the difference in order between an O(n log n) algorithm and an O(n²) algorithm.(2)

(Total for Question 11 is 9 marks)

Aisha runs a small office-relocation company. For one client's move, the following box weights, in kg, must be packed into crates that can each hold a maximum of 20 kg, in the order the boxes are brought out of the office:
12, 9, 14, 7, 11, 8, 15, 6, 13, 10

Figure (to be drawn): A loading bay with a stack of ten labelled boxes and a row of crates awaiting packing.

(a)Calculate the theoretical lower bound for the number of crates needed.(2)

(b)Apply first-fit to the weights in the order given, packing into crates of capacity 20 kg. Show the contents of each crate, and state the number of crates used.(3)

(c)Sort the weights into decreasing order and apply first-fit decreasing, packing into crates of capacity 20 kg. Show the contents of each crate, and state the number of crates used.(3)

(d)Using a full-bin method, find as many crates as possible that can be exactly filled from the original ten weights, and state which items (if any) cannot be paired to exactly fill a crate.(3)

(e)Comment on what your answers to parts (b) to (d) show about the effectiveness of first-fit, first-fit decreasing and the full-bin method for this particular set of data.(2)

(Total for Question 12 is 13 marks)

Mark scheme · FP.D1 Decision Maths: Algorithms, Sorting and Bin Packing

Question 1

(a) M1 correct method for pass 1: at least 4 of the 6 adjacent comparisons and resulting swaps correctly applied, e.g. list becomes 23, 58, 12, 67, 45, 34, 91 oe
(a) A1 passes 2 and 3 both fully correct: 23, 12, 58, 45, 34, 67, 91 then 12, 23, 45, 34, 58, 67, 91
(a) A1 pass 4 fully correct, giving the sorted list 12, 23, 34, 45, 58, 67, 91 cao
(a) B1 a further (5th) pass shown in which no swaps occur, confirming the list is fully sorted
(a) Answer: Pass 1: 23, 58, 12, 67, 45, 34, 91. Pass 2: 23, 12, 58, 45, 34, 67, 91. Pass 3: 12, 23, 45, 34, 58, 67, 91. Pass 4: 12, 23, 34, 45, 58, 67, 91. Pass 5 (check): 12, 23, 34, 45, 58, 67, 91 (no swaps).
(b) B1 5 passes cao
(b) B1 30 comparisons cao (ft from their number of passes: 6 comparisons per pass)
(b) Answer: 5 passes; 30 comparisons.
(c) B1 12 swaps cao (5 + 3 + 3 + 1 + 0)
(c) B1 a pass with no swaps means every adjacent pair in the list is already in the correct order, so no further pass can change the list, confirming it is sorted (oe)
(c) Answer: 12 swaps in total. A pass with no swaps confirms every adjacent pair is correctly ordered, so the list cannot change further and must be sorted.

Question 2

(a) M1 pass 1 correct: 14, 36, 22, 41, 9, 58 oe
(a) A1 passes 2 to 5 all correct, reaching the sorted list 9, 14, 22, 36, 41, 58
(a) B1 a further (6th) pass shown with no swaps, confirming the list is sorted
(a) B1 6 passes stated cao
(a) B1 9 swaps stated cao (ft from their trace)
(a) Answer: Sorted list: 9, 14, 22, 36, 41, 58. 6 passes; 9 swaps.
(b) M1 pass 1 correct: identifies that only 58 and 41 are out of order, giving 9, 14, 22, 36, 41, 58
(b) A1 pass 2 shown with no swaps, confirming the list is sorted
(b) B1 2 passes stated cao
(b) Answer: Sorted list (unchanged apart from the last pair): 9, 14, 22, 36, 41, 58, found in 2 passes.
(c) B1 the best case occurs when the list is already sorted, or nearly sorted (as in part (b)), needing very few passes (as few as 2, i.e. close to O(n) comparisons overall) (oe)
(c) B1 the worst case occurs when the list is far from sorted (as in part (a)), needing up to n - 1 passes and O(n²) comparisons in total (oe)
(c) Answer: Best case: a nearly-sorted list needs only a small, fixed number of passes. Worst case: a list far from sorted can need up to n - 1 passes, giving O(n²) total comparisons.

Question 3

(a) M1 first pivot = 34 identified, with correct sublists {12, 8, 27, 19} (< 34) and {55, 41, 63} (≥ 34)
(a) A1 correct second pivot and split on {12, 8, 27, 19}: pivot 12, giving {8} and {27, 19}
(a) A1 correct second pivot and split on {55, 41, 63}: pivot 55, giving {41} and {63}
(a) A1 correct third-level split on {27, 19}: pivot 27, giving {19} and { } (empty)
(a) A1 correct final sorted list 8, 12, 19, 27, 34, 41, 55, 63 cao
(a) Answer: Final sorted list: 8, 12, 19, 27, 34, 41, 55, 63.
(b) M1 correct method: sums the number of non-pivot items compared at each level, 7 + 3 + 2 + 1
(b) A1 13 comparisons cao
(b) Answer: 13 comparisons.
(c) B1 advantage: it is quick and simple to apply, since no extra comparisons are needed to choose the pivot (oe)
(c) B1 disadvantage: if a sublist happens to be already sorted (or reverse sorted), this choice gives very unbalanced splits, leading to the algorithm's worst-case order of O(n²) (oe)
(c) Answer: Advantage: quick to select, no extra comparisons needed. Disadvantage: gives poor (unbalanced) splits, and hence poor efficiency, on lists that are already sorted or nearly sorted.

Question 4

(a) B1 correctly identifies the first, middle and last items of the full list as 72, 41 and 78, and selects the median value, 72, as the first pivot
(a) A1 correct first split: {55, 41, 67, 60} (< 72) and {89, 78} (≥ 72)
(a) A1 correct second pivot on {55, 41, 67, 60}: first/middle/last are 55, 41, 60, median is 55, giving splits {41} and {67, 60}
(a) A1 correctly orders the remaining 2-item sublists: {67, 60} becomes 60, 67 and {89, 78} becomes 78, 89
(a) A1 correct final sorted list 41, 55, 60, 67, 72, 78, 89 cao
(a) Answer: Final sorted list: 41, 55, 60, 67, 72, 78, 89.
(b) B1 median-of-three is far less likely to choose an extreme (smallest or largest) value as the pivot, giving more balanced splits on average (oe)
(b) B1 the improvement is most noticeable on a list that is already sorted, or nearly sorted, in ascending or descending order, where the first-item method would otherwise produce the worst-case O(n²) behaviour (oe)
(b) Answer: Median-of-three avoids consistently unbalanced splits, keeping the algorithm closer to its efficient O(n log n) average-case behaviour, most noticeably on lists that are already sorted or nearly sorted.

Question 5

(a) M1 correct method: each parcel placed in the first bin (in order) with enough remaining space, opening a new bin only when none of the existing bins can fit it
(a) A1 correct bin contents: Bin 1 {6, 4}, Bin 2 {5, 3, 2}, Bin 3 {7}, Bin 4 {8}, Bin 5 {5}
(a) B1 5 bins used, cao
(a) B1 correctly states the spare capacity in each bin: 0 kg, 0 kg, 3 kg, 2 kg, 5 kg (total 10 kg wasted)
(a) Answer: Bin 1: 6, 4 (full). Bin 2: 5, 3, 2 (full). Bin 3: 7 (3 kg spare). Bin 4: 8 (2 kg spare). Bin 5: 5 (5 kg spare). 5 bins used.
(b) M1 total weight = 6+5+4+7+3+8+2+5 = 40 kg, lower bound = ceiling(40/10)
(b) A1 lower bound = 4 bins, and correctly notes that first-fit's 5 bins is one more than this lower bound
(b) Answer: Lower bound = 4 bins. First-fit used 5 bins, one more than this lower bound.

Question 6

(a) M1 correct decreasing order: 8, 7, 6, 5, 5, 4, 3, 2
(a) A1 correct bins: Bin 1 {8, 2}, Bin 2 {7, 3}, Bin 3 {6, 4}, Bin 4 {5, 5}, all exactly full
(a) B1 4 bins used, cao
(a) Answer: Decreasing order: 8, 7, 6, 5, 5, 4, 3, 2. Bins: {8,2}, {7,3}, {6,4}, {5,5}. 4 bins used.
(b) B1 yes, 4 bins matches the lower bound of 4 found in question 5(b), so this packing is optimal
(b) B1 placing the largest items first means each bin's remaining space is used to accommodate progressively smaller items that fit neatly into the gaps left, avoiding the situation (seen in question 5) where small items fill early bins and leave awkward gaps too small for the larger items that come later (oe)
(b) Answer: Yes, first-fit decreasing achieves the lower bound of 4 bins. Placing the largest parcels first avoids leaving awkward small gaps that later, larger parcels cannot use.

Question 7

(a) M1 total volume = 8+2+7+3+6+4+5+5 = 40 litres
(a) A1 lower bound = ceiling(40/10) = 4 cao
(a) Answer: Lower bound = 4 crates.
(b) M1 correctly pairs the largest remaining tin, 8, with the 2-litre tin to exactly fill a crate: {8, 2}
(b) A1 correctly pairs the next largest remaining tin, 7, with the 3-litre tin: {7, 3}
(b) A1 correctly pairs the next largest remaining tin, 6, with the 4-litre tin: {6, 4}
(b) A1 correctly places the two remaining 5-litre tins together to exactly fill the last crate: {5, 5}
(b) Answer: Crates: {8,2}, {7,3}, {6,4}, {5,5}, each exactly full (10 litres).
(c) B1 all 4 crates are exactly full with no wasted space, so the lower bound of 4 found in part (a) has been achieved: this packing is optimal (oe)
(c) Answer: The full-bin method achieves exactly 4 crates, matching the lower bound, so this is an optimal packing with no wasted capacity.

Question 8

(a) M1 total weight = 6+5+6+5+6+6+5+5 = 44 kg
(a) A1 lower bound = ceiling(44/9) = 5 cao
(a) Answer: Lower bound = 5 crates.
(b) M1 correct decreasing order: 6, 6, 6, 6, 5, 5, 5, 5
(b) A1 correctly shows that no two items can share a crate (6+6=12 > 9, 6+5=11 > 9, 5+5=10 > 9), so each item is placed in its own crate
(b) B1 8 crates used, cao
(b) Answer: Every item needs its own crate: 8 crates used.
(c) B1 any two of these items sum to more than the crate capacity of 9 kg (6+6=12, 6+5=11, 5+5=10, all exceed 9), so no crate can ever hold more than one item (oe)
(c) B1 this means the true minimum number of crates is 8 (one per item), so the lower-bound formula (total weight / capacity, rounded up) only gives a necessary condition, not a value that is always achievable (oe)
(c) Answer: Since every pair of items sums to more than 9 kg, no crate can ever hold two items, so 8 crates are always needed regardless of method; the lower bound of 5 is not achievable for this data.

Question 9

(a) M1 correctly calculates the ratio of successive run times: 32/8 = 4, 128/32 = 4, 512/128 = 4
(a) A1 identifies that the ratio is consistently 4 each time n doubles
(a) A1 correctly concludes the order is O(n²), since 4 = 2² oe
(a) Answer: Algorithm 1 has order O(n²).
(b) M1 correctly calculates the ratio of successive run times: 32/4 = 8, 256/32 = 8
(b) A1 correctly concludes the order is O(n³), since 8 = 2³ oe
(b) Answer: Algorithm 2 has order O(n³).
(c) M1 recognises that 800 is 4 times 200, and that for an O(n) algorithm run time scales by the same factor as n
(c) A1 60 ms cao
(c) Answer: 60 ms.

Question 10

(a) B1 it finds the maximum value, the minimum value, and the range (Max - Min) of the list (oe)
(a) Answer: It finds the maximum value, the minimum value, and the range of the list of numbers.
(b) M1 correct initial values before the loop: Max = 23, Min = 23
(b) A1 correct values through i = 2 to i = 4: i=2 Max=45 Min=23; i=3 Max=45 Min=12; i=4 Max=67 Min=12
(b) A1 correct values through i = 5 to i = 7: i=5 Max=67 Min=12 (no change); i=6 Max=67 Min=9; i=7 Max=67 Min=9 (no change)
(b) Answer: i: 2,3,4,5,6,7 giving Max: 45,45,67,67,67,67 and Min: 23,12,12,12,9,9.
(c) B1 Max = 67, Min = 9, Range = 58, all correct
(c) Answer: Max = 67, Min = 9, Range = 58.
(d) B1 order O(n), i.e. linear
(d) B1 the loop runs a fixed number of comparisons (2 comparisons, at Steps 4 and 5) for each of the n - 1 remaining items, so the total number of comparisons is directly proportional to n (oe)
(d) Answer: O(n): the loop performs a fixed number of comparisons for each of the n - 1 remaining items, so the total work is directly proportional to n.

Question 11

(a) B1 (i) 1225 cao (50 x 49 / 2)
(a) B1 (ii) 19900 cao (200 x 199 / 2)
(a) B1 (iii) 523776 cao (1024 x 1023 / 2)
(a) Answer: (i) 1225; (ii) 19900; (iii) 523776.
(b) M1 correctly calculates the ratio 19900 / 1225 = 16.24... (awrt 16.2)
(b) A1 compares this to 4² = 16 and concludes the closeness confirms the order O(n²) (the small difference from exactly 16 is because n(n-1)/2 also has a lower-order term, becoming negligible for large n) (oe)
(b) Answer: Ratio approx 16.2, close to 4² = 16, consistent with worst-case order O(n²).
(c) M1 uses log2(1024) = 10 (since 2¹⁰ = 1024)
(c) A1 1024 x 10 = 10240 comparisons cao
(c) Answer: Approximately 10240 comparisons.
(d) B1 for n = 1024, quicksort's average 10240 comparisons is far smaller than bubble sort's worst-case 523776 comparisons, roughly 51 times fewer (oe, allow awrt 50)
(d) B1 as n grows large, an O(n log n) algorithm remains practical while an O(n²) algorithm's run time grows far more quickly, so the difference in order becomes increasingly significant for large data sets (oe)
(d) Answer: Quicksort's estimate (10240) is roughly 51 times smaller than bubble sort's worst case (523776); as n grows, this gap widens further, so the choice of algorithm order matters far more for large data sets.

Question 12

(a) M1 total weight = 12+9+14+7+11+8+15+6+13+10 = 105 kg
(a) A1 lower bound = ceiling(105/20) = 6 cao
(a) Answer: Lower bound = 6 crates.
(b) M1 correct method applied in the given order, checking each weight against existing crates before opening a new one
(b) A1 correct crates: {12,7}, {9,11}, {14,6}, {8,10}, {15}, {13}
(b) B1 6 crates used cao
(b) Answer: Crates: {12,7}, {9,11}, {14,6}, {8,10}, {15}, {13}. 6 crates used.
(c) M1 correct decreasing order: 15, 14, 13, 12, 11, 10, 9, 8, 7, 6
(c) A1 correct crates: {15}, {14,6}, {13,7}, {12,8}, {11,9}, {10}
(c) B1 6 crates used cao
(c) Answer: Crates: {15}, {14,6}, {13,7}, {12,8}, {11,9}, {10}. 6 crates used.
(d) M1 identifies the four pairs that sum to exactly 20: (12,8), (9,11), (14,6), (7,13)
(d) A1 correctly identifies that the two remaining items, 15 and 10, cannot be combined (15+10 = 25 > 20), so each needs its own crate
(d) B1 total crates still 6 cao (4 full crates plus 2 further crates for 15 and 10), matching the lower bound in part (a)
(d) Answer: Full crates: {12,8}, {9,11}, {14,6}, {7,13}. Remaining items 15 and 10 cannot be paired (sum 25 > 20), so each needs its own crate. Total 6 crates.
(e) B1 all three methods achieve the same number of crates, 6, matching the lower bound from part (a), so an optimal packing has been found for this data set (oe)
(e) B1 this agreement is not guaranteed in general: as seen in earlier questions, first-fit alone does not always reach the lower bound, so its success here depends on the particular set of weights rather than being a general property of the algorithm (oe)
(e) Answer: All three methods reach the optimal 6 crates for this data set, but this is a feature of this particular set of weights rather than a guarantee: first-fit does not always match the lower bound (as seen with Chidi's parcels in question 5).

Decision Maths: Algorithms, Sorting and Bin Packing - Worksheets, Questions and Revision