| Exam Board | Edexcel |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2001 |
| Session | June |
| Marks | 12 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Sorting Algorithms |
| Type | Bubble Sort Execution |
| Difficulty | Easy -1.8 This is a straightforward algorithmic execution question requiring only mechanical application of bubble sort and first-fit decreasing bin packing. Part (a) is pure procedural recall with no problem-solving, parts (b-c) are standard textbook exercises, and part (d) requires minimal optimization insight since the answer is given. |
| Spec | 7.03j Sorting: bubble sort and shuttle sort7.03l Bin packing: next-fit, first-fit, first-fit decreasing, full bin |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Marks | Guidance |
| Bubbling from left or right shown correctly | M1 | |
| Correct after 1st pass | A1 | |
| Correct after 2nd pass | A1 | |
| Correct after 3rd pass | A1 | |
| Correct final sorted list: \(20\ 25\ 30\ 35\ 40\ 45\ 50\ 55\ 90\) | A1 | c.s.o. (5) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Marks | Guidance |
| \(\frac{475}{120} \approx 3.96\) | M1 | |
| So lower bound is \(4\) tapes | A1 | (2) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Marks | Guidance |
| Tape 1: \(90 + 30\) (full) | M1 | |
| Tape 2: \(55 + 50\) | A1 | |
| Tape 3: \(45 + 40 + 35\) (full) | ||
| Tape 4: \(35 + 30 + 25 + 20\) | ||
| Tape 5: \(20\) | A1 | (3) |
| Answer | Marks | Guidance |
|---|---|---|
| Answer/Working | Marks | Guidance |
| e.g. Tape 1: \(90 + 30\) (full) | M1 | |
| Tape 2: \(55 + 35 + 30\) (full) | A1 | |
| Tape 3: \(45 + 40 + 35\) (full) | ||
| Tape 4: \(50 + 25 + 20 + 20\) | ||
| (Achieved in 4 tapes) | (2) |
## Question 5:
### Part (a):
| Answer/Working | Marks | Guidance |
|---|---|---|
| Bubbling from left **or** right shown correctly | M1 | |
| Correct after 1st pass | A1 | |
| Correct after 2nd pass | A1 | |
| Correct after 3rd pass | A1 | |
| Correct final sorted list: $20\ 25\ 30\ 35\ 40\ 45\ 50\ 55\ 90$ | A1 | c.s.o. **(5)** |
### Part (b):
| Answer/Working | Marks | Guidance |
|---|---|---|
| $\frac{475}{120} \approx 3.96$ | M1 | |
| So lower bound is $4$ tapes | A1 | **(2)** |
### Part (c):
| Answer/Working | Marks | Guidance |
|---|---|---|
| Tape 1: $90 + 30$ (full) | M1 | |
| Tape 2: $55 + 50$ | A1 | |
| Tape 3: $45 + 40 + 35$ (full) | | |
| Tape 4: $35 + 30 + 25 + 20$ | | |
| Tape 5: $20$ | A1 | **(3)** |
### Part (d):
| Answer/Working | Marks | Guidance |
|---|---|---|
| e.g. Tape 1: $90 + 30$ (full) | M1 | |
| Tape 2: $55 + 35 + 30$ (full) | A1 | |
| Tape 3: $45 + 40 + 35$ (full) | | |
| Tape 4: $50 + 25 + 20 + 20$ | | |
| (Achieved in 4 tapes) | | **(2)** |
---5.
$$90,50,55,40,20,35,30,25,45$$
\begin{enumerate}[label=(\alph*)]
\item Use the bubble sort algorithm to sort the list of numbers above into descending order showing the rearranged order after each pass.
Jessica wants to record a number of television programmes onto video tapes. Each tape is 2 hours long. The lengths, in minutes, of the programmes she wishes to record are:
$$\text { 55, 45, 20, 30, 30, 40, 20, 90, 25, 50, } 35 \text { and } 35 .$$
\item Find the total length of programmes to be recorded and hence determine a lower bound for the number of tapes required.
\item Use the first fit decreasing algorithm to fit the programmes onto her 2-hour tapes.
Jessica's friend Amy says she can fit all the programmes onto 4 tapes.
\item Show how this is possible.
\end{enumerate}
\hfill \mbox{\textit{Edexcel D1 2001 Q5 [12]}}