| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2012 |
| Session | January |
| Marks | 13 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Permutations & Arrangements |
| Type | Sorting and searching algorithms |
| Difficulty | Easy -1.2 This is a straightforward algorithmic application question from D1 requiring mechanical execution of standard algorithms (first-fit bin packing, bubble sort, first-fit decreasing) with no problem-solving or insight needed. The algorithms are routine procedures tested exactly as taught, making this easier than average A-level questions which typically require some mathematical reasoning. |
| Spec | 7.03j Sorting: bubble sort and shuttle sort7.03l Bin packing: next-fit, first-fit, first-fit decreasing, full bin |
| 5 | 1 | 8 | 13 | 16 | 5 | 8 | 2 | 15 | 12 | 10 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Marks | Guidance |
| Bin 1: 5, 1, 8, 5 \(\quad\) Bin 4: 8, 12 | M1 | Bin 1 correct; 13 and 16 in bins 2 and 3 |
| Bin 2: 13, 2 \(\quad\) Bin 5: 15 | A1 | Bin 2 correct; 8 in bin 4 |
| Bin 3: 16 \(\quad\) Bin 6: 10 | A1 | CAO |
| 3 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Marks | Guidance |
| Bubble sort left to right shown with passes | M1 | End number (greatest/least) in place; consistent direction throughout |
| First pass correct | A1 | |
| \(2^{\text{nd}}\) and \(3^{\text{rd}}\) passes correct — end three numbers in place | A1ft | |
| \(4^{\text{th}}\) and \(5^{\text{th}}\) passes correct — end five numbers in place | A1ft | |
| CSO including 'sorted', or extra pass, ruling off, boxed, ticked etc. | A1 | |
| Final list: 16, 15, 13, 12, 10, 8, 8, 5, 5, 2, 1 + 'sorted' | ||
| 5 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Marks | Guidance |
| Bin 1: 16, 2, 1 \(\quad\) Bin 4: 12, 8 | M1 | Bins 4 and 5 correct, others started |
| Bin 2: 15, 5 \(\quad\) Bin 5: 10, 8 | A1 | Bins 2 and 3 correct up to the 5s |
| Bin 3: 13, 5 | A1 | CAO |
| 3 |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Marks | Guidance |
| \(\dfrac{95}{20} = 4.75\) so a minimum of 5 bins needed | M1 | Numerical argument; attempt to find lower bound |
| A1 | Correct numerical argument; conclusion (the yes/no may follow from (c)) | |
| 2 |
# Question 5:
## Part (a):
| Answer/Working | Marks | Guidance |
|---|---|---|
| Bin 1: 5, 1, 8, 5 $\quad$ Bin 4: 8, 12 | M1 | Bin 1 correct; 13 and 16 in bins 2 and 3 |
| Bin 2: 13, 2 $\quad$ Bin 5: 15 | A1 | Bin 2 correct; 8 in bin 4 |
| Bin 3: 16 $\quad$ Bin 6: 10 | A1 | CAO |
| | **3** | |
## Part (b):
| Answer/Working | Marks | Guidance |
|---|---|---|
| Bubble sort left to right shown with passes | M1 | End number (greatest/least) in place; consistent direction throughout |
| First pass correct | A1 | |
| $2^{\text{nd}}$ and $3^{\text{rd}}$ passes correct — end three numbers in place | A1ft | |
| $4^{\text{th}}$ and $5^{\text{th}}$ passes correct — end five numbers in place | A1ft | |
| CSO including 'sorted', or extra pass, ruling off, boxed, ticked etc. | A1 | |
| Final list: 16, 15, 13, 12, 10, 8, 8, 5, 5, 2, 1 + 'sorted' | | |
| | **5** | |
## Part (c):
| Answer/Working | Marks | Guidance |
|---|---|---|
| Bin 1: 16, 2, 1 $\quad$ Bin 4: 12, 8 | M1 | Bins 4 and 5 correct, others started |
| Bin 2: 15, 5 $\quad$ Bin 5: 10, 8 | A1 | Bins 2 and 3 correct up to the 5s |
| Bin 3: 13, 5 | A1 | CAO |
| | **3** | |
## Part (d):
| Answer/Working | Marks | Guidance |
|---|---|---|
| $\dfrac{95}{20} = 4.75$ so a minimum of 5 bins needed | M1 | Numerical argument; attempt to find lower bound |
| | A1 | Correct numerical argument; conclusion (the yes/no may follow from (c)) |
| | **2** | |5.
\begin{center}
\begin{tabular}{ l l l l l l l l l l l }
5 & 1 & 8 & 13 & 16 & 5 & 8 & 2 & 15 & 12 & 10 \\
\end{tabular}
\end{center}
\begin{enumerate}[label=(\alph*)]
\item Use the first-fit bin packing algorithm to determine how the numbers listed above can be packed into bins of size 20.
\item The list of numbers is to be sorted into descending order. Use a bubble sort to obtain the sorted list, giving the state of the list after each complete pass.
\item Apply the first-fit decreasing bin packing algorithm to your ordered list to pack the numbers into bins of size 20.
\item Determine whether your answer to (c) uses the minimum number of bins. You must justify your answer.
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 2012 Q5 [13]}}