OCR MEI D1 (Decision Mathematics 1) 2007 January

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

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}

1. Produce the graph for the symbol
2. Give two symbols each having the graph
   \includegraphics[max width=\textwidth, alt={}, center]{a56f79f4-3b71-4ae3-a88b-5a88b0197433-2_52_199_1187_1030}
3. Produce the graph for the symbol .
4. Produce a single graph for the composite symbol
   \includegraphics[max width=\textwidth, alt={}, center]{a56f79f4-3b71-4ae3-a88b-5a88b0197433-2_112_158_1398_1165}
5. 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.
6. 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.
7. Put the five values into the order which maximises the number of swaps made in applying the algorithm, and give that number.
8. 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.
9. Show how to use single digit random numbers to simulate the process efficiently. You need to describe exactly how your simulation will work.
10. Use the random numbers in your answer book to run your simulation 5 times, recording your results.
11. From your results compute an estimate of the mean number of draws needed to get a vowel.
12. State how you could produce a more accurate estimate. Section B (48 marks)

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}

1. Produce the graph for the symbol
2. Give two symbols each having the graph
   \includegraphics[max width=\textwidth, alt={}, center]{a56f79f4-3b71-4ae3-a88b-5a88b0197433-2_52_199_1187_1030}
3. Produce the graph for the symbol .
4. Produce a single graph for the composite symbol
   \includegraphics[max width=\textwidth, alt={}, center]{a56f79f4-3b71-4ae3-a88b-5a88b0197433-2_112_158_1398_1165}
5. 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.
6. 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.
7. Put the five values into the order which maximises the number of swaps made in applying the algorithm, and give that number.
8. 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.
9. Show how to use single digit random numbers to simulate the process efficiently. You need to describe exactly how your simulation will work.
10. Use the random numbers in your answer book to run your simulation 5 times, recording your results.
11. From your results compute an estimate of the mean number of draws needed to get a vowel.
12. 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

13. Draw an activity-on-arc network to represent this information.
14. Find the early time and the late time for each event. Give the project duration and list the critical activities.
15. 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.
16. Formulate Leone's problem as a linear programming problem.
17. Produce a graph to illustrate the inequalities.
18. Solve Leone's problem.
19. If Leone had more than \(\pounds 500\) available initially, how much extra could she spend to minimize maintenance costs?

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}

1. Produce the graph for the symbol
2. Give two symbols each having the graph
   \includegraphics[max width=\textwidth, alt={}, center]{a56f79f4-3b71-4ae3-a88b-5a88b0197433-2_52_199_1187_1030}
3. Produce the graph for the symbol .
4. Produce a single graph for the composite symbol
   \includegraphics[max width=\textwidth, alt={}, center]{a56f79f4-3b71-4ae3-a88b-5a88b0197433-2_112_158_1398_1165}
5. 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.
6. 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.
7. Put the five values into the order which maximises the number of swaps made in applying the algorithm, and give that number.
8. 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.
9. Show how to use single digit random numbers to simulate the process efficiently. You need to describe exactly how your simulation will work.
10. Use the random numbers in your answer book to run your simulation 5 times, recording your results.
11. From your results compute an estimate of the mean number of draws needed to get a vowel.
12. 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

13. Draw an activity-on-arc network to represent this information.
14. Find the early time and the late time for each event. Give the project duration and list the critical activities.
15. 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.
16. Formulate Leone's problem as a linear programming problem.
17. Produce a graph to illustrate the inequalities.
18. Solve Leone's problem.
19. If Leone had more than \(\pounds 500\) available initially, how much extra could she spend to minimize maintenance costs? 6 In a factory a network of pipes connects 6 vats, A, B, C, D, E and F. Two separate connectors need to be chosen from the network The table shows the lengths of pipes (metres) connecting the 6 vats.

    	A	B	C	D	E	F
    A	-	7	-	-	12	-
    B	7	-	5	3	6	6
    C	-	5	-	8	4	7
    D	-	3	8	-	1	5
    E	12	6	4	1	-	7
    F	-	6	7	5	7	-

20. Use Kruskal's algorithm to find a minimum connector. Show the order in which you select pipes, draw your connector and give its total length.
21. Produce a new table excluding the pipes which you selected in part (i). Use the tabular form of Prim's algorithm to find a second minimum connector from this reduced set of pipes. Show your working, draw your connector and give its total length.
22. The factory manager prefers the following pair of connectors:
    \(\{ \mathrm { AB } , \mathrm { BC } , \mathrm { BD } , \mathrm { BE } , \mathrm { BF } \}\) and \(\{ \mathrm { AE } , \mathrm { BF } , \mathrm { CE } , \mathrm { DE } , \mathrm { DF } \}\).
    Give two possible reasons for this preference.