Further Maths Algorithms Practice Questions

Write down the list to be sorted

The bubble sort starts from the list in the order given.

State the list at the end of pass 1

The largest 1 item(s) are now in their final places.

Select the option that gives the list after the first pass

This is the list produced by pass 1.

Write down the starting values

Box 1 initialises the two variables.

Carry out the loop for $K=1$ to $K=5$

Box 2 adds $K^{2}$ to $S$ and Box 3 increases $K$ by one; after this $S=55$.

Note when the loop stops

Box 4 sends the flow chart to the output box.

State the value output

This is the value printed by the flow chart.

Write down the input values

Box 1 reads in the two positive integers.

Divide 1071 by 462 and record the remainder

The remainder is 147, so A becomes 462 and B becomes 147.

Divide 462 by 147 and record the remainder

The remainder is 21, so A becomes 147 and B becomes 21.

Divide 147 by 21 and record the remainder

The remainder is 0, so the algorithm stops.

Note when the flow chart stops

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

State the value output

The flow chart outputs the highest common factor of 1071 and 462.

Write down the input value

Box 1 reads in the starting value.

Apply Box 3 to $N=13$ down to $N=40$

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

Apply Box 3 to $N=20$ down to $N=10$

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

Apply Box 3 to $N=5$ down to $N=16$

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

Apply Box 3 to $N=8$ down to $N=4$

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

Apply Box 3 to $N=2$

2 is even, so the halving rule is used.

Note when the flow chart stops

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

Write out the whole chain of values

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

Count the times the halving rule is used

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

Find the largest value reached

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

State the number that is output

Box 3 is carried out 9 times before $N$ reaches $1$.

Write down the input values

Box 1 reads in the two positive integers.

Carry out the next 2 divisions

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

Note when the flow chart stops

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

List the remainders produced

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

Count the times Box 2 is carried out

One division is done for each pass round the loop.

Check that the output divides both inputs

The output is a common factor of the two inputs.

Check that no larger common factor exists

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

Note the order of the Euclidean algorithm

The Euclidean algorithm is extremely fast even for huge inputs.

Recall what a sorted list means

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

Recall the number of comparisons in one bubble-sort pass

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

Recall the worst case for a bubble sort

A reversed list forces every possible comparison to be made.

Note the order of a bubble sort

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

Note the order of a binary search

Each pass halves the number of items still under consideration.

Recall the lower bound for a bin-packing problem

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

Note that bin-packing algorithms are heuristics

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

State the value output

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