D1 June 2008 Q1
1.
| 29 | 52 | 73 | 87 | 74 | 47 | 38 | 61 | 41 |
The numbers in the list represent the lengths in minutes of nine radio programmes. They are to be recorded onto tapes which each store up to 100 minutes of programmes.
(a) Obtain a lower bound for the number of tapes needed to store the nine programmes. (2)
(b) Use the first-fit bin packing algorithm to fit the programmes onto the tapes. (3)
(c) Use the first-fit decreasing bin packing algorithm to fit the programmes onto the tapes. (3)
| Scheme | Marks |
|---|---|
| \(\dfrac{502}{100} = 5.02\) so 6 tapes. | M1 A1 |
| (2) |
Notes
1M1: \((502 \pm 40) \div 100\) (maybe implicit)
1A1: cao 6 tapes
| Scheme | Marks |
|---|---|
| Bin 1: 29, 52 Bin 5: 47, 38 Bin 2: 73 Bin 6: 61 Bin 3: 87 Bin 7: 41 Bin 4: 74 | M1 A1 A1 |
| (3) |
Notes
1M1: Bin 1 correct and at least 8 values put in bins
1A1: Condone one error, (e.g. extra, omission, ‘balanced’swap).
2A1: All correct
| Scheme | Marks |
|---|---|
| Bin 1: 87 Bin 4: 61, 38 Bin 2: 74 Bin 5: 52, 47 Bin 3: 73 Bin 6: 41, 29 | M1 A1 A1 |
| (3) | |
| (8 marks) |
Notes
1M1: Bin 1 correct and at least 8 values put in bins
1A1: Condone one error, (e.g. extra, omission, ‘balanced’swap).
2A1: All correct