Hard Further Maths Algorithms Questions

Challenging, exam-style Further Maths Algorithms questions with worked solutions. Stretch yourself on the hardest sorting, bubble-sort, quick-sort, pivots problems.

sortingbubble-sortquick-sortpivotsmerge-sortsearching
Further Maths34 questionsStep-by-step solutions
Question 1
9 markschallenging
A flow chart carries out the Euclidean algorithm. Box 1: input the positive integers A=4935A=4935 and B=3050B=3050. Box 2: let RR be the remainder when AA is divided by BB. Box 3: if R=0R=0, output BB and stop. Box 4: otherwise replace AA by BB and BB by RR, then return to Box 2. State the value that is output by the flow chart.
Show worked solution

Worked solution

  1. Write down the input values

    A=4935,B=3050A=4935,\quad B=3050

    Box 1 reads in the two positive integers.

  2. Carry out the next 2 divisions

    4935=1×3050+1885; 3050=1×1885+11654935=1\times 3050+1885;\ 3050=1\times 1885+1165

    Each time, A is replaced by B and B by the remainder.

  3. Note when the flow chart stops

    R=0⇒output B=5R=0\Rightarrow\text{output }B=5

    The last non-zero remainder is the highest common factor.

  4. List the remainders produced

    1885, 1165, 720, 445, 275, 170, 105, 65, 40, 25, 15, 10, 5, 01885,\ 1165,\ 720,\ 445,\ 275,\ 170,\ 105,\ 65,\ 40,\ 25,\ 15,\ 10,\ 5,\ 0

    The remainders strictly decrease, so the flow chart must terminate.

  5. Count the times Box 2 is carried out

    divisions=14\text{divisions}=14

    One division is done for each pass round the loop.

  6. Check that the output divides both inputs

    4935=5×987,3050=5×6104935=5\times 987,\quad 3050=5\times 610

    The output is a common factor of the two inputs.

  7. Check that no larger common factor exists

    gcd⁡(987,610)=1\gcd\left(987,610\right)=1

    The two quotients share no factor, so 5 is the highest common factor.

  8. Note the order of the Euclidean algorithm

    order log⁡(min⁡(A,B))\text{order }\log\left(\min\left(A,B\right)\right)

    The Euclidean algorithm is extremely fast even for huge inputs.

  9. Recall what a sorted list means

    ascending order: a1≤a2≤⋯≤an\text{ascending order: }a_{1}\le a_{2}\le\cdots\le a_{n}

    Every item must be no larger than the item that follows it.

  10. Recall the number of comparisons in one bubble-sort pass

    pass k makes n−k comparisons\text{pass }k\text{ makes }n-k\text{ comparisons}

    Each pass leaves one more item in its final place, so it is one comparison shorter.

  11. Recall the worst case for a bubble sort

    12n(n−1) comparisons\tfrac{1}{2}n\left(n-1\right)\text{ comparisons}

    A reversed list forces every possible comparison to be made.

  12. Note the order of a bubble sort

    bubble sort has order n2\text{bubble sort has order }n^{2}

    Doubling the length of the list roughly quadruples the running time.

  13. Note the order of a binary search

    binary search has order log⁡n\text{binary search has order }\log n

    Each pass halves the number of items still under consideration.

  14. Recall the lower bound for a bin-packing problem

    bins≥⌈total sizecapacity⌉\text{bins}\ge\left\lceil\frac{\text{total size}}{\text{capacity}}\right\rceil

    No packing can use fewer bins than this, though the bound need not be attainable.

  15. Note that bin-packing algorithms are heuristics

    first-fit need not give the optimal packing\text{first-fit need not give the optimal packing}

    A heuristic gives a good solution quickly but not necessarily the best one.

  16. State the value output

    output=5\text{output}=5

    The flow chart outputs the highest common factor of 4935 and 3050.

Answer
55
Question 2
9 markschallenging
A flow chart carries out the following instructions. Box 1: input N=7N=7. Box 2: if N=1N=1, output the number of times Box 3 has been carried out and stop. Box 3: if NN is even replace NN by N2\frac{N}{2}, otherwise replace NN by 3N+13N+1; then return to Box 2. State the value that is output by the flow chart.
Show worked solution

Worked solution

  1. Write down the input value

    N=7N=7

    Box 1 reads in the starting value.

  2. Apply Box 3 to N=7N=7 down to N=22N=22

    7→22→117\to22\to11

    The rule is applied once for each value in this chain.

  3. Apply Box 3 to N=11N=11 down to N=34N=34

    11→34→1711\to34\to17

    The rule is applied once for each value in this chain.

  4. Apply Box 3 to N=17N=17 down to N=52N=52

    17→52→2617\to52\to26

    The rule is applied once for each value in this chain.

  5. Apply Box 3 to N=26N=26 down to N=13N=13

    26→13→4026\to13\to40

    The rule is applied once for each value in this chain.

  6. Apply Box 3 to N=40N=40 down to N=20N=20

    40→20→1040\to20\to10

    The rule is applied once for each value in this chain.

  7. Apply Box 3 to N=10N=10 down to N=5N=5

    10→5→1610\to5\to16

    The rule is applied once for each value in this chain.

  8. Apply Box 3 to N=16N=16 down to N=8N=8

    16→8→416\to8\to4

    The rule is applied once for each value in this chain.

  9. Apply Box 3 to N=4N=4 down to N=2N=2

    4→2→14\to2\to1

    The rule is applied once for each value in this chain.

  10. Note when the flow chart stops

    N=1⇒output the number of times Box 3 was usedN=1\Rightarrow\text{output the number of times Box 3 was used}

    Box 2 stops the flow chart as soon as N=1N=1.

  11. Write out the whole chain of values

    7→22→11→34→17→52→26→13→40→20→10→5→16→8→4→2→17\to22\to11\to34\to17\to52\to26\to13\to40\to20\to10\to5\to16\to8\to4\to2\to 1

    The chain has 16 arrows, one for each use of Box 3.

  12. Count the times the halving rule is used

    even=11,odd=5\text{even}=11,\quad\text{odd}=5

    Every use of the 3N+13N+1 rule is followed by a halving.

  13. Find the largest value reached

    max⁡=52\max=52

    The chain can rise well above its starting value before it falls.

  14. Check the last few steps of the chain

    4→2→14\to 2\to 1

    Every chain of this kind finishes with the same three values.

  15. State the number that is output

    output=16\text{output}=16

    Box 3 is carried out 16 times before NN reaches 11.

Answer
1616
Question 3
9 markschallenging
12 items of sizes 9, 5, 7, 4, 8, 6, 3, 9, 2, 5, 7, 49,\ 5,\ 7,\ 4,\ 8,\ 6,\ 3,\ 9,\ 2,\ 5,\ 7,\ 4 are to be packed into bins of capacity 1616. The first-fit algorithm is used: each item, taken in the order in which it is listed, is placed into the first bin that has room for it. How many bins are used?
Show worked solution

Worked solution

  1. Find the total size of the items

    9+5+7+4+8+6+3+9+2+5+7+4=699+5+7+4+8+6+3+9+2+5+7+4=69

    The total size decides how many bins are needed at the very least.

  2. Work out a lower bound for the number of bins

    ⌈6916⌉=5\left\lceil\frac{69}{16}\right\rceil=5

    At least 5 bins are needed, whatever algorithm is used.

  3. Place the item of size 9

    9→bin 19\to\text{bin }1

    It goes into the first bin with enough room left.

  4. Place the item of size 5

    5→bin 15\to\text{bin }1

    It goes into the first bin with enough room left.

  5. Place the item of size 7

    7→bin 27\to\text{bin }2

    It goes into the first bin with enough room left.

  6. Place the item of size 4

    4→bin 24\to\text{bin }2

    It goes into the first bin with enough room left.

  7. Place the item of size 8

    8→bin 38\to\text{bin }3

    It goes into the first bin with enough room left.

  8. Place the item of size 6

    6→bin 36\to\text{bin }3

    It goes into the first bin with enough room left.

  9. Place the item of size 3

    3→bin 23\to\text{bin }2

    It goes into the first bin with enough room left.

  10. Place the item of size 9

    9→bin 49\to\text{bin }4

    It goes into the first bin with enough room left.

  11. Place the item of size 2

    2→bin 12\to\text{bin }1

    It goes into the first bin with enough room left.

  12. Place the item of size 5

    5→bin 45\to\text{bin }4

    It goes into the first bin with enough room left.

  13. Place the item of size 7

    7→bin 57\to\text{bin }5

    It goes into the first bin with enough room left.

  14. Place the item of size 4

    4→bin 54\to\text{bin }5

    It goes into the first bin with enough room left.

  15. State the contents of the bins

    9, 5, 2 ∣ 7, 4, 3 ∣ 8, 6 ∣ 9, 5 ∣ 7, 49,\ 5,\ 2\ \mid\ 7,\ 4,\ 3\ \mid\ 8,\ 6\ \mid\ 9,\ 5\ \mid\ 7,\ 4

    This packing uses 5 bins.

  16. Find the total in each bin

    9+5+2=16; 7+4+3=14; 8+6=14; 9+5=14; 7+4=119+5+2=16;\ 7+4+3=14;\ 8+6=14;\ 9+5=14;\ 7+4=11

    No bin holds more than the capacity of 16.

  17. State the number of bins used

    bins used=5\text{bins used}=5

    This is the number of bins the algorithm uses.

Answer
55
Question 4
9 markschallenging
12 items of sizes 9, 5, 7, 4, 8, 6, 3, 9, 2, 5, 7, 49,\ 5,\ 7,\ 4,\ 8,\ 6,\ 3,\ 9,\ 2,\ 5,\ 7,\ 4 are to be packed into bins of capacity 1616. The first-fit decreasing algorithm is used: the sizes are first rewritten in decreasing order and the first-fit algorithm is then applied, so that each item is placed into the first bin that has room for it. How much space is left unused in the bins?
Show worked solution

Worked solution

  1. Find the total size of the items

    9+5+7+4+8+6+3+9+2+5+7+4=699+5+7+4+8+6+3+9+2+5+7+4=69

    The total size decides how many bins are needed at the very least.

  2. Work out a lower bound for the number of bins

    ⌈6916⌉=5\left\lceil\frac{69}{16}\right\rceil=5

    At least 5 bins are needed, whatever algorithm is used.

  3. Rewrite the sizes in decreasing order

    9, 9, 8, 7, 7, 6, 5, 5, 4, 4, 3, 29,\ 9,\ 8,\ 7,\ 7,\ 6,\ 5,\ 5,\ 4,\ 4,\ 3,\ 2

    First-fit decreasing sorts the items before packing them.

  4. Place the items of sizes 9,\ 9

    9→bin 1; 9→bin 29\to\text{bin }1;\ 9\to\text{bin }2

    Each item goes into the first bin that has room for it.

  5. Place the items of sizes 8,\ 7

    8→bin 3; 7→bin 18\to\text{bin }3;\ 7\to\text{bin }1

    Each item goes into the first bin that has room for it.

  6. Place the items of sizes 7,\ 6

    7→bin 2; 6→bin 37\to\text{bin }2;\ 6\to\text{bin }3

    Each item goes into the first bin that has room for it.

  7. Place the items of sizes 5,\ 5

    5→bin 4; 5→bin 45\to\text{bin }4;\ 5\to\text{bin }4

    Each item goes into the first bin that has room for it.

  8. Place the items of sizes 4,\ 4

    4→bin 4; 4→bin 54\to\text{bin }4;\ 4\to\text{bin }5

    Each item goes into the first bin that has room for it.

  9. Place the items of sizes 3,\ 2

    3→bin 5; 2→bin 33\to\text{bin }5;\ 2\to\text{bin }3

    Each item goes into the first bin that has room for it.

  10. State the contents of the bins

    9, 7 ∣ 9, 7 ∣ 8, 6, 2 ∣ 5, 5, 4 ∣ 4, 39,\ 7\ \mid\ 9,\ 7\ \mid\ 8,\ 6,\ 2\ \mid\ 5,\ 5,\ 4\ \mid\ 4,\ 3

    This packing uses 5 bins.

  11. Work out the unused space

    5×16−69=115\times 16-69=11

    The unused space is the space in the bins minus the total size.

  12. Find the total in each bin

    9+7=16; 9+7=16; 8+6+2=16; 5+5+4=14; 4+3=79+7=16;\ 9+7=16;\ 8+6+2=16;\ 5+5+4=14;\ 4+3=7

    No bin holds more than the capacity of 16.

  13. Find the spare room in each bin

    (0, 0, 0, 2, 9)\left(0,\ 0,\ 0,\ 2,\ 9\right)

    These spare amounts total 11.

  14. Compare the packing with the lower bound

    5 bins used,lower bound=55\text{ bins used},\quad\text{lower bound}=5

    The packing achieves the lower bound.

  15. Note that the algorithm is a heuristic

    5≥55\ge 5

    The number of bins used can never be below the lower bound.

  16. State the unused space

    unused space=11\text{unused space}=11

    This is the total space left over in the bins.

Answer
1111
Question 5
9 markschallenging
12 items of sizes 9, 5, 7, 4, 8, 6, 3, 9, 2, 5, 7, 49,\ 5,\ 7,\ 4,\ 8,\ 6,\ 3,\ 9,\ 2,\ 5,\ 7,\ 4 are to be packed into bins of capacity 1616. The first-fit decreasing algorithm is used: the sizes are first rewritten in decreasing order and the first-fit algorithm is then applied, so that each item is placed into the first bin that has room for it. Which of the following shows the contents of the bins that are used?
Show worked solution

Worked solution

  1. Find the total size of the items

    9+5+7+4+8+6+3+9+2+5+7+4=699+5+7+4+8+6+3+9+2+5+7+4=69

    The total size decides how many bins are needed at the very least.

  2. Work out a lower bound for the number of bins

    ⌈6916⌉=5\left\lceil\frac{69}{16}\right\rceil=5

    At least 5 bins are needed, whatever algorithm is used.

  3. Rewrite the sizes in decreasing order

    9, 9, 8, 7, 7, 6, 5, 5, 4, 4, 3, 29,\ 9,\ 8,\ 7,\ 7,\ 6,\ 5,\ 5,\ 4,\ 4,\ 3,\ 2

    First-fit decreasing sorts the items before packing them.

  4. Place the items of sizes 9,\ 9

    9→bin 1; 9→bin 29\to\text{bin }1;\ 9\to\text{bin }2

    Each item goes into the first bin that has room for it.

  5. Place the items of sizes 8,\ 7

    8→bin 3; 7→bin 18\to\text{bin }3;\ 7\to\text{bin }1

    Each item goes into the first bin that has room for it.

  6. Place the items of sizes 7,\ 6

    7→bin 2; 6→bin 37\to\text{bin }2;\ 6\to\text{bin }3

    Each item goes into the first bin that has room for it.

  7. Place the items of sizes 5,\ 5

    5→bin 4; 5→bin 45\to\text{bin }4;\ 5\to\text{bin }4

    Each item goes into the first bin that has room for it.

  8. Place the items of sizes 4,\ 4

    4→bin 4; 4→bin 54\to\text{bin }4;\ 4\to\text{bin }5

    Each item goes into the first bin that has room for it.

  9. Place the items of sizes 3,\ 2

    3→bin 5; 2→bin 33\to\text{bin }5;\ 2\to\text{bin }3

    Each item goes into the first bin that has room for it.

  10. Find the total in each bin

    9+7=16; 9+7=16; 8+6+2=16; 5+5+4=14; 4+3=79+7=16;\ 9+7=16;\ 8+6+2=16;\ 5+5+4=14;\ 4+3=7

    No bin holds more than the capacity of 16.

  11. Find the spare room in each bin

    (0, 0, 0, 2, 9)\left(0,\ 0,\ 0,\ 2,\ 9\right)

    These spare amounts total 11.

  12. Compare the packing with the lower bound

    5 bins used,lower bound=55\text{ bins used},\quad\text{lower bound}=5

    The packing achieves the lower bound.

  13. Note that the algorithm is a heuristic

    5≥55\ge 5

    The number of bins used can never be below the lower bound.

  14. Recall what a sorted list means

    ascending order: a1≤a2≤⋯≤an\text{ascending order: }a_{1}\le a_{2}\le\cdots\le a_{n}

    Every item must be no larger than the item that follows it.

  15. Select the option giving the contents of the bins

    9, 7 ∣ 9, 7 ∣ 8, 6, 2 ∣ 5, 5, 4 ∣ 4, 39,\ 7\ \mid\ 9,\ 7\ \mid\ 8,\ 6,\ 2\ \mid\ 5,\ 5,\ 4\ \mid\ 4,\ 3

    This is the packing produced by the algorithm.

Answer
9, 7 ∣ 9, 7 ∣ 8, 6, 2 ∣ 5, 5, 4 ∣ 4, 39,\ 7\ \mid\ 9,\ 7\ \mid\ 8,\ 6,\ 2\ \mid\ 5,\ 5,\ 4\ \mid\ 4,\ 3

Unlock 29 more Algorithms questions

Create a free account to work through every Further Maths Algorithms question with instant step-by-step worked solutions, progress tracking and interactive lessons.

  • Full worked solutions for every question
  • Interactive lessons and instant feedback
  • Track your mastery across every topic
Create a Free Account

No card required · Free forever

More Algorithms practice

Practice QuestionsWorked Solutions

Related Decision Maths topics

Allocation (assignment)Critical path analysisDecision analysisDynamic programmingFlows in networksGame theory