Welcome to the forum and Merry Christmas!

9) Joan decided that she wanted to record a number of programmes on the video recorder. The lengths of the programmes were;

45 min, 1h, 35min, 15min, 40min, 30min, 50min, 55min and 25min.

This is a bin packing problem. The first fit algorithm just takes them as you see them and puts them into the first available bin that they will fit.

Think of the tapes as bins that hold 120 minutes. So start packing.

1st bin: 45 min, 1 hr., 15 min.

2nd bin:35min, 40min, 30 min

3rd bin: 50 min, 55 min,

4th bin: 25 min.

Answer she needs 4 tapes. The algorithm may not have provided the optimum answer but it did provide an answer.

The first-fit decreasing algorithm, sorts the list first, largest to smallest. Then applies the above first fit algorithm.

Bin 1) 60 min, 55min

Bin 2) 50min, 45min, 15min

Bin 3) 40min, 35min, 30min

Bin 4) 25 min

This also requires four tapes.

Can you find a tighter packing than both of these algorithms?

]]>A - 3

B - 8

C - 7

D - 5

E - 8

F - 4

G - 5

H - 4

I - 4

J - 4

To determine how many workers are required;

(a) Apply the first-fit algorithm

(b) Apply the first-fit decreasing algorithm

(c) Is it possible to obtain a better solution than either (a) or (b)?

7) A small ferry that sails between two of the islands in the Hebrides has three lanes 20 metres long on its car deck. The vehicles waiting to be loaded are;

Petrol Tanker - 13m

Small Truck - 6m

Car - 4m

Small Van - 3m

Coach - 12m

Lorry - 11m

Truck - 7m

Car - 3m

(a) Can you use the first-fit decreasing algorithm to load all the vehicles on to the ferry?

(b) Can all te vehicles be taken in one trip?

8) A project consists of eight activities whose durations in hours are as follows;

A - 2

B - 4

C - 3

D - 1

E - 5

F - 4

G - 2

H - 3

Use full-bin combinations to determine the minimum number of workers needed to finish the project in 12 hours.

8) A certain kind of pipe is sold in 10m lengths. For a particular job the following lengths are required;

2m, 8m, 4m, 5m, 2m, 5m, 4m

By looking for full-bin combinations, or otherwise, find the number of 10m lengths required for the job.

9) Joan decided that she wanted to record a number of programmes on the video recorder. The lengths of the programmes were;

45 min, 1h, 35min, 15min, 40min, 30min, 50min, 55min and 25min.

Help Joan decide how many 2h tapes she requires, using;

(a) The first-fit algorithm

(b) The first-fit decreasing algorithm

(c) Full-bin combinations

10) 120, 78, 100, 90, 60, 38, 80, 26, 150

(a) The list of numbers above is to be sorted into descending order. Perform a quick-sort to obtain the required list. Give the state of the list after each rearrangement and indicate clearly the pivot elements used.

(b) (i) Use the first-fit decreasing algorithm to fit the data into bins of size 200.

(ii) Explain how you decided into which bin to place the number 78.

1) The marks obtained in an examination by five students were;

Anne (68), Barry (42), Clare (70), David (45), Eileen (50) and Greg (55).

Use the bubble-sort algorithm to sort these marks

(a) in ascending order

(b) in descending order

2) Use the quick-sort algorithm to sort the list

6, 8, 4, 5, 10, 2, 9

in ascending order.

3) The members of a club have surnames

Monro, Jones, Malik, Wilson and Shah

Use the bubble-sort algorithm to sort these into alphabetical order.

4) Use the bubble-sort algorithm to sort these into alphabetical order;

4, -3, -5, 0, 2, 5, -1

5) The times recorded by seven competitors for a given distance were;

9.8, 9.2, 9.6, 9.7, 9.1, 8.9, 9.0

(a) Use the bubble-sort algorithm to sort these times into order.

(b) Use the quick-sort algorithm to sort the times into ascending order.

(c) Which of the methods is more efficient in this case?