Algorithms

Hiro uses a sorting algorithm to sort the heights in cm of 8 people into ascending order.

At the end of the first pass through the algorithm, Hiro ends up with the list below:

142 165 152 135 171 154 172 182

If Hiro used the shuttle sort algorithm, write down the possibilities for the original list.

Hiro actually used the bubble sort algorithm starting at the left-hand side.

Complete the second and third passes using the bubble sort algorithm.

You should show the list that results at the end of each pass.

In total, Hiro needed 5 passes to complete the bubble sort algorithm.

In total, the shuttle sort algorithm would take 12 comparisons to sort the original list into ascending order.

Using the total number of comparisons for each algorithm, compare the efficiency of

bubble sort and shuttle sort for sorting the heights of the 8 people.

It takes a computer 2.4 × 10^-3 seconds to sort a list of 300 numbers into ascending order using the bubble sort algorithm.

Find the approximate length of a list the computer could sort in 1 minute. Give your answer

to 1 significant figure.

Write down a way in which the nearest neighbour method can fail to solve the problem of

finding a least weight cycle through all the vertices of a network.

Explain why, when trying to find a least weight cycle through all the vertices of a network, an

ad hoc method may be preferable to an algorithmic approach.

The distance matrix below represents a network connecting six viewpoints A, B, C, D, E and F. The distance matrix shows the direct distances between each pair of viewpoints where a direct route exists. The distances are measured in km. A blank shows that there is no direct route between the two viewpoints.

Draw the network on the vertices given in the Printed Answer Booklet.

Apply the nearest neighbour method, starting from A.

A hiker wants to travel between the six viewpoints, starting and finishing at A. The hiker must visit every viewpoint at least once, but may visit a viewpoint more than once.

Show that the hiker does not need to travel as far as 50 km.

Use an appropriate algorithm to find the shortest distance from F to each of the other

viewpoints.

Complete the table in the Printed Answer Book to show the shortest distance between each

pair of viewpoints.

Use your answer to part (g) to find a lower bound for the distance the hiker must travel by

initially deleting vertex A.

A list of 8 values is given below.

3 24 8 1 4 20 30 18

The list is to be sorted into increasing order using quick sort, as given in the Formulae Booklet.

Carry out the first two passes of the sort.

A different list of 8 values is to be sorted into increasing order using quick sort, as given in the Formulae Booklet.

State the maximum number of passes that could be required.

Find the minimum number of passes that could be required.

The run-time for quick sort could be measured by counting the number of comparisons used.

In the worst case, the run time for quick sort is O(n²).

A computer takes at most 0.03 seconds to sort a list of 100 values into increasing order using quick sort.

Calculate an estimate for the time taken, in the worst case, to sort a list of 500 values using

quick sort.

A list of n values (where n > 10) is to be sorted into increasing order using quick sort, as given in the Formulae Booklet.

Explain why, in the best case, n - 3 comparisons are used in the second pass.

A building has 7 CCTV cameras, A to G, at the junctions of some of the corridors.

The cameras at the junctions and the lengths of the 11 corridors between them, in metres, are shown in the table below.

Model this information as a network.

Use an appropriate algorithm to calculate the minimum distance from A to each of the other

vertices.

The run‑time of an algorithm for finding this minimum distance is proportional to the total number of comparisons used. For a network with n vertices, the worst case is when the algorithm is applied to a network based on the complete graph K_n.

In each pass

• A vertex is made permanent and the temporary label at all adjacent vertices that are not yet permanent are updated. This uses 1 comparison for every such vertex (adjacent to the permanent label) that previously already had a temporary label.

• The best temporary labels at all vertices that do not yet have permanent labels are then compared to determine the next vertex to become permanent. If there are k such vertices this involves k - 1 comparisons.

By considering the number of comparisons of each type in each iteration, show that the algorithm uses a total of 6 comparisons when it is applied to a network based on the complete

graph K₄.

You are given that the total number of comparisons used when the algorithm is applied to a network based on K_n is (n - 1)(n - 2).

A computer takes 0.03 seconds to apply this algorithm on a network based on K₇.

Calculate, to 1 decimal place, how many seconds it will take the computer to apply the

algorithm to a network based on K₇₀.

The manager wants to construct a tour (a closed route) that passes each camera.

Find a lower bound for the length of this tour by initially deleting D.

Find an upper bound for the length of this tour by using the nearest neighbour algorithm

starting from D.

Deduce the length of the shortest possible tour. Briefly explain your reasoning.

Explain carefully how you know that the graph K₅ has thickness 2.

The following colouring algorithm can be used to determine whether a connected graph is bipartite or not. The algorithm colours each vertex of a graph in one of two colours, α and β.

STEP 1 Choose a vertex and assign it colour α.

STEP 2 If any vertex is adjacent to another vertex of the same colour, jump to STEP 5. Otherwise assign colour β to each vertex that is adjacent to a vertex with colour α.

STEP 3 If any vertex is adjacent to another vertex of the same colour, jump to STEP 5. Otherwise assign colour α to each vertex that is adjacent to a vertex with colour β.

STEP 4 Repeat STEP 2 and STEP 3 until all vertices are coloured.

STEP 5 If there are no adjacent vertices of the same colour then the graph is bipartite. Otherwise the graph is not bipartite.

STEP 6 Stop.

Apply this algorithm to graph A, starting with the vertex in the top left corner, to determine

whether graph A is bipartite or not.

The worst case is when the graph is a path that starts at one vertex and ends at another, having passed through each of the other vertices once.

What can you deduce about the efficiency of the colouring algorithm in this worst case?

The colouring algorithm is used on two graphs, X and Y. It takes 10 seconds to run for graph X and 60 seconds to run for graph Y. Graph X has 1000 vertices.

Estimate the number of vertices in graph Y.

A different algorithm has efficiency O(2ⁿ). This algorithm takes 10 seconds to run for graph X.

Explain why you would expect this algorithm to take longer than 60 seconds to run for graph Y.

A network is formed by weighting the graph below using the listed arc weights.

Show the result after the first pass and after the second pass, when the list of weights is

sorted into increasing order using bubble sort.

Show the result after the first pass and after the second pass, when the list of weights is

sorted into increasing order using shuttle sort.

In the remaining passes of bubble sort another 14 comparisons are made. In the remaining passes of shuttle sort another 11 comparisons are made. The total number of swaps needed is the same for both sorting methods.

Use the total number of comparisons and the total number of swaps to compare the efficiency

of bubble sort and shuttle sort for sorting this list of weights.

The sorted list of arc weights for the network is as follows.

0.9 1.5 2.3 2.9 3.5 4.2 4.7 5.3

These weights can be given to the arcs of the graph in several ways to form different networks.

What is the smallest weight that does not have to appear in a minimum spanning tree for

any of these networks? You must explain your reasoning.

Show a way of weighting the arcs, using the weights in the list, that results in the largest possible total for a minimum spanning tree. You should state the total weight of your

minimum spanning tree.

Determine the total weight of an optimal solution of the route inspection problem for the

network found in part (c)(ii).