Questions D1 - A-Level Maths

Draw two graphs to represent the sets $\mathrm { X } , \mathrm { Y }$ and Z shown in the following diagram.
\includegraphics[max width=\textwidth, alt={}, center]{7330fba5-720f-47d5-a2ac-ad24e0cf097b-3_415_613_1388_731}
Draw a diagram to represent the sets $\mathrm { P } , \mathrm { Q }$ and R for which both of the following graphs apply. \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{7330fba5-720f-47d5-a2ac-ad24e0cf097b-3_202_264_1980_621} \captionsetup{labelformat=empty} \caption{'is a subset of'}
\end{figure} \begin{figure}[h]
\includegraphics[alt={},max width=\textwidth]{7330fba5-720f-47d5-a2ac-ad24e0cf097b-3_200_260_1982_1155} \captionsetup{labelformat=empty} \caption{'shares at least one element with'}
\end{figure}

OCR MEI D1 2012 June Q4

4 In a factory, two types of motor are made. Each motor of type X takes 10 man hours to make and each motor of type Y takes 12 man hours to make. In each week there are 200 man hours available. To satisfy customer demand, at least 5 of each type of motor must be made each week.
Once a motor has been started it must be completed; no unfinished motors may be left in the factory at the end of each week. When completed, the motors are put into a container for shipping. The volume of the container is $7 \mathrm {~m} ^ { 3 }$. A type X motor occupies a volume of $0.5 \mathrm {~m} ^ { 3 }$ and a type Y motor occupies a volume of $0.3 \mathrm {~m} ^ { 3 }$.

Define appropriate variables and from the above information derive four inequalities which must be satisfied by those variables.
Represent your inequalities on a graph and shade the infeasible region. The profit on each type X is $\pounds 100$ and on each type Y is $\pounds 70$.
The weekly profit is to be maximised. Write down the objective function and find the maximum profit.
Because of absenteeism, the manager decides to organise the work in the factory on the assumption that there will be only 180 man hours available each week. Find the number of motors of each type that should now be made in order to maximise the profit.

OCR MEI D1 2012 June Q5

5 Each morning I reach into my box of tea bags and, without looking, randomly choose a bag. The bags are manufactured in pairs, which can be separated along a perforated line. So when I choose a bag it might be attached to another, in which case I have to separate them and return the other bag to the box. Alternatively, it might be a single bag, having been separated on an earlier day. I only use one tea bag per day, and the box always gets thoroughly shaken during the day as things are moved around in the kitchen. You are to simulate this process, starting with 5 double bags and 0 single bags in the box. You are to use single-digit random numbers in your simulation.

On day 2 there will be 4 double bags and 1 single bag in the box, 9 bags in total. Give a rule for simulating whether I choose a single bag or a double bag, assuming that I am equally likely to choose any of the 9 bags. Use single-digit random numbers in your simulation rule.
On day 3 there will either be 4 double bags or 3 double bags and 2 single bags in the box. Give a rule for simulating what sort of bag I choose in the second of these cases. Use single-digit random numbers in your simulation rule.
Using the random digits in your answer book, simulate what happens on days 2,3 and 4 , briefly explaining your simulations. Give an estimate of the probability that I choose a single bag on day 5 .
Using the random digits in your answer book, carry out 4 more simulations and record the results.
Using your 5 simulations, estimate the probability that I choose a single bag on day 5 .
[0pt] [Question 6 is printed overleaf.]

OCR MEI D1 2012 June Q6

6 The table shows the tasks involved in making a batch of buns, the time in minutes required for each task, and their precedences.

Task		Time (minutes)	Immediate predecessors
A	measure out flour	0.5	-
B	mix flour and water	1	A
C	shell eggs	0.5	-
D	mix in eggs and fat	2	B, C
E	get currants ready	0.5	-
F	get raisins ready	0.5	-
G	fold fruit into mix	0.5	D, E, F
H	bake	10	G

Draw an activity on arc network for these activities.
Mark on your diagram the early time and the late time for each event. Give the minimum completion time and the critical activities. Preparing the batch for baking consists of tasks A to G ; each of these tasks can only be done by one person. Baking, task H, requires no people.
How many people are required to prepare the batch for baking in the minimum time?
What is the minimum time required to prepare the batch for baking if only one person is available? Jim is preparing and baking three batches of buns. He has one oven available for baking. For the rest of the question you should consider 'preparing the batch for baking' as one activity.
Assuming that the oven can bake only one batch at a time, draw an activity on arc diagram for this situation and give the minimum time in which the three batches of buns can be prepared and baked.
Assuming that the oven is big enough to bake all three batches of buns at the same time, give the minimum time in which the three batches of buns can be prepared and baked.

OCR MEI D1 2014 June Q1

2 marks

1 The diagram shows the layout of a Mediterranean garden. Thick lines represent paths.
\includegraphics[max width=\textwidth, alt={}, center]{aac29742-fee8-48a9-896c-e96696742251-2_961_1093_440_468}

Draw a graph to represent this information using the vertices listed below, and with arcs representing the 18 paths. Vertices: patio (pa); pool (po); top steps (ts); orange tree (or); fig tree (fi); pool door (pd); back door (bd); front door (fd); front steps (fs); gate (gat); olive tree (ol); garage (gar). [2] Joanna, the householder, wants to walk along all of the paths.
Explain why she cannot do this without repeating at least one path.
Write down a route for Joanna to walk along all of the paths, repeating exactly one path. Write down the path which must be repeated. Joanna has a new path constructed which links the pool directly to the top steps.
Describe how this affects Joanna's walk, and where she can start and finish. (You are not required to give a new route.)

OCR MEI D1 2014 June Q2

2 Honor either has coffee or tea at breakfast. On one third of days she chooses coffee, otherwise she has tea. She can never remember what she had the day before.

Construct a simulation rule, using one-digit random numbers, to model Honor's choices of breakfast drink.
Using the one-digit random numbers in your answer book, simulate Honor's choice of breakfast drink for 10 days. Honor also has either coffee or tea at the end of her evening meal, but she does remember what she had for breakfast, and her choice depends on it. If she had coffee at breakfast then the probability of her having coffee again is 0.55 . If she had tea for breakfast, then the probability of her having tea again is 0.15 .
Construct a simulation rule, using two-digit random numbers, to model Honor's choice of evening drink given that she had coffee at breakfast. Construct a simulation rule, using two-digit random numbers, to model Honor's choice of evening drink given that she had tea at breakfast.
Using your breakfast simulation from part (ii), and the two-digit random numbers in your answer book, simulate Honor's choice of evening drink for 10 days.
Use your results from parts (ii) and (iv) to estimate the proportion of Honor's drinks, breakfast and evening meal combined, which are coffee. \section*{Question 3 begins on page 4}

OCR MEI D1 2014 June Q3

3 Six remote villages are linked by a set of roads. Two villages are connected directly if there is a road between them which does not pass through another village. The table gives the lengths in miles of all direct connections.

	A	B	C	D	E	F
A		6	7	12		3
B	6		10		8
C	7	10		2
D	12		2		9	8
E		8		9
F	3			8

Why might it be thought surprising that the direct distance between A and D is as long as 12 miles? Give a possible reason why the distance is longer than might have been expected.
Use the tabular form of Prim's algorithm, starting at A , to find a minimum connector for these villages. Draw your connector and give its total length.

OCR MEI D1 2014 June Q4

4 The table lists tasks which are involved in adding a back door to a garage. The table also lists the duration and immediate predecessor(s) for each task. Each task is undertaken by one person.

Task		Duration (hours)	Immediate predecessor(s)
A	measure	0.5	-
B	manufacture frame and door	5	A
C	cut hole in wall	2	A
D	fit lintel and marble step	1.5	C
E	fit frame	1	B, C
F	fit door	1	E
G	repair plaster around door	1	E

Draw an activity on arc network for these activities.
Mark on your diagram the early time and the late time for each event. Give the minimum completion time and the critical activities.
Produce a schedule to show how two people can complete the project in the minimum time. Soon after starting activity D , the marble step breaks. Getting a replacement step adds 4 hours to the duration of activity D.
How does this delay affect the minimum completion time, the critical activities and the minimum time needed for two people to complete the project? \section*{Question 5 begins on page 6}

OCR MEI D1 2014 June Q5

The following instructions operate on positive integers greater than 4.
Step 10 Choose any positive integer greater than 4, and call it $n$.
Step 15 Write down $n$.
Step 20 If $n$ is even then let $n = \frac { n } { 2 }$ and write down the result.
Step 30 If $n$ is odd then let $n = 3 n + 1$ and write down the result.
Step 40 Go to Step 20.
1. Apply the instructions with 6 as the chosen integer, stopping when a sequence repeats itself.
2. Apply the instructions with 256 as the chosen integer, stopping when a sequence repeats itself.
3. Add an instruction to stop the process when $n$ becomes 1 .
4. It is not known if, when modified to stop cycling through $4,2,1$, the instructions form an algorithm. What would need to be known for it to be an algorithm?
Six items with weights given in the table are to be packed into boxes each of which has a capacity of 10 kg .
Item A B C D E F
Weight $( \mathrm { kg } )$ 2 1 6 3 3 5
The first-fit algorithm is as follows.
\includegraphics[max width=\textwidth, alt={}, center]{aac29742-fee8-48a9-896c-e96696742251-7_809_1280_660_356}
1. Use the first-fit algorithm to pack the items in the order given, and state how many boxes are needed.
2. Place the items in increasing order of weight, and then apply the first-fit algorithm.
3. Place the items in decreasing order of weight, and then apply the first-fit algorithm. An optimal solution is one which uses the least number of boxes.
4. Find a set of weights for which placing in decreasing order of weight, and then applying the firstfit algorithm, does not give an optimal solution. Show both the results of first-fit decreasing and an optimal solution.
5. First-fit decreasing has quadratic complexity. If it takes a person 30 seconds to apply first-fit decreasing to 6 items, about how long would it take that person to apply it to 60 items?

OCR MEI D1 2014 June Q6

6 Ian the chef is to make vegetable stew and vegetable soup for distribution to a small chain of vegetarian restaurants. The recipes for both of these require carrots, beans and tomatoes. 10 litres of stew requires 1.5 kg of carrots, 1 kg of beans and 1.5 kg of tomatoes.
10 litres of soup requires 1 kg of carrots, 0.75 kg of beans and 1.5 kg of tomatoes. Ian has available 100 kg of carrots, 70 kg of beans and 110 kg of tomatoes.

Identify appropriate variables and write down three inequalities corresponding to the availabilities of carrots, beans and tomatoes.
Graph your inequalities and identify the region corresponding to feasible production plans. The profit on a litre of stew is $\pounds 5$, and the profit on a litre of soup is $\pounds 4$.
Find the most profitable production plan, showing your working. Give the maximum profit. Ian can buy in extra tomatoes at $\pounds 2.50$ per kg .
What extra quantity of tomatoes should Ian buy? How much extra profit would be generated by the extra expenditure? \section*{END OF QUESTION PAPER} \section*{OCR}

OCR MEI D1 2015 June Q1

1 The directed bipartite graph represents links between chairlifts and ski runs in one part of a ski resort. Chairlifts are represented by capital letters, and ski runs are represented by numbers. For example, chairlift A takes skiers to the tops of ski runs 1 and 2, whereas ski run 2 takes skiers to the bottom of chairlift B .
\includegraphics[max width=\textwidth, alt={}, center]{a27c868b-4fc4-4e82-b27f-d367b15b42c2-2_551_333_493_849}

The incomplete map in your answer book represents the three chairlifts and ski run 2 . Complete the map by drawing in the other 4 ski runs. Angus wants to ski all 5 ski runs, starting and finishing at the bottom of chairlift A .
Which chairlifts does Angus have to repeat, and why?
Which ski runs does Angus have to repeat, and why? The chairlifts and ski runs shown above form only part of the resort. In fact, chairlift C also takes skiers to the bottom of chairlift $D$.
Why can this information not be represented in a bipartite graph?

OCR MEI D1 2015 June Q2

7 marks

2 The following algorithm operates on the equations of 3 straight lines, each in the form $y = m _ { i } x + c _ { i }$.

Step 1	Set $i = 1$
Step 2	Input $m _ { i }$ and $c _ { i }$
Step 3	If $i = 3$ then go to Step 6
Step 4	Set $i = i + 1$
Step 5	Go to Step 2
Step 6	Set $j = 1$
Step 7	Set $a = j + 1$
Step 8	If $a > 3$ then set $a = a - 3$
Step 9	Set $b = j + 2$
Step 10	If $b > 3$ then set $b = b - 3$
Step 11	Set $d _ { j } = m _ { b } - m _ { a }$
Step 12	If $d _ { j } = 0$ then go to Step 20
Step 13	Set $x _ { j } = \frac { c _ { a } - c _ { b } } { d _ { j } }$
Step 14	Set $y _ { j } = m _ { a } \times x _ { j } + c _ { a }$
Step 15	Record $\left( x _ { j } , y _ { j } \right)$ in the print area
Step 16	If $j = 3$ then go to Step 19
Step 17	Set $j = j + 1$
Step 18	Go to Step 7
Step 19	Stop
Step 20	Record "parallel" in the print area
Step 21	Go to Step 16

Run the algorithm for the straight lines $y = 2 x + 8 , y = 2 x + 5$ and $y = 4 x + 3$ using the table given in your answer book. The first five steps have been completed, so you should continue from Step 6. [7]
Describe what the algorithm achieves.

OCR MEI D1 2015 June Q3

3 Mary takes over a small café. She will sell two types of hot drink: tea and coffee.
A coffee filter costs her $\pounds 0.10$, and makes one cup of coffee. A tea bag costs her $\pounds 0.05$ and makes one cup of tea. She has a total weekly budget of $\pounds 50$ to spend on coffee filters and tea bags. She anticipates selling at least 500 cups of hot drink per week. She estimates that between $50 \%$ and $75 \%$ of her sales of cups of hot drink will be for cups of coffee. Mary needs help to decide how many coffee filters and how many tea bags to buy per week.

Explain why the number of tea bags which she buys should be no more than the number of coffee filters, and why it should be no less than one third of the number of coffee filters.
Allocate appropriate variables, and draw a graph showing the feasible region for Mary's problem. Mary's partner suggests that she buys 375 coffee filters and 250 tea bags.
How does this suggestion relate to the estimated demand for coffee and tea?

OCR MEI D1 2015 June Q4

4 The table defines a network on 6 nodes, the numbers representing distances between those nodes.

	A	B	C	D	E	F
A		3	2	7	8	3
B	3		4	5
C	2	4			6
D	7	5
E	8		6			2
F	3				2

Use Dijkstra's algorithm to find the shortest routes from A to each of the other vertices. Give those routes and their lengths.
Jack wants to find a minimum spanning tree for the network.
1. Apply Prim's algorithm to the network, draw the minimum spanning tree and give its length. Jill suggests the following algorithm is easier.
  Step 1 Remove an arc of longest length which does not disconnect the network
  Step 2 If there is an arc which can be removed without disconnecting the network then go to Step 1
  Step 3 Stop
2. Show the order in which arcs are removed when Jill's algorithm is applied to the network.
3. Explain why Jill's algorithm always produces a minimum spanning tree for a connected network.
4. In a complete network on $n$ vertices there are $\frac { n ( n - 1 ) } { 2 }$ arcs. There are $n - 1$ arcs to include when using Prim's algorithm. How many arcs are there to remove using Jill's algorithm? For what values of $n$ does Jill have more arcs to remove than Prim has to include?

OCR MEI D1 2015 June Q5

5 The table lists activities which are involved in framing a picture. The table also lists their durations and their immediate predecessors. Except for activities C and H, each activity is undertaken by one person. Activities C and H require no people.

Activity		Duration (mins)	Immediate predecessor(s)
A	select mounting	5	-
B	glue picture to mounting	5	A
C	allow mounting glue to dry	20	B
D	measure for frame	5	A
E	select type of frame	10	A
F	cut four frame pieces	5	D, E
G	pin and glue frame pieces together	5	F
H	allow frame glue to dry	20	G
I	cut and bevel glass	30	D
J	fit glass to frame	5	H, I
K	fit mounted picture to frame	5	C, J

Draw an activity on arc network for these activities.
Mark on your diagram the early time and the late time for each event. Give the minimum completion time and the critical activities. A picture is to be framed as quickly as possible. Two people are available to do the job.
Produce a schedule to show how two people can complete the picture framing in the minimum time. To reduce the completion time an instant glue is to be used. This will reduce the time for activities C and H to 0 minutes.
Produce a schedule for two people to complete the framing in the new minimum completion time, and give that time.

OCR MEI D1 2015 June Q6

6 Adrian and Kleo like to go out for meals, sometimes to a French restaurant, and sometimes to a Greek restaurant. If their last meal out was at the French restaurant, then the probability of their next meal out being at the Greek restaurant is 0.7 , whilst the probability of it being at the French restaurant is 0.3 . If their last meal out was at the Greek restaurant, then the probability of their next meal out being at the French restaurant is 0.6 , whilst the probability of it being at the Greek restaurant is 0.4 .

Construct two simulation rules, each using single-digit random numbers, to model their choices of where to eat.

Their last meal out was at the Greek restaurant. Use the random digits printed in your answer book to simulate their choices for the next 10 of their meals out. Hence estimate the proportion of their meals out which are at the French restaurant, and the proportion which are at the Greek restaurant. Adrian and Kleo find a Hungarian restaurant which they like. The probabilities of where they eat next are now given in the following table.

\backslashbox{last meal out}{next meal out}	French	Greek	Hungarian
French	$\frac { 1 } { 5 }$	$\frac { 3 } { 5 }$	$\frac { 1 } { 5 }$
Greek	$\frac { 1 } { 2 }$	$\frac { 3 } { 10 }$	$\frac { 1 } { 5 }$
Hungarian	$\frac { 1 } { 3 }$	$\frac { 1 } { 3 }$	$\frac { 1 } { 3 }$

Construct simulation rules, each using single-digit random numbers, to model this new situation.
Their last meal out was at the Greek restaurant. Use the random digits printed in your answer book to simulate their choices for the next 10 of their meals out. Hence estimate the proportion of their meals out which are at each restaurant. \section*{END OF QUESTION PAPER}

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?

Edexcel D1 Q1

1. \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{6c6b7934-ab46-4a87-8a11-f99bf9a5d743-02_629_700_196_443} \captionsetup{labelformat=empty} \caption{Fig 1}

\end{figure}

Find a Hamiltonian cycle for the graph shown in Figure 1.
Starting with your cycle, construct a plane drawing of the graph, showing your method clearly.
(5 marks)

Edexcel D1 Q2

2. (a) The following list of numbers is to be sorted into descending order. $$\begin{array} { l l l l l l } 35 & 23 & 10 & 46 & 24 & 11 \end{array}$$ Use the Bubble sort algorithm to obtain a sorted list, giving the state of the list at each stage where two values could be interchanged.
(b) Find the maximum number of interchanges needed when 8 values are sorted into descending order using the Bubble sort algorithm.
(c) Use the first-fit decreasing algorithm to fit the data in part (a) into bins of size 50. Explain how you decided in which bin to place the number 11.

Edexcel D1 Q3

3. This question should be answered on the sheet provided. \begin{figure}[h]

\includegraphics[alt={},max width=\textwidth]{6c6b7934-ab46-4a87-8a11-f99bf9a5d743-03_744_1524_319_315} \captionsetup{labelformat=empty} \caption{Fig. 2}

\end{figure} Figure 2 shows an activity network. The nodes represent events and the arcs represent the activities. The number in each bracket gives the time, in days, needed to complete the activity.

Calculate the early and late times for each event using appropriate forward and backward scanning.
(5 marks)
Hence, determine the activities which lie on the critical path.
State the minimum number of days needed to complete the entire project.

\backslashbox{last meal out}{next meal out}	French	Greek	Hungarian
French	\(\frac { 1 } { 5 }\)	\(\frac { 3 } { 5 }\)	\(\frac { 1 } { 5 }\)
Greek	\(\frac { 1 } { 2 }\)	\(\frac { 3 } { 10 }\)	\(\frac { 1 } { 5 }\)
Hungarian	\(\frac { 1 } { 3 }\)	\(\frac { 1 } { 3 }\)	\(\frac { 1 } { 3 }\)

Step 1	Set \(i = 1\)
Step 2	Input \(m _ { i }\) and \(c _ { i }\)
Step 3	If \(i = 3\) then go to Step 6
Step 4	Set \(i = i + 1\)
Step 5	Go to Step 2
Step 6	Set \(j = 1\)
Step 7	Set \(a = j + 1\)
Step 8	If \(a > 3\) then set \(a = a - 3\)
Step 9	Set \(b = j + 2\)
Step 10	If \(b > 3\) then set \(b = b - 3\)
Step 11	Set \(d _ { j } = m _ { b } - m _ { a }\)
Step 12	If \(d _ { j } = 0\) then go to Step 20
Step 13	Set \(x _ { j } = \frac { c _ { a } - c _ { b } } { d _ { j } }\)
Step 14	Set \(y _ { j } = m _ { a } \times x _ { j } + c _ { a }\)
Step 15	Record \(\left( x _ { j } , y _ { j } \right)\) in the print area
Step 16	If \(j = 3\) then go to Step 19
Step 17	Set \(j = j + 1\)
Step 18	Go to Step 7
Step 19	Stop
Step 20	Record "parallel" in the print area
Step 21	Go to Step 16

Item	A	B	C	D	E	F
Weight \(( \mathrm { kg } )\)	2	1	6	3	3	5

Questions D1 (899 questions)

Browse by module

Browse by board

OCR MEI D1 2012 June Q3

OCR MEI D1 2012 June Q4

OCR MEI D1 2012 June Q5

OCR MEI D1 2012 June Q6

OCR MEI D1 2014 June Q1

OCR MEI D1 2014 June Q2

OCR MEI D1 2014 June Q3

OCR MEI D1 2014 June Q4

OCR MEI D1 2014 June Q5

OCR MEI D1 2014 June Q6

OCR MEI D1 2015 June Q1

OCR MEI D1 2015 June Q2

OCR MEI D1 2015 June Q3

OCR MEI D1 2015 June Q4

OCR MEI D1 2015 June Q5

OCR MEI D1 2015 June Q6

OCR MEI D1 2016 June Q1

OCR MEI D1 2016 June Q2

OCR MEI D1 2016 June Q3

OCR MEI D1 2016 June Q4

OCR MEI D1 2016 June Q5

OCR MEI D1 2016 June Q6

Edexcel D1 Q1

Edexcel D1 Q2

Edexcel D1 Q3