OCR MEI D1 2007 January — Question 3 8 marks

Exam BoardOCR MEI
ModuleD1 (Decision Mathematics 1)
Year2007
SessionJanuary
Marks8
PaperDownload PDF ↗
Mark schemeDownload PDF ↗
TopicDynamic Programming
TypeRecurrence relation solution
DifficultyEasy -1.2 This is a straightforward simulation question requiring basic probability understanding and following a simple algorithm. Students need only assign digits to outcomes (trivial with 5 equally likely options), follow a stopping rule, and calculate a mean from 5 trials. No complex probability theory, proof, or problem-solving insight is required—just mechanical execution of a standard D1 simulation procedure.
Spec2.03e Model with probability: critiquing assumptions
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.
  1. Show how to use single digit random numbers to simulate the process efficiently. You need to describe exactly how your simulation will work. [3]
  2. Use the random numbers in your answer book to run your simulation 5 times, recording your results. [2]
  3. From your results compute an estimate of the mean number of draws needed to get a vowel. [2]
  4. State how you could produce a more accurate estimate. [1]
Question 3:
3
2 The following algorithm is a version of bubble sort.
Step 1 Store the values to be sorted in locations L(1), L(2), … , L(n) and set i to be the
number, n, of values to be sorted.
Step 2 Set j = 1.
Step 3 Compare the values in locations L(j) and L(j+1) and swap them if that in L(j) is
larger than that in L(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, L(1), L(2), … , L(n).
Step 6 Subtract 1 from i.
Step 7 If i is larger than 1 then go to step 2.
Step 8 Stop.
(i) Apply this algorithm to sort the following list.
109 32 3 523 58.
Count the number of comparisons and the number of swaps which you make in applying the
algorithm. [4]
(ii) Put the five values into the order which maximises the number of swaps made in applying the
algorithm, and give that number. [2]
(iii) 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
100 000 values? (Give your answer in hours and minutes.) [2]
3 Abag 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 (Aor 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.
(i) Show how to use single digit random numbers to simulate the process efficiently. You need to
describe exactly how your simulation will work. [3]
(ii) Use the random numbers in your answer book to run your simulation 5 times, recording your
results. [2]
(iii) From your results compute an estimate of the mean number of draws needed to get a vowel.
[2]
(iv) State how you could produce a more accurate estimate. [1]
[Turn over
© OCR 2007 4771/01 Jan 07
Question 3:
3
2 The following algorithm is a version of bubble sort.
Step 1 Store the values to be sorted in locations L(1), L(2), … , L(n) and set i to be the
number, n, of values to be sorted.
Step 2 Set j = 1.
Step 3 Compare the values in locations L(j) and L(j+1) and swap them if that in L(j) is
larger than that in L(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, L(1), L(2), … , L(n).
Step 6 Subtract 1 from i.
Step 7 If i is larger than 1 then go to step 2.
Step 8 Stop.
(i) Apply this algorithm to sort the following list.
109 32 3 523 58.
Count the number of comparisons and the number of swaps which you make in applying the
algorithm. [4]
(ii) Put the five values into the order which maximises the number of swaps made in applying the
algorithm, and give that number. [2]
(iii) 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
100 000 values? (Give your answer in hours and minutes.) [2]
3 Abag 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 (Aor 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.
(i) Show how to use single digit random numbers to simulate the process efficiently. You need to
describe exactly how your simulation will work. [3]
(ii) Use the random numbers in your answer book to run your simulation 5 times, recording your
results. [2]
(iii) From your results compute an estimate of the mean number of draws needed to get a vowel.
[2]
(iv) State how you could produce a more accurate estimate. [1]
[Turn over
© OCR 2007 4771/01 Jan 07
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.

\begin{enumerate}[label=(\roman*)]
\item Show how to use single digit random numbers to simulate the process efficiently. You need to describe exactly how your simulation will work. [3]

\item Use the random numbers in your answer book to run your simulation 5 times, recording your results. [2]

\item From your results compute an estimate of the mean number of draws needed to get a vowel. [2]

\item State how you could produce a more accurate estimate. [1]
\end{enumerate}

\hfill \mbox{\textit{OCR MEI D1 2007 Q3 [8]}}
This paper (6 questions)
View full paper
Q1 8 Q2 8 Q3 8 Q4 16 Q5 16 Q6 16