| Exam Board | OCR |
|---|---|
| Module | Further Discrete (Further Discrete) |
| Year | 2018 |
| Session | December |
| Marks | 11 |
| Topic | Sorting Algorithms |
| Type | Quick Sort Execution |
| Difficulty | Easy -1.2 This is a multi-part question testing basic definitions and routine algorithmic execution. Parts (a)-(c) require simple classification and counting with minimal calculation. Part (d) is a standard quicksort trace—a mechanical procedure taught explicitly in the syllabus requiring no problem-solving insight, just careful bookkeeping. |
| Spec | 5.01a Permutations and combinations: evaluate probabilities7.01a Types of problem: existence, construction, enumeration, optimisation7.01e Permutations: ordered subsets of r from n elements7.01i Selections with constraints7.03k Sorting: quick sort |
| Answer | Marks | Guidance |
|---|---|---|
| 3 | 0 | 4 |
Question 3:
3 | 0 | 4 | 33 A set of ten cards have the following values:\\
$\begin{array} { l l l l l l l l l l } 13 & 8 & 4 & 20 & 12 & 15 & 3 & 2 & 10 & 8 \end{array}$
Kerenza wonders if there is a set of these cards with a total of exactly 50 .
\begin{enumerate}[label=(\alph*)]
\item Which type of problem (existence, construction, enumeration or optimisation) is this?
The five cards $4,8,8,10$ and 20 have a total of 50.
\item How many ways are there to arrange three of these five cards (with the two 8 s being indistinguishable) so that the total of the numbers on the first two cards is less than the number on the third card?
\item How many ways are there to select (choose) three of the five cards so that the total of the numbers on the three cards is less than 25 ?
\item Show how quicksort works by using it to sort the original list of ten cards into increasing order.\\
You should indicate the pivots used and which values are already known to be in their correct position.
\end{enumerate}
\hfill \mbox{\textit{OCR Further Discrete 2018 Q3 [11]}}