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)