Decision Maths: Algorithms, Sorting and Bin Packing - Worksheets, Questions and Revision
23 original exam-style questions - 10 pages of questions with a full mark scheme - free printable PDF.
Decision Maths: Algorithms, Sorting and Bin Packing revision guideWrite-in editionMore A Level Further Maths practiceMock exams
This topic is chapter 1 of A Level Further Maths Decision Topic Workbook and chapter 16 of A Level Further Maths 10-Minute Tests 1.
4.1 Decision Maths: Algorithms, Sorting and Bin Packing
6, 5, 4, 7, 3, 8, 2, 5
12, 9, 14, 7, 11, 8, 15, 6, 13, 10
34, 12, 55, 8, 41, 27, 63, 19
8, 2, 7, 3, 6, 4, 5, 5
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(nk).(3)
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)
Question 1
- (a) 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 itM1
- (a) correct bin contents: Bin 1 {6, 4}, Bin 2 {5, 3, 2}, Bin 3 {7}, Bin 4 {8}, Bin 5 {5}A1
- (a) 5 bins used, caoB1
- (a) correctly states the spare capacity in each bin: 0 kg, 0 kg, 3 kg, 2 kg, 5 kg (total 10 kg wasted)B1
- (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) total weight = 6+5+4+7+3+8+2+5 = 40 kg, lower bound = ceiling(40/10)M1
- (b) lower bound = 4 bins, and correctly notes that first-fit's 5 bins is one more than this lower boundA1
- (b) Answer: Lower bound = 4 bins. First-fit used 5 bins, one more than this lower bound.
Question 2
- (a) (i) 1225 cao (50 x 49 / 2)B1
- (a) (ii) 19900 cao (200 x 199 / 2)B1
- (a) (iii) 523776 cao (1024 x 1023 / 2)B1
- (a) Answer: (i) 1225; (ii) 19900; (iii) 523776.
- (b) correctly calculates the ratio 19900 / 1225 = 16.24... (awrt 16.2)M1
- (b) compares this to 42 = 16 and concludes the closeness confirms the order O(n2) (the small difference from exactly 16 is because n(n-1)/2 also has a lower-order term, becoming negligible for large n) (oe)A1
- (b) Answer: Ratio approx 16.2, close to 42 = 16, consistent with worst-case order O(n2).
- (c) uses log2(1024) = 10 (since 210 = 1024)M1
- (c) 1024 x 10 = 10240 comparisons caoA1
- (c) Answer: Approximately 10240 comparisons.
- (d) 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)B1
- (d) as n grows large, an O(n log n) algorithm remains practical while an O(n2) algorithm's run time grows far more quickly, so the difference in order becomes increasingly significant for large data sets (oe)B1
- (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 3
- (a) total weight = 12+9+14+7+11+8+15+6+13+10 = 105 kgM1
- (a) lower bound = ceiling(105/20) = 6 caoA1
- (a) Answer: Lower bound = 6 crates.
- (b) correct method applied in the given order, checking each weight against existing crates before opening a new oneM1
- (b) correct crates: {12,7}, {9,11}, {14,6}, {8,10}, {15}, {13}A1
- (b) 6 crates used caoB1
- (b) Answer: Crates: {12,7}, {9,11}, {14,6}, {8,10}, {15}, {13}. 6 crates used.
- (c) correct decreasing order: 15, 14, 13, 12, 11, 10, 9, 8, 7, 6M1
- (c) correct crates: {15}, {14,6}, {13,7}, {12,8}, {11,9}, {10}A1
- (c) 6 crates used caoB1
- (c) Answer: Crates: {15}, {14,6}, {13,7}, {12,8}, {11,9}, {10}. 6 crates used.
- (d) identifies the four pairs that sum to exactly 20: (12,8), (9,11), (14,6), (7,13)M1
- (d) correctly identifies that the two remaining items, 15 and 10, cannot be combined (15+10 = 25 > 20), so each needs its own crateA1
- (d) total crates still 6 cao (4 full crates plus 2 further crates for 15 and 10), matching the lower bound in part (a)B1
- (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) 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)B1
- (e) 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)B1
- (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 1).
Question 4
- (a) total size = 84M1
- (a) 84/20 = 4.20, so at least 5 binsA1
- (a) Answer: 5
- (b) places each item in the first bin with enough room, in the order givenM1
- (b) first bins correctA1
- (b) bins: (11, 7); (15, 5); (12, 5); (14, 4); (11)A1
- (b) Answer: (11, 7); (15, 5); (12, 5); (14, 4); (11)
- (c) sorts the items into descending orderM1
- (c) applies first-fit to the sorted listM1
- (c) 5 bins: (15, 5); (14, 5); (12, 7); (11, 4); (11)A1
- (c) Answer: 5 bins: (15, 5); (14, 5); (12, 7); (11, 4); (11)
Question 5
- (a) compares adjacent pairs from the left, swapping when the left item is largerM1
- (a) list after pass 1: 1, 24, 34, 40, 50, 44, 28, 55A1
- (a) 5 swapsB1
- (a) Answer: 1, 24, 34, 40, 50, 44, 28, 55; 5 swaps
- (b) repeats the process, ignoring the final item (already in place)M1
- (b) 1, 24, 34, 40, 44, 28, 50, 55A1
- (b) Answer: 1, 24, 34, 40, 44, 28, 50, 55
- (c) 5 passesB1
- (c) 10 swaps in totalB1
- (c) Answer: 5 passes, 10 swaps
Question 6
- (a) compares adjacent pairs from the left, swapping when the left item is largerM1
- (a) list after pass 1: 38, 40, 43, 22, 12, 48, 49, 52A1
- (a) 5 swapsB1
- (a) Answer: 38, 40, 43, 22, 12, 48, 49, 52; 5 swaps
- (b) repeats the process, ignoring the final item (already in place)M1
- (b) 38, 40, 22, 12, 43, 48, 49, 52A1
- (b) Answer: 38, 40, 22, 12, 43, 48, 49, 52
- (c) 5 passesB1
- (c) 12 swaps in totalB1
- (c) Answer: 5 passes, 12 swaps
Question 7
- (a) compares adjacent pairs from the left, swapping when the left item is largerM1
- (a) list after pass 1: 10, 39, 2, 27, 11, 14, 56A1
- (a) 6 swapsB1
- (a) Answer: 10, 39, 2, 27, 11, 14, 56; 6 swaps
- (b) repeats the process, ignoring the final item (already in place)M1
- (b) 10, 2, 27, 11, 14, 39, 56A1
- (b) Answer: 10, 2, 27, 11, 14, 39, 56
- (c) 3 passesB1
- (c) 13 swaps in totalB1
- (c) Answer: 3 passes, 13 swaps
Question 8
- (a) compares adjacent pairs from the left, swapping when the left item is largerM1
- (a) list after pass 1: 2, 7, 14, 15, 28, 51, 16, 54A1
- (a) 3 swapsB1
- (a) Answer: 2, 7, 14, 15, 28, 51, 16, 54; 3 swaps
- (b) repeats the process, ignoring the final item (already in place)M1
- (b) 2, 7, 14, 15, 28, 16, 51, 54A1
- (b) Answer: 2, 7, 14, 15, 28, 16, 51, 54
- (c) 3 passesB1
- (c) 5 swaps in totalB1
- (c) Answer: 3 passes, 5 swaps
Question 9
- (a) compares adjacent pairs from the left, swapping when the left item is largerM1
- (a) list after pass 1: 3, 23, 36, 46, 27, 43, 54, 55, 58A1
- (a) 4 swapsB1
- (a) Answer: 3, 23, 36, 46, 27, 43, 54, 55, 58; 4 swaps
- (b) repeats the process, ignoring the final item (already in place)M1
- (b) 3, 23, 36, 27, 43, 46, 54, 55, 58A1
- (b) Answer: 3, 23, 36, 27, 43, 46, 54, 55, 58
- (c) 3 passesB1
- (c) 7 swaps in totalB1
- (c) Answer: 3 passes, 7 swaps
Question 10
- (a) compares adjacent pairs from the left, swapping when the left item is largerM1
- (a) list after pass 1: 7, 49, 51, 31, 56, 28, 55, 9, 59A1
- (a) 6 swapsB1
- (a) Answer: 7, 49, 51, 31, 56, 28, 55, 9, 59; 6 swaps
- (b) repeats the process, ignoring the final item (already in place)M1
- (b) 7, 49, 31, 51, 28, 55, 9, 56, 59A1
- (b) Answer: 7, 49, 31, 51, 28, 55, 9, 56, 59
- (c) 7 passesB1
- (c) 19 swaps in totalB1
- (c) Answer: 7 passes, 19 swaps
Question 11
- (a) total size = 166M1
- (a) 166/40 = 4.15, so at least 5 binsA1
- (a) Answer: 5
- (b) places each item in the first bin with enough room, in the order givenM1
- (b) first bins correctA1
- (b) bins: (35); (9, 11, 12, 7); (24); (33); (35)A1
- (b) Answer: (35); (9, 11, 12, 7); (24); (33); (35)
- (c) sorts the items into descending orderM1
- (c) applies first-fit to the sorted listM1
- (c) 5 bins: (35); (35); (33, 7); (24, 12); (11, 9)A1
- (c) Answer: 5 bins: (35); (35); (33, 7); (24, 12); (11, 9)
Question 12
- (a) total size = 212M1
- (a) 212/40 = 5.30, so at least 6 binsA1
- (a) Answer: 6
- (b) places each item in the first bin with enough room, in the order givenM1
- (b) first bins correctA1
- (b) bins: (25, 4); (21, 16); (24, 12); (23); (22); (29); (36)A1
- (b) Answer: (25, 4); (21, 16); (24, 12); (23); (22); (29); (36)
- (c) sorts the items into descending orderM1
- (c) applies first-fit to the sorted listM1
- (c) 7 bins: (36, 4); (29); (25, 12); (24, 16); (23); (22); (21)A1
- (c) Answer: 7 bins: (36, 4); (29); (25, 12); (24, 16); (23); (22); (21)
Question 13
- (a) total size = 96M1
- (a) 96/20 = 4.80, so at least 5 binsA1
- (a) Answer: 5
- (b) places each item in the first bin with enough room, in the order givenM1
- (b) first bins correctA1
- (b) bins: (12, 6); (14, 5); (14); (14); (7, 10); (14)A1
- (b) Answer: (12, 6); (14, 5); (14); (14); (7, 10); (14)
- (c) sorts the items into descending orderM1
- (c) applies first-fit to the sorted listM1
- (c) 6 bins: (14, 6); (14, 5); (14); (14); (12, 7); (10)A1
- (c) Answer: 6 bins: (14, 6); (14, 5); (14); (14); (12, 7); (10)
Question 14
- (a) total size = 136M1
- (a) 136/25 = 5.44, so at least 6 binsA1
- (a) Answer: 6
- (b) places each item in the first bin with enough room, in the order givenM1
- (b) first bins correctA1
- (b) bins: (21); (18, 7); (14, 10); (19); (20); (19); (8)A1
- (b) Answer: (21); (18, 7); (14, 10); (19); (20); (19); (8)
- (c) sorts the items into descending orderM1
- (c) applies first-fit to the sorted listM1
- (c) 7 bins: (21); (20); (19); (19); (18, 7); (14, 10); (8)A1
- (c) Answer: 7 bins: (21); (20); (19); (19); (18, 7); (14, 10); (8)
Question 15
- (a) compares adjacent pairs from the left, swapping when the left item is largerM1
- (a) list after pass 1: 3, 14, 31, 8, 33, 44, 56A1
- (a) 4 swapsB1
- (a) Answer: 3, 14, 31, 8, 33, 44, 56; 4 swaps
- (b) repeats the process, ignoring the final item (already in place)M1
- (b) 3, 14, 8, 31, 33, 44, 56A1
- (b) Answer: 3, 14, 8, 31, 33, 44, 56
- (c) 3 passesB1
- (c) 6 swaps in totalB1
- (c) Answer: 3 passes, 6 swaps
Question 16
- (a) total size = 189M1
- (a) 189/50 = 3.78, so at least 4 binsA1
- (a) Answer: 4
- (b) places each item in the first bin with enough room, in the order givenM1
- (b) first bins correctA1
- (b) bins: (8, 11, 31); (34, 13); (39); (35); (18)A1
- (b) Answer: (8, 11, 31); (34, 13); (39); (35); (18)
- (c) sorts the items into descending orderM1
- (c) applies first-fit to the sorted listM1
- (c) 4 bins: (39, 11); (35, 13); (34, 8); (31, 18)A1
- (c) Answer: 4 bins: (39, 11); (35, 13); (34, 8); (31, 18)
Question 17
- (a) total size = 102M1
- (a) 102/20 = 5.10, so at least 6 binsA1
- (a) Answer: 6
- (b) places each item in the first bin with enough room, in the order givenM1
- (b) first bins correctA1
- (b) bins: (8, 8); (8, 10); (14, 5); (15); (16); (9, 9)A1
- (b) Answer: (8, 8); (8, 10); (14, 5); (15); (16); (9, 9)
- (c) sorts the items into descending orderM1
- (c) applies first-fit to the sorted listM1
- (c) 6 bins: (16); (15, 5); (14); (10, 9); (9, 8); (8, 8)A1
- (c) Answer: 6 bins: (16); (15, 5); (14); (10, 9); (9, 8); (8, 8)
Question 18
- (a) total size = 50M1
- (a) 50/20 = 2.50, so at least 3 binsA1
- (a) Answer: 3
- (b) places each item in the first bin with enough room, in the order givenM1
- (b) first bins correctA1
- (b) bins: (14, 4); (7, 5, 8); (3, 6, 3)A1
- (b) Answer: (14, 4); (7, 5, 8); (3, 6, 3)
- (c) sorts the items into descending orderM1
- (c) applies first-fit to the sorted listM1
- (c) 3 bins: (14, 6); (8, 7, 5); (4, 3, 3)A1
- (c) Answer: 3 bins: (14, 6); (8, 7, 5); (4, 3, 3)
Question 19
- (a) compares adjacent pairs from the left, swapping when the left item is largerM1
- (a) list after pass 1: 26, 14, 34, 16, 48, 3, 57A1
- (a) 5 swapsB1
- (a) Answer: 26, 14, 34, 16, 48, 3, 57; 5 swaps
- (b) repeats the process, ignoring the final item (already in place)M1
- (b) 14, 26, 16, 34, 3, 48, 57A1
- (b) Answer: 14, 26, 16, 34, 3, 48, 57
- (c) 6 passesB1
- (c) 13 swaps in totalB1
- (c) Answer: 6 passes, 13 swaps
Question 20
- (a) first pivot = 34 identified, with correct sublists {12, 8, 27, 19} (< 34) and {55, 41, 63} (≥ 34)M1
- (a) correct second pivot and split on {12, 8, 27, 19}: pivot 12, giving {8} and {27, 19}A1
- (a) correct second pivot and split on {55, 41, 63}: pivot 55, giving {41} and {63}A1
- (a) correct third-level split on {27, 19}: pivot 27, giving {19} and { } (empty)A1
- (a) correct final sorted list 8, 12, 19, 27, 34, 41, 55, 63 caoA1
- (a) Answer: Final sorted list: 8, 12, 19, 27, 34, 41, 55, 63.
- (b) correct method: sums the number of non-pivot items compared at each level, 7 + 3 + 2 + 1M1
- (b) 13 comparisons caoA1
- (b) Answer: 13 comparisons.
- (c) advantage: it is quick and simple to apply, since no extra comparisons are needed to choose the pivot (oe)B1
- (c) 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(n2) (oe)B1
- (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 21
- (a) correct decreasing order: 8, 7, 6, 5, 5, 4, 3, 2M1
- (a) correct bins: Bin 1 {8, 2}, Bin 2 {7, 3}, Bin 3 {6, 4}, Bin 4 {5, 5}, all exactly fullA1
- (a) 4 bins used, caoB1
- (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) yes, 4 bins matches the lower bound of 4 found in question 1(b), so this packing is optimalB1
- (b) 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 1) where small items fill early bins and leave awkward gaps too small for the larger items that come later (oe)B1
- (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 22
- (a) total volume = 8+2+7+3+6+4+5+5 = 40 litresM1
- (a) lower bound = ceiling(40/10) = 4 caoA1
- (a) Answer: Lower bound = 4 crates.
- (b) correctly pairs the largest remaining tin, 8, with the 2-litre tin to exactly fill a crate: {8, 2}M1
- (b) correctly pairs the next largest remaining tin, 7, with the 3-litre tin: {7, 3}A1
- (b) correctly pairs the next largest remaining tin, 6, with the 4-litre tin: {6, 4}A1
- (b) correctly places the two remaining 5-litre tins together to exactly fill the last crate: {5, 5}A1
- (b) Answer: Crates: {8,2}, {7,3}, {6,4}, {5,5}, each exactly full (10 litres).
- (c) 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)B1
- (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 23
- (a) correctly calculates the ratio of successive run times: 32/8 = 4, 128/32 = 4, 512/128 = 4M1
- (a) identifies that the ratio is consistently 4 each time n doublesA1
- (a) correctly concludes the order is O(n2), since 4 = 22 oeA1
- (a) Answer: Algorithm 1 has order O(n2).
- (b) correctly calculates the ratio of successive run times: 32/4 = 8, 256/32 = 8M1
- (b) correctly concludes the order is O(n3), since 8 = 23 oeA1
- (b) Answer: Algorithm 2 has order O(n3).
- (c) recognises that 800 is 4 times 200, and that for an O(n) algorithm run time scales by the same factor as nM1
- (c) 60 ms caoA1
- (c) Answer: 60 ms.
Mark your answers
Check answers without an account. Some answers can be checked automatically; use the mark scheme to mark the rest.