Questions - OCR MEI D1 - A-Level Maths

OCR MEI D1 2016 June Q1

1 Pierre knows that, if he gambles, he will lose money in the long run. Nicolas tries to convince him that this is not the case. Pierre stakes a sum of money in a casino game. If he wins then he gets back his stake plus the same amount again. If he loses then he loses his stake. Nicolas says that Pierre can guarantee to win by repeatedly playing the game, even though the probability of winning an individual game is less than 0.5 . His idea is that Pierre should bet in the first game with a stake of $\pounds 100$. If he wins then he stops, as he will have won $\pounds 100$. If he loses then he plays again with a stake of $\pounds 200$. If he wins then he has lost $\pounds 100$ and won $\pounds 200$. This gives a total gain of $\pounds 100$, and he stops. If he loses then he plays again with a stake of $\pounds 400$. If he wins this time he has lost $\pounds 100$ and $\pounds 200$ and won $\pounds 400$. This gives a total gain of $\pounds 100$, and he stops. Nicolas's advice is that Pierre simply has to continue in this way, doubling his stake every time that he loses, until he eventually wins. Nicolas says that this guarantees that Pierre will win $\pounds 100$. You are to simulate what might happen if Pierre tries this strategy in a casino game in which the probability of him winning an individual game is 0.4 , and in which he has $\pounds 1000$ available.

Give an efficient rule for using 1-digit random numbers to simulate the outcomes of individual games, given that the probability of Pierre winning an individual game is 0.4 .
Explain why at most three random digits are needed for one simulation of Nicolas's strategy, given that Pierre is starting with $\pounds 1000$.
Simulate five applications of Nicolas's strategy, using the five sets of three 1-digit random numbers in your answer book.
Summarise the results of your simulations, giving your mean result.

OCR MEI D1 2016 June Q2

2 A bag contains 26 cards. A different letter of the alphabet is written on each one. A card is chosen at random and its letter is written down. The card is returned to the bag. The bag is shaken and the process is repeated several times. Tania wants to investigate the probability of a letter appearing twice. She wants to know how many cards need to be chosen for this probability to exceed 0.5. Tania uses the following algorithm. Step 1 Set $n = 1$
Step 2 Set $p = 1$
Step 3 Set $n = n + 1$
Step 4 Set $p = p \times \left( \frac { 27 - n } { 26 } \right)$
Step 5 If $p < 0.5$ then stop
Step 6 Go to Step 3

Run the algorithm.
Interpret your results. A well-known problem asks how many randomly-chosen people need to be assembled in a room before the probability of at least two of them sharing a birthday exceeds 0.5 (ignoring anyone born on 29 February).
Modify Tania's algorithm to answer the birthday problem. (Do not attempt to run your modified algorithm.)
Why have 29 February birthdays been excluded?

OCR MEI D1 2016 June Q3

3 The adjacency graph of a cube
\includegraphics[max width=\textwidth, alt={}, center]{e88abde1-8769-4a3c-b115-031cea08d9a6-4_106_108_214_735}
is shown. Vertices on the graph represent faces of the cube. Two vertices are connected by an arc if the corresponding faces of the cube share an edge.
\includegraphics[max width=\textwidth, alt={}, center]{e88abde1-8769-4a3c-b115-031cea08d9a6-4_401_464_246_1334} The second graph is the complement of the adjacency graph, i.e. the graph that consists of the same vertices together with the arcs that are not in the adjacency graph.
\includegraphics[max width=\textwidth, alt={}, center]{e88abde1-8769-4a3c-b115-031cea08d9a6-4_403_464_737_1334} Throughout this question we wish to colour solids so that two faces that share an edge have different colours. The second graph shows that the minimum number of colours required for a cube is three, one colour for the top and base, one for the front and back, and one for the left and right.

Draw the adjacency graph for a square-based pyramid, and draw its complement. Hence find the minimum number of colours needed to colour a square-based pyramid.
\includegraphics[max width=\textwidth, alt={}, center]{e88abde1-8769-4a3c-b115-031cea08d9a6-4_161_202_1434_1548}
(A) Draw the adjacency graph for an octahedron, and draw its complement.
(B) An octahedron can be coloured using just two colours. Explain how this relates to the complement of the adjacency graph.
\includegraphics[max width=\textwidth, alt={}, center]{e88abde1-8769-4a3c-b115-031cea08d9a6-4_227_205_1731_1548}

OCR MEI D1 2016 June Q4

4 Two products are to be made from material that is supplied in a single roll, 20 m long and 1 m wide. The two products require widths of 47 cm and 32 cm respectively. Two ways of cutting lengths of material are shown in the plans below.
\includegraphics[max width=\textwidth, alt={}, center]{e88abde1-8769-4a3c-b115-031cea08d9a6-5_408_1538_520_269}
\includegraphics[max width=\textwidth, alt={}, center]{e88abde1-8769-4a3c-b115-031cea08d9a6-5_403_1533_952_274}

Given that there should be no unnecessary waste, draw one other cutting plan that might be used for a cut of length $z$ metres.
Write down an expression for the total area that is wasted in terms of $x , y$ and $z$. All of the roll is to be cut, so $x + y + z = 20$.
There needs to be a total length of at least 20 metres of the material for the first product, the one requiring width 47 cm .
Write this as a linear constraint on the variables. There needs to be a total length of at least 24 metres of the material for the second product, the one requiring width 32 cm .
Write this as a linear constraint on the variables.
Formulate an LP in terms of $x$ and $y$ to minimise the area that is wasted. You will need to use the relationship $x + y + z = 20$, together with your answers to parts (ii), (iii) and (iv).
Solve your LP graphically, and interpret the solution.

OCR MEI D1 2016 June Q5

5 A village amateur dramatic society is planning its annual pantomime. Three rooms in the village hall have been booked for one evening per week for 12 weeks. The following activities must take place. Their durations are shown.

Activity		Duration (weeks)
A	choose lead actors	1
B	choose rest of actors	1
C	choose dancers	1
D	rehearse lead actors	8
E	rehearse rest of actors	6
F	rehearse dancers	6
G	prepare scenery	6
H	install scenery	1
I	prepare music	2
J	make costumes	4
K	dress rehearsals	2

Each activity needs a room except for activities G, I and J.
Choosing actors and dancers can be done in the same week. Rehearsals can begin after this. Rehearsing the dancers cannot begin until the music has been prepared. The scenery must be installed after rehearsals, but before dress rehearsals.
Making the costumes cannot start until after the actors and dancers have been chosen. Everything must be ready for the dress rehearsals in the final two weeks of the 12-week preparation period.

Complete the table in your answer book by showing the immediate predecessors for each activity.
Draw an activity on arc network for these activities.
Mark on your network the early time and the late time for each event. Give the critical activities. It is discovered that there is a double booking and that one of the rooms will not be available after week 6.
Using the space provided, produce a schedule showing how the pantomime can be ready in time for its first performance.

OCR MEI D1 2016 June Q6

6 A mountain ridge separates two populated areas. Networks representing roads connecting the villages in each area are shown below. The numbers on the arcs represent distances in kilometres.
\includegraphics[max width=\textwidth, alt={}, center]{e88abde1-8769-4a3c-b115-031cea08d9a6-7_524_1429_340_319} There is also a mountain road of length 15 kilometres connecting C to Z .

A national bus company needs a route from A to X .
1. Use Dijkstra's algorithm on the complete network, including CZ, to find the shortest route from A to X . Give the route and its corresponding distance.
2. Would it need fewer computations to use Dijkstra's algorithm on the network for villages A to F to find the shortest route from A to C, and then use Dijkstra's algorithm on the network for villages U to Z to find the shortest route from Z to X? Give a brief justification for your answer.
The local council needs to discover which roads it should keep clear of snow during the winter to keep all the villages connected, and the corresponding total length of road.
1. Use Kruskal's algorithm on the network for villages A to F to find a minimum connector for $\{ \mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { D } , \mathrm { E } , \mathrm { F } \}$. Show your use of the algorithm. Draw your minimum connector.
2. Use Prim's algorithm on the network for villages U to Z to find a minimum connector for $\{ \mathrm { U } , \mathrm { V } , \mathrm { W } , \mathrm { X } , \mathrm { Y } , \mathrm { Z } \}$, starting at U . Show your use of the algorithm. Draw your minimum connector.
3. What is the total length of road that the council must keep clear of snow?

OCR MEI D1 2006 January Q2

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}$$
What does the algorithm achieve?
How many comparisons did you make in applying the algorithm?
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?

OCR MEI D1 Q2

2 Answer this question on the insert provided.

Use Dijkstra's algorithm to find the least weight route from A to G in the network shown in Fig. 2.1. Show the order in which you label vertices, give the route and its weight. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{5d8d35b7-e4ba-4bc0-93a1-0cae58093a02-003_458_586_525_758} \captionsetup{labelformat=empty} \caption{Fig. 2.1}
\end{figure}
Fig. 2.2 shows a partially completed application of Kruskal's algorithm to find a minimum spanning tree for the network. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{5d8d35b7-e4ba-4bc0-93a1-0cae58093a02-003_417_524_1309_786} \captionsetup{labelformat=empty} \caption{Fig. 2.2}
\end{figure} Complete the algorithm and give the total weight of your minimum spanning tree.

OCR MEI D1 2005 January Q2

2 Answer this question on the insert provided.

Use Dijkstra's algorithm to find the least weight route from $A$ to $G$ in the network shown in Fig. 2.1. Show the order in which you label vertices, give the route and its weight. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{b9ee9306-18ca-42b3-9f2e-b23849374b5e-3_458_584_525_760} \captionsetup{labelformat=empty} \caption{Fig. 2.1}
\end{figure}
Fig. 2.2 shows a partially completed application of Kruskal's algorithm to find a minimum spanning tree for the network. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{b9ee9306-18ca-42b3-9f2e-b23849374b5e-3_421_533_1307_779} \captionsetup{labelformat=empty} \caption{Fig. 2.2}
\end{figure} Complete the algorithm and give the total weight of your minimum spanning tree.

OCR MEI D1 2005 January Q4

4 Answer this question on the insert provided. The table shows activities involved in a "perm" in a hair salon, their durations and immediate predecessors. \begin{table}[h]

	Activity	Duration (mins)	Immediate predecessor(s)
A	shampoo	5	-
B	prepare perm lotion	2	-
C	make coffee for customer	3	-
D	trim	5	A
E	clean sink	3	A
F	put rollers in	15	D
G	clean implements	3	D
H	apply perm lotion	5	B, F
I	leave to set	20	C,H
J	clean lotion pot and spreaders	3	H
K	neutralise and rinse	10	I, E
L	dry	10	K
M	wash up and clean up	15	K
N	style	4	G, L

\captionsetup{labelformat=empty} \caption{Table 4}

\end{table}

Complete the activity-on-arc network in the insert to represent the precedences.
Perform a forward pass and a backward pass to find early and late event times. Give the critical activities and the time needed to complete the perm.
Give the total float time for the activity $G$. Activities $\mathrm { D } , \mathrm { F } , \mathrm { H } , \mathrm { K }$ and N require a stylist.
Activities $\mathrm { A } , \mathrm { B } , \mathrm { C } , \mathrm { E } , \mathrm { G } , \mathrm { J }$ and M are done by a trainee.
Activities $I$ and $L$ require no-one in attendance.
A stylist and a trainee are to give a perm to a customer.
Use the chart in the insert to show a schedule for the activities, assuming that all activities are started as early as possible.
Which activity would be better started at its latest start time?

OCR MEI D1 2005 June Q1

1 Answer this question on the insert provided. The nodes in the unfinished graph in Fig. 1 represent six components, A, B, C, D, E, F and the mains. The components are to be joined by electrical cables to the mains. Each component can be joined directly to the mains, or can be joined via other components. \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{03df7d9e-63d4-48fb-9cf3-e92003f44788-2_486_879_623_607} \captionsetup{labelformat=empty} \caption{Fig. 1}

\end{figure} The total number of connections that the electrician has to make is the sum of the orders of the nodes in the finished graph.

Draw arcs representing suitable cables so that the electrician has to make as few connections as possible. Give this number. The electrician has a junction box. This can be represented by an eighth node on the graph.
What is the minimum number of connections which the electrician will have to make if he uses the junction box?
The electrician has to make more connections if he uses his junction box. Why might he choose to use it anyway? The electrician decides not to use the junction box. He measures each of the distances between pairs of nodes, and records them in a complete graph. He then constructs a minimum connector for his graph to find which nodes to connect.
Will this result in the minimum number of connections? Justify your answer.

OCR MEI D1 2005 June Q2

2 Answer this question on the insert provided. A maze is constructed by building east/west and north/south walls so that there is a route from the entrance to the exit. The maze is shown in Fig. 2.1. \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{03df7d9e-63d4-48fb-9cf3-e92003f44788-3_495_717_470_671} \captionsetup{labelformat=empty} \caption{Fig. 2.1}

\end{figure} On entering the maze Janet says "I'm always going to keep a hand in contact with the wall on the right." John says "I'm always going to keep a hand in contact with the wall on the left."

On the insert for this question show Janet's route through the maze. On the insert show John's route.
Will these strategies always find a way through such mazes? Justify your answer. In some mazes the objective is to get to a marked point before exiting. An example is shown in Fig. 2.2, where $\mathbf { X }$ is the marked point. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{03df7d9e-63d4-48fb-9cf3-e92003f44788-3_497_716_1672_669} \captionsetup{labelformat=empty} \caption{Fig. 2.2}
\end{figure} In the maze shown in Fig. 2.2 Janet's algorithm takes her to $\mathbf { X }$. John's algorithm does not take him to $\mathbf { X }$. John modifies his algorithm by saying that he will turn his back on the exit if he arrives there without visiting $\mathbf { X }$. He will then move onwards, continuing to keep a hand in contact with the wall on the left.
Will this modified algorithm take John to the point $\mathbf { X }$ in the maze in Fig. 2.2?
Will this modified algorithm take John to any marked point in the maze in Fig. 2.2? Justify your answer.

OCR MEI D1 2005 June Q4

8 marks

4 Answer parts (i) and (ii) on the insert provided. Fig. 4 shows a network of roads giving direct connections between a city, C , and 7 towns labelled P to V. The weights on the arcs are distances in kilometres. The local coastline is also shown. \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{03df7d9e-63d4-48fb-9cf3-e92003f44788-5_536_828_573_642} \captionsetup{labelformat=empty} \caption{Fig. 4}

\end{figure}

Use Dijkstra's algorithm on the insert to find the shortest distances from each of the towns to the city, C. List those distances and give the shortest route from P to C and from V to C. [8]
Use Kruskal's algorithm to find a minimum connector for the network. List the order in which you include arcs and give the length of your connector. A bridge is built giving a direct road between P and Q of length 12 km .
What effect does the bridge have on the shortest distances from the towns to the city? (You do not need to use an algorithm to answer this part of the question.)
What effect does the bridge have on the minimum connector for the network? (You do not need to use an algorithm to answer this part of the question.)
Before the bridge was built it was possible to travel from P to C using every road once and only once. With the bridge in place, it is possible to travel from a different town to C using every road once and only once. Give this town and justify your answer.

OCR MEI D1 2006 June Q1

2 marks

1 Answer this question on the insert provided. \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{c429bfed-9241-409a-9cd5-9553bf16c9df-2_658_739_466_662} \captionsetup{labelformat=empty} \caption{Fig. 1}

\end{figure}

Apply Dijkstra's algorithm to the copy of Fig. 1 in the insert to find the least weight route from A to D. Give your route and its weight.
Arc DE is now deleted. Write down the weight of the new least weight route from A to D , and explain how your working in part (i) shows that it is the least weight.
[0pt] [2]

OCR MEI D1 2006 June Q6

6 Answer parts (ii)(A) and (iii)(B) of this question on the insert provided. A particular component of a machine sometimes fails. The probability of failure depends on the age of the component, as shown in Table 6.

Year of life

first

second

third

fourth

fifth

sixth

Probability of failure during year,

given no earlier failure

0.10

0.05

0.02

0.20

0.30

\section*{Table 6} You are to simulate six years of machine operation to estimate the probability of the component failing during that time. This will involve you using six 2-digit random numbers, one for each year.

Give a rule for using a 2-digit random number to simulate failure of the component in its first year of life. Similarly give rules for simulating failure during each of years 2 to 6 .
(A) Use your rules, together with the random numbers given in the insert, to complete the simulation table in the insert. This simulates 10 repetitions of six years operation of the machine. Start in the first column working down cell-by-cell. In each cell enter a tick if there is no simulated failure and a cross if there is a simulated failure. Stop and move on to the next column if a failure occurs.
(B) Use your results to estimate the probability of a failure occurring. It is suggested that any component that has not failed during the first three years of its life should automatically be replaced.
(A) Describe how to simulate the operation of this policy.
(B) Use the table in the insert to simulate 10 repetitions of the application of this policy. Re-use the same random numbers that are given in the insert.
(C) Use your results to estimate the probability of a failure occurring.
How might the reliability of your estimates in parts (ii) and (iii) be improved?

OCR MEI D1 2006 January Q5

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]

	A	B	C	D	E	F	G
A	-	10	-	-	-	12	15
B	10	-	15	20	-	-	8
C	-	15	-	7	-	-	11
D	-	20	7	-	20	-	13
E	-	-	-	20	-	17	9
F	12	-	-	-	17	-	13
G	15	8	11	13	9	13	-

\captionsetup{labelformat=empty} \caption{Table 5}

\end{table}

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.
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.
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)?

OCR MEI D1 2006 January Q6

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.

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}
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}
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.
Complete the table using the random numbers which are provided.
Calculate the mean total time spent queuing and paying.

OCR MEI D1 2007 January Q1

1 Each of the following symbols consists of boundaries enclosing regions.
(0) 1

OCR MEI D1 2007 January Q3

3
$\triangle$
5
(5) 7
(8)
(O) The symbol representing zero has three regions, the outside, that between the two boundaries and the inside. To classify the symbols a graph is produced for each one. The graph has a vertex for each region, with arcs connecting regions which share a boundary. Thus the graph for
\includegraphics[max width=\textwidth, alt={}, center]{a56f79f4-3b71-4ae3-a88b-5a88b0197433-2_110_81_900_767}
is
\includegraphics[max width=\textwidth, alt={}, center]{a56f79f4-3b71-4ae3-a88b-5a88b0197433-2_49_350_959_959}

Produce the graph for the symbol
Give two symbols each having the graph
\includegraphics[max width=\textwidth, alt={}, center]{a56f79f4-3b71-4ae3-a88b-5a88b0197433-2_52_199_1187_1030}
Produce the graph for the symbol .
Produce a single graph for the composite symbol
\includegraphics[max width=\textwidth, alt={}, center]{a56f79f4-3b71-4ae3-a88b-5a88b0197433-2_112_158_1398_1165}
Give the name of a connected graph with $n$ nodes and $n - 1 \operatorname { arcs }$. 2 The following algorithm is a version of bubble sort.
Step 1 Store the values to be sorted in locations $\mathrm { L } ( 1 ) , \mathrm { L } ( 2 ) , \ldots , \mathrm { L } ( \mathrm { n } )$ and set i to be the number, n , of values to be sorted. Step $2 \quad$ Set $\mathrm { j } = 1$.
Step 3 Compare the values in locations $\mathrm { L } ( \mathrm { j } )$ and $\mathrm { L } ( \mathrm { j } + 1 )$ and swap them if that $\mathrm { in } \mathrm { L } ( \mathrm { j } )$ is larger than that in $\mathrm { L } ( \mathrm { j } + 1 )$. Step 4 Add 1 to j.
Step 5 If j is less than i then go to step 3.
Step 5 Write out the current list, $\mathrm { L } ( 1 ) , \mathrm { L } ( 2 ) , \ldots , \mathrm { L } ( \mathrm { n } )$.
Step 6 Subtract 1 from i .
Step 7 If i is larger than 1 then go to step 2.
Step 8 Stop.
Apply this algorithm to sort the following list. $$\begin{array} { l l l l l } 109 & 32 & 3 & 523 & 58 \end{array} .$$ Count the number of comparisons and the number of swaps which you make in applying the algorithm.
Put the five values into the order which maximises the number of swaps made in applying the algorithm, and give that number.
Bubble sort has quadratic complexity. Using bubble sort it takes a computer 1.5 seconds to sort a list of 1000 values. Approximately how long would it take to sort a list of 100000 values? (Give your answer in hours and minutes.) 3 A bag contains five pieces of paper labelled A, B, C, D and E. One piece is drawn at random from the bag. If the piece is labelled with a vowel (A or E) then the process stops. Otherwise the piece of paper is replaced, the bag is shaken, and the process is repeated. You are to simulate this process to estimate the mean number of draws needed to get a vowel.
Show how to use single digit random numbers to simulate the process efficiently. You need to describe exactly how your simulation will work.
Use the random numbers in your answer book to run your simulation 5 times, recording your results.
From your results compute an estimate of the mean number of draws needed to get a vowel.
State how you could produce a more accurate estimate. Section B (48 marks)

OCR MEI D1 2007 January Q5

5
(5) 7
(8)
(O) The symbol representing zero has three regions, the outside, that between the two boundaries and the inside. To classify the symbols a graph is produced for each one. The graph has a vertex for each region, with arcs connecting regions which share a boundary. Thus the graph for
\includegraphics[max width=\textwidth, alt={}, center]{a56f79f4-3b71-4ae3-a88b-5a88b0197433-2_110_81_900_767}
is
\includegraphics[max width=\textwidth, alt={}, center]{a56f79f4-3b71-4ae3-a88b-5a88b0197433-2_49_350_959_959}

Produce the graph for the symbol
Give two symbols each having the graph
\includegraphics[max width=\textwidth, alt={}, center]{a56f79f4-3b71-4ae3-a88b-5a88b0197433-2_52_199_1187_1030}
Produce the graph for the symbol .
Produce a single graph for the composite symbol
\includegraphics[max width=\textwidth, alt={}, center]{a56f79f4-3b71-4ae3-a88b-5a88b0197433-2_112_158_1398_1165}
Give the name of a connected graph with $n$ nodes and $n - 1 \operatorname { arcs }$. 2 The following algorithm is a version of bubble sort.
Step 1 Store the values to be sorted in locations $\mathrm { L } ( 1 ) , \mathrm { L } ( 2 ) , \ldots , \mathrm { L } ( \mathrm { n } )$ and set i to be the number, n , of values to be sorted. Step $2 \quad$ Set $\mathrm { j } = 1$.
Step 3 Compare the values in locations $\mathrm { L } ( \mathrm { j } )$ and $\mathrm { L } ( \mathrm { j } + 1 )$ and swap them if that $\mathrm { in } \mathrm { L } ( \mathrm { j } )$ is larger than that in $\mathrm { L } ( \mathrm { j } + 1 )$. Step 4 Add 1 to j.
Step 5 If j is less than i then go to step 3.
Step 5 Write out the current list, $\mathrm { L } ( 1 ) , \mathrm { L } ( 2 ) , \ldots , \mathrm { L } ( \mathrm { n } )$.
Step 6 Subtract 1 from i .
Step 7 If i is larger than 1 then go to step 2.
Step 8 Stop.
Apply this algorithm to sort the following list. $$\begin{array} { l l l l l } 109 & 32 & 3 & 523 & 58 \end{array} .$$ Count the number of comparisons and the number of swaps which you make in applying the algorithm.
Put the five values into the order which maximises the number of swaps made in applying the algorithm, and give that number.
Bubble sort has quadratic complexity. Using bubble sort it takes a computer 1.5 seconds to sort a list of 1000 values. Approximately how long would it take to sort a list of 100000 values? (Give your answer in hours and minutes.) 3 A bag contains five pieces of paper labelled A, B, C, D and E. One piece is drawn at random from the bag. If the piece is labelled with a vowel (A or E) then the process stops. Otherwise the piece of paper is replaced, the bag is shaken, and the process is repeated. You are to simulate this process to estimate the mean number of draws needed to get a vowel.
Show how to use single digit random numbers to simulate the process efficiently. You need to describe exactly how your simulation will work.
Use the random numbers in your answer book to run your simulation 5 times, recording your results.
From your results compute an estimate of the mean number of draws needed to get a vowel.

State how you could produce a more accurate estimate. Section B (48 marks)
4 Cassi is managing the building of a house. The table shows the major activities that are involved, their durations and their precedences.

Activity		Duration (days)	Immediate predecessors
A	Build concrete frame	10	-
B	Lay bricks	7	A
C	Lay roof tiles	10	A
D	First fit electrics	5	B
E	First fit plumbing	4	B
F	Plastering	6	C, D, E
G	Second fit electrics	3	F
H	Second fit plumbing	2	F
I	Tiling	10	G, H
J	Fit sanitary ware	2	H
K	Fit windows and doors	5	I

Draw an activity-on-arc network to represent this information.
Find the early time and the late time for each event. Give the project duration and list the critical activities.
Calculate total and independent floats for each non-critical activity. Cassi's clients wish to take delivery in 42 days. Some durations can be reduced, at extra cost, to achieve this.
- The tiler will finish activity I in 9 days for an extra $\pounds 250$, or in 8 days for an extra $\pounds 500$.
- The bricklayer will cut his total of 7 days on activity B by up to 3 days at an extra cost of $\pounds 350$ per day.
- The electrician could be paid $\pounds 300$ more to cut a day off activity D, or $\pounds 600$ more to cut two days.
- What is the cheapest way in which Cassi can get the house built in 42 days?
5 Leone is designing her new garden. She wants to have at least $1000 \mathrm {~m} ^ { 2 }$, split between lawn and flower beds. Initial costs are $\pounds 0.80$ per $\mathrm { m } ^ { 2 }$ for lawn and $\pounds 0.40$ per $\mathrm { m } ^ { 2 }$ for flowerbeds. Leone's budget is $\pounds 500$.
Leone prefers flower beds to lawn, and she wants the area for flower beds to be at least twice the area for lawn. However, she wants to have at least $200 \mathrm {~m} ^ { 2 }$ of lawn. Maintenance costs each year are $\pounds 0.15$ per $\mathrm { m } ^ { 2 }$ for lawn and $\pounds 0.25$ per $\mathrm { m } ^ { 2 }$ for flower beds. Leone wants to minimize the maintenance costs of her garden.
Formulate Leone's problem as a linear programming problem.
Produce a graph to illustrate the inequalities.
Solve Leone's problem.
If Leone had more than $\pounds 500$ available initially, how much extra could she spend to minimize maintenance costs?

OCR MEI D1 2007 January Q7

7
(8)
(O) The symbol representing zero has three regions, the outside, that between the two boundaries and the inside. To classify the symbols a graph is produced for each one. The graph has a vertex for each region, with arcs connecting regions which share a boundary. Thus the graph for
\includegraphics[max width=\textwidth, alt={}, center]{a56f79f4-3b71-4ae3-a88b-5a88b0197433-2_110_81_900_767}
is
\includegraphics[max width=\textwidth, alt={}, center]{a56f79f4-3b71-4ae3-a88b-5a88b0197433-2_49_350_959_959}

Produce the graph for the symbol
Give two symbols each having the graph
\includegraphics[max width=\textwidth, alt={}, center]{a56f79f4-3b71-4ae3-a88b-5a88b0197433-2_52_199_1187_1030}
Produce the graph for the symbol .
Produce a single graph for the composite symbol
\includegraphics[max width=\textwidth, alt={}, center]{a56f79f4-3b71-4ae3-a88b-5a88b0197433-2_112_158_1398_1165}
Give the name of a connected graph with $n$ nodes and $n - 1 \operatorname { arcs }$. 2 The following algorithm is a version of bubble sort.
Step 1 Store the values to be sorted in locations $\mathrm { L } ( 1 ) , \mathrm { L } ( 2 ) , \ldots , \mathrm { L } ( \mathrm { n } )$ and set i to be the number, n , of values to be sorted. Step $2 \quad$ Set $\mathrm { j } = 1$.
Step 3 Compare the values in locations $\mathrm { L } ( \mathrm { j } )$ and $\mathrm { L } ( \mathrm { j } + 1 )$ and swap them if that $\mathrm { in } \mathrm { L } ( \mathrm { j } )$ is larger than that in $\mathrm { L } ( \mathrm { j } + 1 )$. Step 4 Add 1 to j.
Step 5 If j is less than i then go to step 3.
Step 5 Write out the current list, $\mathrm { L } ( 1 ) , \mathrm { L } ( 2 ) , \ldots , \mathrm { L } ( \mathrm { n } )$.
Step 6 Subtract 1 from i .
Step 7 If i is larger than 1 then go to step 2.
Step 8 Stop.
Apply this algorithm to sort the following list. $$\begin{array} { l l l l l } 109 & 32 & 3 & 523 & 58 \end{array} .$$ Count the number of comparisons and the number of swaps which you make in applying the algorithm.
Put the five values into the order which maximises the number of swaps made in applying the algorithm, and give that number.
Bubble sort has quadratic complexity. Using bubble sort it takes a computer 1.5 seconds to sort a list of 1000 values. Approximately how long would it take to sort a list of 100000 values? (Give your answer in hours and minutes.) 3 A bag contains five pieces of paper labelled A, B, C, D and E. One piece is drawn at random from the bag. If the piece is labelled with a vowel (A or E) then the process stops. Otherwise the piece of paper is replaced, the bag is shaken, and the process is repeated. You are to simulate this process to estimate the mean number of draws needed to get a vowel.
Show how to use single digit random numbers to simulate the process efficiently. You need to describe exactly how your simulation will work.
Use the random numbers in your answer book to run your simulation 5 times, recording your results.
From your results compute an estimate of the mean number of draws needed to get a vowel.