OCR MEI D1 (Decision Mathematics 1) 2006 January

1 Table 1 shows a precedence table for a project. \begin{table}[h] \end{table}

1. Draw an activity-on-arc network to represent the precedences.
2. Find the early event time and late event time for each vertex of your network, and list the critical activities.
3. Extra resources become available which enable the durations of three activities to be reduced, each by up to two days. Which three activities should have their durations reduced so as to minimise the completion time of the project? What will be the new minimum project completion time?

1. Complete the table in the insert showing the outcome of applying the algorithm to the following two lists: $$\begin{array} { l r l l l l l } \text { List 1: } & 2 , & 34 , & 35 , & 56 & &
   \text { List 2: } & 13 , & 22 , & 34 , & 81 , & 90 , & 92 \end{array}$$
2. What does the algorithm achieve?
3. How many comparisons did you make in applying the algorithm?
4. If the number of elements in List 1 is \(x\), and the number of elements in List 2 is \(y\), what is the maximum number of comparisons that will have to be made in applying the algorithm, and what is the minimum number?

3 Fig. 3 shows a graph representing the seven bus journeys run each day between four rural towns. Each directed arc represents a single bus journey. \begin{figure}[h] \end{figure}

1. Show that if there is only one bus, which is in service at all times, then it must start at one town and end at a different town. Give the start town and the end town.
2. Show that there is only one Hamilton cycle in the graph. Show that, if an extra journey is added from your end town to your start town, then there is still only one Hamilton cycle.
3. A tourist is staying in town B. Give a route for her to visit every town by bus, visiting each town only once and returning to B . Section B (48 marks)

4 Table 4 shows the butter and sugar content in two recipes. The first recipe is for 1 kg of toffee and the second is for 1 kg of fudge. \begin{table}[h] \section*{Table 6.1} (ii) Specify an efficient rule for using one-digit random numbers to simulate the time taken at the till by customers purchasing fuel. Table 6.2 shows the distribution of time taken at the till by customers who are not buying fuel. \section*{Table 6.2} (iii) Specify an efficient rule for using two-digit random numbers to simulate the time taken at the till by customers not buying fuel. What is the advantage in using two-digit random numbers instead of one-digit random numbers in this part of the question? The table in the insert shows a partially completed simulation study of 10 customers arriving at the till.
(iv) Complete the table using the random numbers which are provided.
(v) Calculate the mean total time spent queuing and paying.

5 Answer this question on the insert provided. Table 5 specifies a road network connecting 7 towns, A, B, \(\ldots\), G. The entries in Table 5 give the distances in miles between towns which are connected directly by roads. \begin{table}[h] \end{table}

1. Using the copy of Table 5 in the insert, apply the tabular form of Prim's algorithm to the network, starting at vertex A. Show the order in which you connect the vertices. Draw the resulting tree, give its total length and describe a practical application.
2. The network in the insert shows the information in Table 5. Apply Dijkstra's algorithm to find the shortest route from A to E. Give your route and its length.
3. A tunnel is built through a hill between A and B , shortening the distance between A and B to 6 miles. How does this affect your answers to parts (i) and (ii)?

6 Answer part (iv) of this question on the insert provided. There are two types of customer who use the shop at a service station. \(70 \%\) buy fuel, the other \(30 \%\) do not. There is only one till in operation.

1. Give an efficient rule for using one-digit random numbers to simulate the type of customer arriving at the service station. Table 6.1 shows the distribution of time taken at the till by customers who are buying fuel.

   Time taken (mins)	1	1.5	2	2.5
   Probability	\(\frac { 3 } { 10 }\)	\(\frac { 2 } { 5 }\)	\(\frac { 1 } { 5 }\)	\(\frac { 1 } { 10 }\)

   \section*{Table 6.1}
2. Specify an efficient rule for using one-digit random numbers to simulate the time taken at the till by customers purchasing fuel. Table 6.2 shows the distribution of time taken at the till by customers who are not buying fuel.

   Time taken (mins)	1	1.5	2	2.5	3
   Probability	\(\frac { 1 } { 7 }\)	\(\frac { 2 } { 7 }\)	\(\frac { 2 } { 7 }\)	\(\frac { 1 } { 7 }\)	\(\frac { 1 } { 7 }\)

   \section*{Table 6.2}
3. Specify an efficient rule for using two-digit random numbers to simulate the time taken at the till by customers not buying fuel. What is the advantage in using two-digit random numbers instead of one-digit random numbers in this part of the question? The table in the insert shows a partially completed simulation study of 10 customers arriving at the till.
4. Complete the table using the random numbers which are provided.
5. Calculate the mean total time spent queuing and paying.