OCR D1 (Decision Mathematics 1) 2005 June

1

1. 1. Use the first-fit decreasing method to pack these weights, in kg, into bags that can each hold a maximum of 10 kg . $$\begin{array} { l l l l l l l l l l } 2 & 7 & 5 & 3 & 3 & 4 & 3 & 2 & 8 & 3 \end{array}$$
   2. Find a packing that uses fewer bags.
2. The order of a particular algorithm is a cubic function of the number of input values. It takes 4 seconds for the algorithm to process 100 input values. Approximately how many seconds will it take the algorithm to process 500 input values?

2 A simple graph is one which has no repeated arcs and no arc that joins a vertex to itself.

1. Draw a simple graph that connects four vertices using five arcs.
2. Explain why, in any graph, there must be an even number of odd vertices.
3. By considering the orders of the vertices, show that there is only one possible simple graph that connects four vertices using five arcs.

3 This diagram shows a network.
\includegraphics[max width=\textwidth, alt={}, center]{9aa57bb0-3d88-4858-a348-ff95592fa659-2_693_744_1307_694}

1. Obtain a minimum connector for this network. Draw your minimum connector, state the order in which the arcs were chosen and give their total weight.
2. Use the nearest neighbour method, starting from vertex \(A\), to find a cycle that passes through every vertex. The network represents a cubical die, with vertices labelled \(A\) to \(H\), and faces numbered from 1 to 6 in such a way that the numbers on each pair of opposite faces add up to 7 . When two faces meet in an edge, the sum of the numbers on the two faces is recorded as the weight on that edge.
3. (a) List the vertices of each of the two faces that meet in the edge \(A G\).
   (b) What number is on the face \(A C E G\) ?
   (c) Which face is numbered 3?

4 [Answer this question on the insert provided.]
\includegraphics[max width=\textwidth, alt={}, center]{9aa57bb0-3d88-4858-a348-ff95592fa659-3_918_1242_351_443} In this network the vertices represent towns, the arcs represent roads and the weights on the arcs show the lengths of roads in kilometres.

1. Use Dijkstra's algorithm on the diagram in the insert to find the length of the shortest path from \(A\) to each of the other vertices. You must show your working, including temporary labels, permanent labels and the order in which the permanent labels were assigned. Find the route of the shortest path from \(A\) to \(G\). The total weight of the arcs is 120 kilometres.
2. By using an appropriate algorithm, find the length of a shortest route that uses every road starting and ending at \(A\). You should explain your method.
3. Find the length of a shortest route that uses every road starting at \(A\) and ending at \(G\). You should explain your method.

5 Consider the following algorithm which is to be applied to a list of numbers.

1. Apply the algorithm to this list. $$\begin{array} { l l l l l } 3 & 6 & 5 & 7 & 3 \end{array}$$ Record in a table the values of \(X , N , T\) and \(S\) at each pass through Step 3 and give the output values.
2. Write down the number of additions and the number of multiplications that are done in Step 3 for a list of five numbers. Hence find the total number of arithmetic operations (additions, multiplications, divisions, subtractions and square roots) that are done in Step 3 and Step 5 when applying the algorithm to a list of five numbers.
3. Find an expression for the total number of arithmetic operations that are done in applying the algorithm to a list of \(n\) numbers.
4. The total number of arithmetic operations can be used as a measure of the run-time for the algorithm. If it takes approximately 2 seconds to apply the algorithm to a list of 1000 numbers, approximately how long will it take to apply the algorithm to a list of 5000 numbers?