**Packaging Ads**

Prepared by:

Joseph Malkevitch

Department of Mathematics

York College (CUNY)

Jamaica, New York 11451

email:

__malkevitch@york.cuny.edu__

web page:

__http://york.cuny.edu/~malk/__

A local public access television station schedules programming in a way that ad breaks are limited to 90 seconds in total, and no ad can be accepted that lasts more than 80 seconds.

The station has received requests to air ads of the following lengths in seconds unless otherwise indicated:

30, 18, 10 38, 11, 19, 12, 22, 10, 10, 1/2 a minute, 7, 40, 22, 23, 42, 9, 16, 14, 40, 12, 30, 12, 1 minute, 12, 14, 16, 18, 48, 13, 17, 7, 10, 12, 14, 11, 16, 19. 28, 30, 24, 21, 51, 9, 21.

Problem 1:

a. What is the minimum number of 90-second slots that the ads can be accommodated (packaged) in?

b. Why might it make sense to have the ads placed in a minimum number of slots?

Problem 2:

What is the minimum number of 90-second slots that an ad can be accommodated in if no time slot is allowed to have more than 5 ads?

Problem 3:

Explain in words the procedure you used to find your solution.

Problem 4:

Design at least two algorithms (procedures) to solve a similar problem to Problem 1 which had: (a) A different time length t into which the ads had to be grouped (b) Different time lengths for the ads from the ones in this particular situation but using the same 90-second grouping.

Problem 5:

How can you tell whether or not the answer you got is a minimum for this particular problem? How for this "type" of problem could you tell that you had an optimal answer?

Problem 6:

Construct examples of "situations" which are similar in spirit to this type of problem but come up in different real world contexts.

(For example, one might have a plumber who has to cut different lengths of 1" diameter pipe from 1'' diameter pipes of length 3 feet and wishes to know the minimum number of 3-foot pipes he must purchase from a supply store.)

Problem 7:

How might the station decide how many 90-second time slots per hour to allow?