OCR MEI D1 (Decision Mathematics 1) 2010 June

1

1. Use Dijkstra's algorithm to find the shortest distances and corresponding routes from A to each of the other vertices in the given network.
   \includegraphics[max width=\textwidth, alt={}, center]{839adc96-1bea-44ef-917e-f03e396a3061-2_588_792_632_632}
2. If the shortest distances and routes between every pair of vertices are required how many applications of Dijkstra will be needed?

2 The following steps define an algorithm which acts on two numbers.
STEP 1 Write down the two numbers side by side on the same row.
STEP 2 Beneath the left-hand number write down double that number. Beneath the right-hand number write down half of that number, ignoring any remainder. STEP 3 Repeat STEP 2 until the right-hand number is 1.
STEP 4 Delete those rows where the right-hand number is even. Add up the remaining left-hand numbers. This is the result.

1. Apply the algorithm to the left-hand number 3 and the right-hand number 8.
2. Apply the algorithm to the left-hand number 26 and the right-hand number 42.
3. Use your results from parts (i) and (ii), together with any other examples you may choose, to write down what the algorithm achieves.

3 Traffic flows in and out of a junction of three roads as shown in the diagram.
\includegraphics[max width=\textwidth, alt={}, center]{839adc96-1bea-44ef-917e-f03e396a3061-3_296_337_333_863} Assuming that no traffic leaves the junction by the same road as it entered, then the digraph shows traffic flows across the junction.
\includegraphics[max width=\textwidth, alt={}, center]{839adc96-1bea-44ef-917e-f03e396a3061-3_362_511_852_776}

1. Redraw the digraph to show that it is planar.
2. Draw a digraph to show the traffic flow across the junction of 4 roads, assuming that no traffic leaves the junction by the same road as it entered.
   \includegraphics[max width=\textwidth, alt={}, center]{839adc96-1bea-44ef-917e-f03e396a3061-3_366_366_1512_854}
   (Note that the resulting digraph is also planar, but you are not required to show this.)
3. The digraphs showing flows across the junctions omit an important aspect in their modelling of the road junctions. What is it that they omit?

4 A wall 4 metres long and 3 metres high is to be tiled. Two sizes of tile are available, 10 cm by 10 cm and 30 cm by 30 cm .

1. If \(x\) is the number of boxes of ten small tiles used, and \(y\) is the number of large tiles used, explain why \(10 x + 9 y \geqslant 1200\). There are only 100 of the large tiles available.
   The tiler advises that the area tiled with the small tiles should not exceed the area tiled with the large tiles.
2. Express these two constraints in terms of \(x\) and \(y\). The smaller tiles cost 15 p each and the larger tiles cost \(\pounds 2\) each.
3. Given that the objective is to minimise the cost of tiling the wall, state the objective function. Use the graphical approach to solve the problem.
4. Give two other factors which would have to be taken into account in deciding how many of each tile to purchase.

5 The diagram shows the progress of a drunkard towards his home on one particular night. For every step which he takes towards his home, he staggers one step diagonally to his left or one step diagonally to his right, randomly and with equal probability. There is a canal three steps to the right of his starting point, and no constraint to the left. On this particular occasion he falls into the canal after 5 steps.
\includegraphics[max width=\textwidth, alt={}, center]{839adc96-1bea-44ef-917e-f03e396a3061-5_723_622_488_724}

1. Explain how you would simulate the drunkard's walk, making efficient use of one-digit random numbers.
2. Using the random digits in the Printed Answer Book simulate the drunkard's walk and show his progress on the grid. Stop your simulation either when he falls into the canal or when he has staggered 6 steps, whichever happens first.
3. How could you estimate the probability of him falling into the canal within 6 steps? On another occasion the drunkard sets off carrying a briefcase in his right hand. This changes the probabilities of him staggering to the right to \(\frac { 2 } { 3 }\), and to the left to \(\frac { 1 } { 3 }\).
4. Explain how you would now simulate this situation.
5. Simulate the drunkard's walk (with briefcase) 10 times, and hence estimate the probability of him falling into the canal within 6 steps. (In your simulations you are not required to show his progress on a grid. You only need to record his steps to the right or left.)

6 The table shows the tasks that have to be completed in building a stadium for a sporting event, their durations and their precedences. The stadium has to be ready within two years.

1. Draw an activity on arc network for these activities.
2. Mark on your diagram the early time and the late time for each event. Give the project duration and the critical activities. In the later stages of planning the project it is discovered that task J will actually take 9 months to complete. However, other tasks can have their durations shortened by employing extra resources. The costs of "crashing" tasks (i.e. the costs of employing extra resources to complete them more quickly) are given in the table.

   Tasks which can be completed more quickly by employing extra resources	Number of months which can be saved	Cost per month of employing extra resources (£m)
   A	2	3
   D	1	1
   C	3	3
   F	2	2
   G	2	4

3. Find the cheapest way of completing the project within two years.
4. If the delay in completing task J is not discovered until it is started, how can the project be completed in time, and how much extra will it cost?