OCR MEI D1 (Decision Mathematics 1) 2008 June

1 Consider the following LP.
Maximise \(x + y\)
subject to \(2 x + y < 44\)
\(2 x + 3 y < 60\)
\(10 x + 11 y < 244\)
Part of a graphical solution is produced below and in your answer book.
Complete this graphical solution in your answer book.
\includegraphics[max width=\textwidth, alt={}, center]{8eba759f-38bc-4d14-ac65-9a0ee6c79741-2_1316_1346_916_356}

2 The following algorithm acts on a list of three or more numbers.
Step 1: Set both X and Y equal to the first number on the list.
Step 2: If there is no next number then go to Step 5.
Step 3: If the next number on the list is bigger than X then set X equal to it. If it is less than Y then set Y equal to it. Step 4: Go to Step 2.
Step 5: Delete a number equal to X from the list and delete a number equal to Y from the list.
Step 6: If there is one number left then record it as the answer and stop.
Step 7: If there are two numbers left then record their mean as the answer and stop.
Step 8: Go to Step 1.

1. Apply the algorithm to the list \(5,14,153,6,24,2,14,15\), counting the number of comparisons which you have to make.
2. Apply the algorithm to the list \(5,14,153,6,24,2,14\), counting the number of comparisons which you have to make.
3. Say what the algorithm is finding.
4. The order of the algorithm is quadratic. Explain what this means when it is applied to long lists.

3 The graph represents four towns together with (two-way) roads connecting them.
\includegraphics[max width=\textwidth, alt={}, center]{8eba759f-38bc-4d14-ac65-9a0ee6c79741-4_191_286_319_886} A path is a set of connected arcs linking one vertex to another. A path contains no repeated vertex. \(\mathrm { T } _ { 1 } \rightarrow \mathrm {~T} _ { 2 }\) and \(\mathrm { T } _ { 1 } \rightarrow \mathrm {~T} _ { 3 } \rightarrow \mathrm {~T} _ { 2 }\) are paths.

1. There are six paths from \(\mathrm { T } _ { 1 }\). List them.
2. List the paths from \(\mathrm { T } _ { 4 }\).
3. How many paths are there altogether? For this question a route is defined to be a path in which the direction of the arcs is not relevant. Thus \(\mathrm { T } _ { 1 } \rightarrow \mathrm {~T} _ { 2 }\) and \(\mathrm { T } _ { 2 } \rightarrow \mathrm {~T} _ { 1 }\) are the same route. Similarly \(\mathrm { T } _ { 1 } \rightarrow \mathrm {~T} _ { 3 } \rightarrow \mathrm {~T} _ { 2 }\) and \(\mathrm { T } _ { 2 } \rightarrow \mathrm {~T} _ { 3 } \rightarrow \mathrm {~T} _ { 1 }\) are the same route (but note that \(\mathrm { T } _ { 1 } \rightarrow \mathrm {~T} _ { 2 } \rightarrow \mathrm {~T} _ { 3 }\) is different).
4. How many routes are there altogether?

4 Joe is to catch a plane to go on holiday. He has arranged to leave his car at a car park near to the airport. There is a bus service from the car park to the airport, and the bus leaves when there are at least 15 passengers on board. Joe is delayed getting to the car park and arrives needing the bus to leave within 15 minutes if he is to catch his plane. He is the \(10 ^ { \text {th } }\) passenger to board the bus, so he has to wait for another 5 passengers to arrive. The distribution of the time intervals between car arrivals and the distribution of the number of passengers per car are given below.

1. Give an efficient rule for using 2-digit random numbers to simulate the intervals between car arrivals.
2. Give an efficient rule for using 2-digit random numbers to simulate the number of passengers in a car.
3. The incomplete table in your answer book shows the results of nine simulations of the situation. Complete the table, showing in each case whether or not Joe catches his plane.
4. Use the random numbers provided in your answer book to run a tenth simulation.
   [0pt]
5. Estimate the probability of Joe catching his plane. State how you could improve your estimate. [2]

5

1. The graphs below illustrate the precedences involved in running two projects, each consisting of the same activities \(\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D }\) and E . \begin{figure}[h]
   \captionsetup{labelformat=empty} \caption{Project 1} \includegraphics[alt={},max width=\textwidth]{8eba759f-38bc-4d14-ac65-9a0ee6c79741-6_280_385_429_495}
   \end{figure} \begin{figure}[h]
   \captionsetup{labelformat=empty} \caption{Project 2} \includegraphics[alt={},max width=\textwidth]{8eba759f-38bc-4d14-ac65-9a0ee6c79741-6_255_392_429_1187}
   \end{figure}
   1. For one activity the precedences in the two projects are different. State which activity and describe the difference.
   2. The table below shows the durations of the five activities.

      Activity	A	B	C	D	E
      Duration	2	1	\(x\)	3	2

      Give the total time for project 1 for all possible values of \(x\).
      Give the total time for project 2 for all possible values of \(x\).
2. The durations and precedences for the activities in a project are shown in the table.

   Activity	Duration	Immediate predecessors
   R	2	-
   S	1	-
   T	5	-
   w	3	R, S
   X	2	R, S, T
   Y	3	R
   Z	1	W, Y

   1. Draw an activity on arc network to represent this information.
   2. Find the early time and the late time for each event. Give the project duration and list the critical activities.

6 The matrix gives the lengths of the arcs of a network.

1. Using the copy of the matrix in your answer book, apply the tabular form of Prim's algorithm to find a minimum connector for the network. Start by choosing vertex A and show the order in which you include vertices.
   List the arcs in your connector and give its total length. Serena takes a different approach to find a minimum connector. She first uses Dijkstra's algorithm to find shortest paths from A to each of the other vertices. She then uses the arcs in those paths to construct a connector.
2. Draw the network using the vertices printed in your answer book.
3. Apply Serena's method to produce a connector. List the arcs in the connector and give its total length. Serena adapts her method by starting from each vertex in turn, producing six connectors, from which she chooses the best.
4. Serena's approach will not find the minimum connector in all networks, but it is an algorithm. What is its algorithmic complexity? Justify your answer.