D1 January 2005 Q4
4.
650 431 245 643 455 134 710 234 162 452
(a) The list of numbers above is to be sorted into descending order. Perform a Quick Sort to obtain the sorted list, giving the state of the list after each pass, indicating the pivot elements. (5)
The numbers in the list represent the lengths, in mm, of some pieces of wood. The wood is sold in one metre lengths.
(b) Use the first-fit decreasing bin packing algorithm to determine how these pieces could be cut from the minimum number of one metre lengths. (You should ignore wastage due to cutting.) (4)
(c) Determine whether your solution to part (b) is optimal. Give a reason for your answer. (2)
| Scheme | Marks |
|---|---|
E.g. | M1 A1 A1ft A1ft A1 |
| (5) |
Notes
Pivots are circled; numbers in their final positions are boxed. The passes read:
650 431 245 643 455 710 234 162 452 134
650 643 710 455 431 245 234 162 452 134
650 710 643 455 431 245 452 234 162 134
710 650 643 455 431 452 245 234 162 134
710 650 643 455 452 431 245 234 162 134 stop.
| Scheme | Marks |
|---|---|
| Bin 1 710 + 245 Bin 3 643 + 162 + 134 Bin 5 431 | M1 A1 |
| Bin 2 650 + 234 Bin 4 455 + 452 | A1ft A1 |
| (4) |
| Scheme | Marks |
|---|---|
| e.g. \(\dfrac{4116}{1000} = 4.116\ \therefore\) 5 bins needed \(\therefore\) optimal | M1 A1ft |
| (2) | |
| (11 marks) |