Edexcel International A Level Maths · D1 · Decision Mathematics 1
Algorithms: sorting, searching and packing
28 free, high-quality past-paper-style questions on Algorithms: sorting, searching and packing for Edexcel IAL Maths, each with a full mark scheme. For when you have finished the past papers, or want to practise one topic at a time.IAL Maths notes and flashcards →Not sure of your level? Diagnostic test →Multiple choice or structured questions, with the mark scheme as a separate PDF.28 new this month · 232 marks · Updated 26 October 2026 · Created by Evan Kotronis with AI assistance · How questions are checked
1IALM-D1-1-B-01D1 · ASEasy6 marks
An algorithm is given below. Step 1: Input two positive integers A and B. Step 2: Let Q = 0. Step 3: If A < B, go to Step 6. Step 4: Let A = A − B and let Q = Q + 1. Step 5: Go to Step 3. Step 6: Output Q and A. Stop.
(a)
Carry out the algorithm with A = 47 and B = 6. Show the values of A and Q in a table and state the output.
(3)
(b)
State what the two outputs represent in terms of the inputs.
(2)
(c)
Write down how many times Step 4 is carried out when A = 1000 and B = 7.
(1)
Show mark scheme
Answer
Mark
Notes
Part (a)
repeated subtraction of 6 recorded, with Q increasing by 1 each time
Q is the quotient (whole number of times B goes into A)
B1
A is the remainder when the input A is divided by B
B1
Part (c)
1000 = 142 × 7 + 6, so 142 times
B1
Common error: Stopping one subtraction too early or too late. The test in Step 3 is made before each subtraction: with A = 5 and B = 6 the algorithm goes straight to the output.
The times, in seconds, of seven swimmers in a 100 m race are 63, 58, 71, 60, 66, 55, 69 The times are to be sorted into ascending order using a bubble sort.
(a)
Carry out the first pass. State the list at the end of the pass, and the number of comparisons and swaps made.
(3)
(b)
Complete the sort, giving the list at the end of each further pass. State clearly how you know the sort is complete.
(3)
Show mark scheme
Answer
Mark
Notes
Part (a)
compares neighbouring pairs from the left, swapping any pair in the wrong order
pass 6: no swaps (or 6 passes, the most needed for 7 items), so the list is sorted: 55, 58, 60, 63, 66, 69, 71
A1
Exam tip: Write the full list after every pass, even when only one pair has moved. A pass with no swaps is how the algorithm knows it has finished, so show it.
A theatre keeps a list of the seat numbers already booked for one performance, in ascending order: 104, 117, 123, 138, 146, 152, 165, 171, 189, 194, 207, 218, 226
(a)
Use a binary search to find the seat number 189 in the list. Show each iteration, stating which item you compare with and which part of the list you keep.
(3)
(b)
Find the maximum number of iterations that a binary search of this list could need, giving a reason.
Boxes of floor tiles are to be stored on shelves. Each shelf can safely hold at most 25 kg. The masses of the boxes, in kg, in the order in which they are delivered, are 9, 14, 6, 11, 8, 13, 5, 7
(a)
Calculate a lower bound for the number of shelves needed. Show your working.
(2)
(b)
Use the first-fit algorithm, taking the boxes in the order given, to allocate the boxes to shelves.
(3)
(c)
Explain whether your allocation in part (b) is optimal.
(1)
Show mark scheme
Answer
Mark
Notes
Part (a)
total 73 and 73 ÷ 25 = 2.92
M1
rounded up: 3 shelves
A1
Part (b)
each box placed in the first shelf with enough room, checking from shelf 1 each time
M1
first two shelves correct: Shelf 1: 9, 14 and Shelf 2: 6, 11, 8
A1
Shelf 3: 13, 5, 7, so 3 shelves
A1
Part (c)
it uses 3 shelves, equal to the lower bound, so it is optimal ft on their (a) and (b)
B1
Exam tip: First fit is not always worse than first-fit decreasing. Here first-fit decreasing (14, 11 · 13, 9 · 8, 7, 6 · 5) would use 4 shelves; only a comparison with the lower bound tells you a packing is optimal.
7 times (six answers ‘yes’ and one ‘no’) ft on their table
B1
Part (c)
1 + 3 + 5 + 7 + 9 + 11 + 13 = 49, so the output is 7 and N = 0 when it stops
B1
Part (d)
the largest integer whose square is at most N, i.e. the integer part of √N (since 1 + 3 + … + (2K − 1) = K2)
B1
Exam tip: Keep one row of the table for each time you return to the decision box. The last row (N = 4, D = 13) is where the answer ‘no’ is given, and it is easy to forget to record it.
The graph in Figure 1 shows the temperature at noon, in °C, at a weather station on each day of one week. The seven temperatures, in the order Monday to Sunday, are to be sorted into ascending order using a bubble sort, starting at the left-hand end of the list in each pass.
(a)
Use the graph to write down the list of temperatures, in the order Monday to Sunday.
(1)
(b)
Carry out the first pass of the bubble sort. Give the list at the end of the pass and the number of swaps made.
(2)
(c)
Complete the bubble sort, giving the list at the end of each further pass, and explain how you know that the sort is complete.
pass 5 makes no swaps, so the list is in order: −4, −2, 0, 1, 3, 5, 6
A1
Common error: Comparing negative numbers by their size without the sign. −4 is smaller than −2, so in ascending order −4 must come first; check each comparison on the number line if unsure.
The timeline in Figure 1 shows the years in which the twelve bridges across a river were opened. The years form an ordered list, the earliest being in position 1.
(a)
Use a binary search to locate the year 1957 in the list. Show each iteration, stating the item you compare with and which part of the list you keep.
(3)
(b)
Find the greatest number of iterations a binary search of this list could need. Give a reason for your answer.
⌈(8 + 8)/2⌉ = 8, item 1957: found in position 8, after 4 iterations
A1
Part (b)
each iteration removes the middle item and at least half of the rest: 12 → at most 6 → 3 → 1 (or 23 = 8 ≤ 12 < 16 = 24)
M1
4 iterations
A1
Exam tip: Number the positions on the figure before you start. The binary search works with positions, not with the years themselves, so ⌈(8 + 12)/2⌉ = 10 tells you to look at the 10th year.
A plumber needs the eight lengths of pipe A to H shown, with their lengths, in Figure 1. They are to be cut from standard 6 m lengths of pipe. Assume no pipe is lost in cutting, and that a piece may not be made by joining two shorter pieces.
(a)
Find a lower bound for the number of 6 m lengths needed.
(2)
(b)
Use the first-fit algorithm, taking the pieces in the order A to H, to decide how the pieces are cut. State how many 6 m lengths are used.
(3)
(c)
Find a way of cutting all eight pieces from three 6 m lengths, and explain why this is optimal.
(2)
Show mark scheme
Answer
Mark
Notes
Part (a)
total 17.8 m and 17.8 ÷ 6 = 2.97
M1
rounded up: 3 lengths
A1
Part (b)
each piece placed in the first length with enough pipe left, checking from length 1 each time
M1
Length 1: 2.4, 3.1 · Length 2: 1.7, 2.8, 0.9
A1
Length 3: 3.5, 1.2 · Length 4: 2.2, so 4 lengths
A1
Part (c)
e.g. F + A = 5.9, B + D = 5.9, H + C + G + E = 6.0 (any valid allocation into 3 lengths)
B1
3 is the lower bound, so no cutting plan can use fewer: optimal
B1
Exam tip: Work in decimetres (24, 31, 17, …) to avoid decimal slips when adding, then convert back to metres for your final answer.
A flow chart has the following boxes. Box 1: Start. Box 2: Input positive integers a and b. Box 3: Let r be the remainder when a is divided by b. Box 4 (decision): Is r = 0? If yes, go to Box 7. If no, go to Box 5. Box 5: Let a = b. Box 6: Let b = r, then go back to Box 3. Box 7: Output b. Box 8: Stop.
(a)
Use the flow chart with the input a = 391, b = 323. Show your working in a table with columns a, b and r, and state the output.
(4)
(b)
State what the algorithm finds.
(1)
(c)
State how many times Box 3 is used in part (a).
(1)
(d)
The inputs are now entered the other way round, a = 323 and b = 391. Describe what happens, and state how many times Box 3 is used.
(2)
Show mark scheme
Answer
Mark
Notes
Part (a)
a
b
r
391
323
68
323
68
51
68
51
17
51
17
0
first row 391, 323, 68
M1
second row 323, 68, 51
A1
third and fourth rows 68, 51, 17 and 51, 17, 0
A1
output 17
A1
Part (b)
the highest common factor of a and b (391 = 17 × 23, 323 = 17 × 19)
B1
Part (c)
4 times ft on their table
B1
Part (d)
first remainder is 323 (391 does not go into 323), so after Boxes 5 and 6, a = 391 and b = 323: the inputs are swapped and the algorithm continues as in (a) with the same output 17
B1
Box 3 is used 5 times
B1
Exam tip: Boxes 5 and 6 must be done in that order. Doing Box 6 first would overwrite b before it is copied into a; read the flow chart box by box and do not combine steps in your head.
A club secretary has the surnames of ten new members: Okafor, Bianchi, Novak, Haddad, Tanaka, Lindqvist, Ferreira, Kowalski, Diaz, Mensah The names are to be sorted into alphabetical order using a quick sort, taking the pivot of each sublist as its middle item (the item just right of centre when a sublist has an even number of items).
(a)
Carry out the quick sort. Show the list after each pass and state the pivots used in each pass.
(5)
(b)
In a quick sort, each item in a sublist is compared once with that sublist’s pivot. Find the number of comparisons made in pass 1 and in pass 2.
pass 2 pivots Ferreira and Tanaka: Bianchi, Diaz, Ferreira, Haddad, Kowalski, Lindqvist, Okafor, Novak, Mensah, Tanaka ft
A1
pass 3 pivots Diaz, Kowalski and Novak
M1
Bianchi, Diaz, Ferreira, Haddad, Kowalski, Lindqvist, Mensah, Novak, Okafor, Tanaka, every name now a pivot or alone
A1
Part (b)
pass 1: 9 comparisons
B1
pass 2: sublists of 5 and 4 names, 4 + 3 = 7 comparisons ft
B1
Common error: Putting the names that come before the pivot into alphabetical order straight away. They must stay in the order in which they appeared in the list; only the pivot is fixed in each pass.
The distances, in metres, of eight throws in a shot-put competition are 3.4, 5.1, 2.8, 6.0, 4.7, 5.5, 3.9, 6.3 The distances are to be sorted into descending order using a bubble sort, starting at the left-hand end of the list in each pass and making one comparison fewer in each pass than in the one before.
(a)
Carry out the bubble sort, giving the list at the end of each pass.
(4)
(b)
Find the total number of comparisons and the total number of swaps made.
(2)
(c)
Explain why no list of eight items can need more comparisons than this in a bubble sort.
(2)
Show mark scheme
Answer
Mark
Notes
Part (a)
a pair is swapped when the left item is smaller than the right item
at most 7 passes are needed, and pass k makes 8 − k comparisons
M1
so the maximum is ½ × 8 × 7 = 28, which this list reaches
A1
Exam tip: In descending order the smallest item moves to the right-hand end in pass 1, so the last place is fixed after pass 1, the last two after pass 2, and so on. Use that as a check on each line.
A list of the 20 locker numbers that have been allocated in a sports centre is held in ascending order: 12, 19, 23, 31, 36, 44, 47, 52, 58, 63, 67, 71, 76, 80, 85, 88, 91, 95, 97, 99
(a)
Use a binary search to locate locker number 58. Show your working.
(3)
(b)
Use a binary search to show that locker number 40 has not been allocated.
(3)
(c)
Write down the maximum number of iterations needed to search this list.
(1)
Show mark scheme
Answer
Mark
Notes
Part (a)
⌈(1 + 20)/2⌉ = 11, item 67; 58 < 67 so keep 1–10
M1
⌈(1 + 10)/2⌉ = 6, item 44; 58 > 44 so keep 7–10
A1
⌈(7 + 10)/2⌉ = 9, item 58: found, position 9
A1
Part (b)
items 67 (position 11) then 44 (position 6): 40 is smaller each time, keep 1–5
no items remain (first > last), so 40 is not in the list
A1
Part (c)
5 (since 24 = 16 ≤ 20 < 32 = 25)
B1
Common error: Stopping an unsuccessful search when only one or two items are left, and saying “40 is not there” without checking them. Carry on until the list is empty.
Nine data files, of sizes (in GB) 22, 28, 14, 11, 15, 9, 13, 17, 21 are to be stored on discs, each of which can hold 50 GB. A file cannot be split between discs.
(a)
Find a lower bound for the number of discs needed.
(2)
(b)
Use the first-fit decreasing algorithm to allocate the files to discs.
(3)
(c)
Use full bins to find an allocation that uses fewer discs.
(3)
(d)
Explain why your allocation in part (c) is optimal.
(1)
Show mark scheme
Answer
Mark
Notes
Part (a)
150 ÷ 50
M1
3 discs
A1
Part (b)
sorted: 28, 22, 21, 17, 15, 14, 13, 11, 9
M1
Disc 1: 28, 22 and Disc 2: 21, 17, 11
A1
Disc 3: 15, 14, 13 and Disc 4: 9, so 4 discs
A1
Part (c)
looks for combinations totalling exactly 50, e.g. 28 + 22
M1
a second full disc, e.g. 21 + 15 + 14
A1
remaining files fill the third disc, e.g. 17 + 13 + 11 + 9 = 50: 3 discs (any correct 3-disc allocation)
A1
Part (d)
3 discs equals the lower bound, so no allocation can use fewer
B1
Exam tip: When the total is an exact multiple of the capacity, an allocation that meets the lower bound must fill every bin exactly — so look for exact totals first.
A computer program sorts lists of names using a bubble sort, which has quadratic order. It takes 0.12 seconds to sort a list of 400 names. A second program, which has cubic order, takes 1.6 seconds to process a list of 50 items.
(a)
Estimate the time the first program takes to sort 2000 names.
(2)
(b)
Estimate the size of list that the second program can process in 200 seconds.
(2)
(c)
A binary search is used on an ordered list of 4000 names. Explain why it never needs more than 12 iterations.
(2)
Show mark scheme
Answer
Mark
Notes
Part (a)
0.12 × (2000 ÷ 400)2
M1
3 seconds
A1
Part (b)
(n ÷ 50)3 = 200 ÷ 1.6 = 125
M1
n ÷ 50 = 5, so about 250 items
A1
Part (c)
each iteration discards the middle item and at least half of the rest, so after k iterations at most 4000 ÷ 2k items remain
M1
211 = 2048 ≤ 4000 < 4096 = 212: after 11 iterations at most 4000 ÷ 2048 < 2, so at most 1 item remains and the 12th iteration ends the search; at most 12 iterations
A1
Exam tip: Write the scale factor as (new size ÷ old size) raised to the order: here 52 = 25 for the quadratic program, not 5.
Figure 1 shows the scores of nine players in a quiz, in the order in which they finished. The scores are to be sorted into descending order using a quick sort, choosing the middle item of each sublist as its pivot (the item just right of centre when a sublist has an even number of items).
(a)
Carry out the quick sort on the scores, in the order shown in Figure 1. Show the list after each pass and state the pivots used in each pass.
(5)
(b)
Hence list the players in order, from highest score to lowest.
(1)
(c)
A tenth player, Jun, finishes last with a score of 70 and is added to the end of the original list. Find the pivot and the list after the first pass of a quick sort of the ten scores.
(2)
Show mark scheme
Answer
Mark
Notes
Part (a)
pass 1 pivot 58, the 5th item
M1
pass 1: 64, 81, 90, 73, 86, 58, 47, 39, 52
A1
pass 2 pivots 90 and 39: 90, 64, 81, 73, 86, 58, 47, 52, 39 ft
A1
pass 3 pivots 73 and 52: 90, 81, 86, 73, 64, 58, 52, 47, 39 ft
A1
pass 4 pivot 86, every item now a pivot or alone: 90, 86, 81, 73, 64, 58, 52, 47, 39
A1
Part (b)
Dev, Hugo, Ben, Farid, Ana, Ema, Iris, Chloe, Gia ft
B1
Part (c)
10 items, so the pivot is the 6th item, 73
B1
81, 90, 86, 73, 64, 47, 58, 39, 52, 70 ft on their pivot
B1
Common error: Choosing the pivot by value (the median score) instead of by position. The pivot is whatever item is in the middle position of the sublist, here the 5th of 9.
A list of eight numbers is being sorted into ascending order using a bubble sort, starting at the left-hand end of the list in each pass. Figure 1 shows the list at the start and the list at the end of the first pass, with two of the values in the second row replaced by question marks.
(a)
Find the two missing values, explaining how you obtain them.
(2)
(b)
Complete the bubble sort, giving the list at the end of each further pass.
(3)
(c)
Find the total number of comparisons and the total number of swaps made in the whole sort.
(2)
Show mark scheme
Answer
Mark
Notes
Part (a)
carrying out pass 1 on the start row: 45 and 12 swap, 45 and 38 swap, 71 moves right past 26, 59, 33 and 64
pass 5: no swaps, so the sort is complete: 12, 26, 33, 38, 45, 59, 64, 71
A1
Part (c)
comparisons 7 + 6 + 5 + 4 + 3 = 25
B1
swaps 6 + 2 + 2 + 1 + 0 = 11 ft
B1
Exam tip: The missing values must be two numbers from the start row that are not already shown in the second row (here 26 and 33), so you can check your answer by elimination as well as by running the pass.
Two computer programs, A and B, each process lists of n items. Figure 1 shows the time each program took for lists of 100, 200, …, 600 items.
(a)
Use the times for n = 200 and n = 400 to show that the times for program A are consistent with an algorithm of quadratic order.
(2)
(b)
State, with a reason, the order of program B.
(2)
(c)
Estimate the time program A takes for a list of 1500 items.
(2)
(d)
Use the graph to state the values of n for which program B is quicker than program A, explaining your answer.
(2)
Show mark scheme
Answer
Mark
Notes
Part (a)
0.8 s and 3.2 s read from the graph
M1
doubling n multiplies the time by 3.2 ÷ 0.8 = 4 = 22, as expected for quadratic order
A1
Part (b)
doubling n doubles the time, e.g. 1.2 s → 2.4 s (or the points lie on a straight line through the origin)
M1
linear order
A1
Part (c)
7.2 × (1500 ÷ 600)2
M1
45 seconds
A1
Part (d)
the two programs take the same time, 1.8 s, when n = 300
B1
A grows faster than B, so B is quicker for n > 300
B1
Exam tip: For an order question, use a pair of points where n doubles (or triples) and compare the factor by which the time changes: 2 for linear, 4 for quadratic, 8 for cubic.
Nine groups of walkers, of sizes 7, 2, 6, 9, 11, 3, 4, 5, 10 in the order in which they booked, are to be taken to the start of a walk in minibuses that each seat 16 people. A group must travel together. Sam tries to use the first-fit algorithm, taking the groups in the order given, and produces the allocation shown in Figure 1.
(a)
Explain why Sam’s allocation is not the result of the first-fit algorithm, identifying the first group that has been placed incorrectly.
(2)
(b)
Apply the first-fit algorithm correctly.
(3)
(c)
Calculate a lower bound for the number of minibuses needed, and hence state whether your allocation in part (b) is optimal.
(2)
Show mark scheme
Answer
Mark
Notes
Part (a)
the group of 3 was put in minibus 3, but it fits in minibus 2 (9 + 3 = 12 ≤ 16)
B1
first fit tries the minibuses in order from minibus 1 for every group; Sam only tried the most recent minibus and started a new one whenever a group did not fit it
B1
Part (b)
each group placed in the first minibus with enough seats, checking from minibus 1
M1
Minibus 1: 7, 2, 6 · Minibus 2: 9, 3, 4
A1
Minibus 3: 11, 5 · Minibus 4: 10, so 4 minibuses
A1
Part (c)
57 ÷ 16 = 3.56…, so the lower bound is 4
M1
4 minibuses = lower bound, so it is optimal ft
A1
Common error: Starting a new bin as soon as an item does not fit the most recent one, as Sam did. That is a different method, called next fit. First fit goes back to bin 1 for every new item, so the group of 3 belongs in minibus 2.
A carpenter needs ten pieces of timber with the following lengths, in cm: 85, 150, 60, 120, 40, 95, 135, 70, 110, 55 The pieces are to be cut from planks of length 240 cm. Assume that no length is lost in cutting.
(a)
Use a quick sort to arrange the lengths in descending order. Show the list after each pass and identify the pivots, taking the middle item of each sublist (right of centre for an even number of items).
(5)
(b)
Apply the first-fit decreasing algorithm to your ordered list to find how the pieces can be cut from the planks.
(3)
(c)
Calculate a lower bound for the number of planks needed.
(2)
(d)
State, with a reason, whether your answer to part (b) is optimal, and find the total length of timber left over.
Common error: Rounding 3.83 to the nearest whole number would happen to give 4 here, but the method is “round up”: a total of 725 cm would also need at least 4 planks, not 3.
A list of n numbers is stored as L(1), L(2), …, L(n). An algorithm is given below. Step 1: Let i = 2. Step 2: Let j = i. Step 3: If j = 1, go to Step 6. Step 4: If L(j − 1) ≤ L(j), go to Step 6. Step 5: Swap the values of L(j − 1) and L(j). Let j = j − 1. Go to Step 3. Step 6: Let i = i + 1. Step 7: If i ≤ n, go to Step 2. Otherwise stop. The algorithm is applied to the list 31, 17, 45, 12, 28.
(a)
Give the list each time Step 6 is reached.
(4)
(b)
Find the number of times Step 4 is carried out, and the number of swaps made.
(3)
(c)
State what the algorithm does, and show that for a list of n numbers in strictly decreasing order Step 4 is carried out ½n(n − 1) times.
(2)
(d)
Hence state the order of the algorithm, and estimate how long a list of 900 numbers in decreasing order takes, given that a list of 300 such numbers takes 0.5 seconds.
(2)
Show mark scheme
Answer
Mark
Notes
Part (a)
i = 2: 17, 31, 45, 12, 28
B1
i = 3: 17, 31, 45, 12, 28 (no swap)
B1
i = 4: 12, 17, 31, 45, 28
B1
i = 5: 12, 17, 28, 31, 45
B1
Part (b)
counts the comparisons for each value of i: 1, 1, 3, 3
M1
Step 4 carried out 8 times
A1
6 swaps
B1
Part (c)
it sorts the list into ascending order, and for a strictly decreasing list every comparison leads to a swap, so the item at position i is compared i − 1 times
M1
1 + 2 + … + (n − 1) = ½n(n − 1)
A1
Part (d)
quadratic order (n2)
B1
0.5 × (900 ÷ 300)2 = 4.5 seconds ft on their order
B1
Exam tip: Count what the question asks you to count. Step 4 is a comparison; it is carried out even when it leads to “go to Step 6”, so the 3 comparisons for i = 5 include the one that stops the inner loop.
A goods lift can carry at most 100 kg on each trip. Ten crates, with masses in kg, are waiting to go up in the order 42, 63, 19, 37, 56, 67, 59, 51, 55, 30 A crate cannot be split between trips, and the crates are the only load.
(a)
Calculate a lower bound for the number of trips needed.
(2)
(b)
Use the first-fit algorithm, taking the crates in the order given, to allocate the crates to trips.
(3)
(c)
Use the first-fit decreasing algorithm to allocate the crates to trips.
(3)
(d)
Show that it is not possible to take all the crates up in 5 trips, and hence state whether your answer to part (c) is optimal.
(3)
(e)
Explain why the first-fit allocation needed more trips than the first-fit decreasing allocation.
the six crates 67, 63, 59, 56, 55 and 51 each have mass more than 50 kg
M1
no two of them can go on the same trip (their total would exceed 100 kg), so at least 6 trips are needed
A1
(c) uses 6 trips, so it is optimal
A1
Part (e)
in first fit the small crates (19, 30, 37) were used up early, so the heavy crates near the end of the list had nothing to share a trip with
B1
Common error: Concluding that the first-fit decreasing answer is not optimal because 6 is more than the lower bound of 5. The lower bound only tells you that fewer than 5 trips is impossible; it need not be achievable.
A warehouse stocks eleven products with the following product codes: 655, 317, 846, 129, 574, 482, 215, 703, 260, 391, 538 The codes are first to be sorted into ascending order using a quick sort, and the sorted list is then to be searched.
(a)
Carry out the quick sort, choosing the middle item of each sublist as the pivot (right of centre for an even number of items). Show the list after each pass and identify the pivots.
(5)
(b)
Use a binary search on your sorted list to locate the code 538. Show your working.
(3)
(c)
Use a binary search to show that the code 400 is not in the list.
(3)
(d)
Write down the maximum number of iterations a binary search of eleven items can need.
Exam tip: In pass 4 the list is already in order, but the sublists 317, 391 and 655, 703 have not yet been split by a pivot. The quick sort is only complete when every item has been a pivot or is alone in its sublist.
Figure 1 shows a flow chart for an algorithm that is applied to a list of n numbers L(1), L(2), …, L(n). If m = k in box 9, the list is unchanged. The algorithm is applied to the list 23, 41, 17, 35, 29
(a)
Give the list each time box 9 has been carried out, stating the value of m used.
(4)
(b)
Find the number of times box 5 is used and the number of times box 6 is used.
(3)
(c)
Explain why, for any list of n numbers, box 5 is used ½n(n − 1) times.
(2)
(d)
A computer takes 0.8 seconds to apply the algorithm to a list of 2000 numbers. State the order of the algorithm and estimate the time it would take for a list of 6000 numbers.
(2)
Show mark scheme
Answer
Mark
Notes
Part (a)
k = 5: m = 2, list 23, 29, 17, 35, 41
M1
k = 4: m = 4, list unchanged 23, 29, 17, 35, 41
A1
k = 3: m = 2, list 23, 17, 29, 35, 41
A1
k = 2: m = 1, list 17, 23, 29, 35, 41
A1
Part (b)
box 5 is used k − 1 times for each value of k: 4 + 3 + 2 + 1
M1
box 5: 10 times
A1
box 6: 4 times
B1
Part (c)
the number of comparisons does not depend on the values: for each k = n, n − 1, …, 2, box 5 is used for i = 2, …, k, i.e. k − 1 times
M1
(n − 1) + (n − 2) + … + 1 = ½n(n − 1)
A1
Part (d)
quadratic order
B1
0.8 × (6000 ÷ 2000)2 = 7.2 seconds ft on their order
B1
Exam tip: Track m as a position, not a value. In box 5 compare the number in position i with the number in position m, and when the inner loop ends swap the numbers in positions m and k.
Eleven crates, A to K, arrive at a loading bay in alphabetical order. Their masses are shown in Figure 1. The crates are to be moved on trolleys, each of which can carry at most 100 kg. A crate cannot be split between trolleys.
(a)
Calculate a lower bound for the number of trolleys needed.
(2)
(b)
Use the first-fit algorithm, taking the crates in alphabetical order, to allocate the crates to trolleys.
(3)
(c)
Use the first-fit decreasing algorithm to allocate the crates to trolleys.
(3)
(d)
Find an allocation of the crates that uses only four trolleys.
(3)
(e)
Explain why your allocation in part (d) is optimal.
looks for groups with totals close to 100 kg, the total spare capacity being only 15 kg
M1
two correct trolleys, e.g. 54 + 42 = 96 and 47 + 38 + 14 = 99
A1
the rest on two more, e.g. 41 + 36 + 23 = 100 and 34 + 32 + 24 = 90: 4 trolleys (any correct 4-trolley allocation)
A1
Part (e)
it uses 4 trolleys, which equals the lower bound, so no allocation can use fewer
B1
Exam tip: When both first fit and first-fit decreasing miss the lower bound, find the total spare capacity (here 4 × 100 − 385 = 15 kg). Every trolley in a 4-trolley allocation must then carry at least 85 kg, which narrows the search.
A garden centre keeps an alphabetical list of the twelve trees it sells: Ash, Beech, Cedar, Elm, Fir, Hazel, Larch, Maple, Oak, Pine, Rowan, Yew The list is searched using a binary search in which the middle position of the list first, …, last is ⌈(first + last)/2⌉. Figure 1 shows, as a tree, the positions that can be inspected in each iteration.
(a)
Use a binary search to locate Rowan. Show your working and check that your iterations follow a path down the tree in Figure 1.
(3)
(b)
Use Figure 1 to list the trees that need the greatest number of iterations to be found.
(2)
(c)
Each tree on the list is equally likely to be searched for. Find the mean number of iterations needed to find it.
(2)
(d)
A customer asks for a Holly tree. Use a binary search to show that it is not on the list, stating the number of iterations needed.
(2)
(e)
The list grows to 1000 trees. Find the maximum number of iterations now needed, and describe how this number changes as the length of the list doubles.
(2)
Show mark scheme
Answer
Mark
Notes
Part (a)
position ⌈(1 + 12)/2⌉ = 7, Larch: Rowan is after, keep 8–12
M1
position 10, Pine: keep 11–12; position 12, Yew: keep 11–11
A1
position 11, Rowan: found after 4 iterations, path 7 → 10 → 12 → 11
A1
Part (b)
the bottom level of the tree, positions 1, 3, 5, 8, 11 (4 iterations)
M1
Ash, Cedar, Fir, Maple, Rowan
A1
Part (c)
1 × 1 + 2 × 2 + 4 × 3 + 5 × 4 = 37
M1
37 ÷ 12 = 3.08 (3 s.f.)
A1
Part (d)
Larch (position 7): Holly is before, keep 1–6; Elm (position 4): after, keep 5–6
M1
Hazel (position 6): after, keep 7–6, which is empty: not on the list after 3 iterations
A1
Part (e)
29 = 512 ≤ 1000 < 1024 = 210, so at most 10
B1
doubling the length increases the maximum by only 1 (it grows like log2n)
B1
Exam tip: Each level of the tree is one iteration, so the depth of the tree is the maximum number of iterations. An unsuccessful search ends below a node, after the last item inspected, without adding an extra iteration.
A laboratory has ten tests, A to J, to run on a machine. Figure 1 shows the time, in minutes, that each test takes. The machine is booked in sessions of 60 minutes, and a test cannot be split between sessions.
(a)
Use a bubble sort, starting at the left-hand end of the list in each pass, to arrange the times in the order A to J into descending order. Give the list at the end of each pass.
(4)
(b)
Find the total number of comparisons made in your bubble sort.
(1)
(c)
Apply the first-fit decreasing algorithm to allocate the tests to sessions.
(3)
(d)
Calculate a lower bound for the number of sessions needed.
(2)
(e)
Use full bins to find an allocation of the tests to three sessions, naming the tests in each session, and explain why it is optimal.
(3)
Show mark scheme
Answer
Mark
Notes
Part (a)
a pair is swapped when the left time is smaller than the right one
every session must be exactly 60 minutes, e.g. G + D + H = 30 + 17 + 13 = 60
M1
A + E + I = 28 + 18 + 14 = 60 and B + C + J + F = 27 + 20 + 7 + 6 = 60 (any correct allocation)
A1
3 sessions = lower bound, so it is optimal
A1
Common error: Stopping the bubble sort after pass 6 because the list looks sorted. The algorithm only knows it has finished when a pass makes no swaps, so pass 7 must be shown (or the reason it is not needed stated).
We use essential cookies to make this site work. With your permission we'd also use analytics and advertising cookies to understand which resources help students most and how families find us. Nothing optional is set unless you accept. Privacy policy
EssentialNeeded for the site and your cookie choice to work.
Always on
AnalyticsAnonymous visit statistics that help improve the free resources.
MarketingMeasures whether ads reach the right families. Off unless you turn it on.