Adventures in Geometry for Second Graders (9/05/99)
Prepared by:
Joseph Malkevitch
Department of Mathematics and Computing
York College (CUNY)
Jamaica, New York 11451
email: malkevitch@york.cuny.edu
Dear Parents,
The "facts" of Mathematics, unlike those of science, do not have to be revised in
light of new empirical discoveries. Once mathematics is proven valid, it remains
so. This creates a problem for teachers of mathematics at all grade levels since
new mathematical ideas are being discovered all the time and never replace what has come before,
only augment it. This especially provides challenges for what new mathematics to
teach in the lower grades since youngsters, say in the second grade, do not have
a lot of prior mathematical knowledge at their disposal. Thus, it is especially nice, when
from time to time, it becomes possible to find use for skills traditionally taught
in the lower grades on a topic that is at the frontiers of the kinds of problems
mathematicians think about. But what is it precisely that mathematicians do?
If you wanted to give a simple definition of what a mathematician does, to accompany
the simple definitions that define the work of a carpenter, pharmacist, or doctor,
what definition would you offer? Mathematicians are not experts at balancing check
books, nor are they better at arithmetic in general than most people. Mathematicians are
experts in the science of studying patterns. For example, they study patterns in
numbers, patterns in knots, patterns in data (statistics) and patterns in shapes
(geometry), to give but a small sample of what mathematicians study.
One recent new domain of the study of patterns by mathematicians are patterns that
are of value in the practice of business. Are there general principles that can be
put to work to help governments and business carry out their myriad tasks more efficiently? One example of studying patterns to help businesses is the recent work that has
been done on scheduling problems. Problems about scheduling belong to the part of
mathematics called Operations Research or Management Science. Management Science
is mathematics studied in an effort to make the activities of businesses and governments go more
smoothly and in a way that minimizes cost or time.
Scheduling is a ubiquitous problem for us all..As a simple example consider scheduling
questions at a hospital. Personnel in such varied positions as nurses and people
who arrange to take patients for tests must be provided. The operating rooms must
be scheduled in an efficient as well as flexible way and there must be a system to administer
both traditional x-rays and CAT scans around the clock. There has to be someone on
duty in the pharmacy at all times and a systematic program must exist to give each
patient his/her medicines accurately and on time.
How can second graders come to see the role mathematics is playing scheduling? What
follows begins with a problem that seems to have little to do with scheduling problems
and, yet, there is a connection. Furthermore, rather surprisingly, the skills needed
involve only some logical reasoning and a knowledge of adding and subtracting numbers!
Bin Packing
Imagine that you have identical bins, say, of size or capacity 10. You also have items
of different sizes that are to be packed into these bins . Obviously, unless all
the items to be packed have size at most 10 we can not carry out the process. We
are given a large collection of such bins but they are expensive, so we would like to carry
out the packing of the items into the bins in a way which uses as few bins as possible.
This type of problem is known as bin packing
.
Can you think of situations which require solving problems of this kind? Examples
include making wooden bookcases by making cuts of different lengths from (costly)
boards of a fixed length, packing advertisements of different lengths into fixed
length station breaks on radio or television, or taking a large number of pieces of music of
different time lengths and recording them on tape cassettes or (audio) compact discs
which allow for a fixed amount of recording time. In the last example, the capacity
of the bins might be cassettes with 60 minutes of recording time and one might have pieces
with times (in minutes) of: 12, 16, 23, 31, 25, 27, 9, 11, 15, 7, 52, 48, 25, 43,
26, 4, 4, 5, 5, 7, 7, 34, and 32. What is the minimum number of cassettes needed
to record all the music?
How does one solve bin packing problems? One way would be to use trial and error.
This involves trying different clusters of items and checking whether or not they
fit into the bins. This might be acceptable if one only required the solution of
a few problems of this type. However, if one has thousands of such problems to solve, one needs
a systematic method of solving them, ideally a method that is suitable for solution
on a computer. Such methods of solving problems are known as algorithms. An algorithm
for a problem is a step-by-step description of how to solve problems of a particular
type that terminates with an answer in a finite amount of time.
What might an algorithm for solving bin packing problems be? The items to be packed
are typically given to us in a list. Using this list we would like to develop an
algorithm or procedure which systematically tells us how to go about packing the
items as given in the list into the bins, rather than trying to pack them using trial and error:
Here are examples of such procedures. When the addition of an item just fills a bin,
that bin is closed. It is convenient to think of the bins as having numbers starting
at 1. (Since the bins are displayed vertically, as the items are placed in the bins
they fill the bins up from bottom to top.)
1. Next fit: Place the next item in the list into the current bin if it fits; if it
does not, close the current bin (though it may not be full) and start a new bin.
2. First fit: Place the next item in the list into the lowest numbered bin that it
will fit into. If it will not fit into any bin, open a new one for it.
3. Worst fit: Place the next item in the list into that bin which will leave the largest
amount of room left over after the item is placed in the bin. (Here is where being
able to subtract comes in handy.)
4. Best fit: Place the next item in the list into that bin which will leave the least
room left over after the the item is placed in the bin.
Here is an example that will help illustrate the idea:
Pack 8, 5, 7, 6, 2, 4, 1 into bins of capacity 10, using next fit, first fit, worst
fit, and best fit. In the diagrams below, space without a number label is empty space
in the bin.
Next fit:
bin 1 bin 2 bin 3 bin 4
bin 5
Figure 1
First fit:
Figure 2
Worst fit:
Figrue 3
Best fit:
Figure 4
In this particular example, it is not difficult to see that one can not pack these
items in fewer than 4 bins and, thus, we have achieved several different optimal
packings. (If one add the values of the items to be packed: 8 + 5 + 7 + 6 + 2 + 4
+ 1 one gets 33. Now 33 divided by 10 is 3.3 which means that one can not possibility pack these
items into only 3 bins.) In general, there is no guarantee that any of these 4 algorithms
will yield an optimal solution. (In fact, it is fun to produce examples which show that for a particular list which one might create, next fit, say, yields an optimal
solution, while the other three methods do not. This is the type of "entertainment"
that mathematicians enjoy!) It may surprise you to learn that no one knows any procedure (algorithm) for solving bin packing problems that always guarantees a minimum
number of bins and that is fast and easy to carry out. (One can always try all the
different possibilities, "brute force," to obtain an answer, but this is not practical
for even modest sized problems because it would take too long.)
In our discussion of the four procedures above, although next fit requires more bins,
it does not require as much memory (human or computer), since it is not necessary
to keep track of how much space is left in many bins, since one only examines one
bin at a time. This is a "baby" example. Realistic examples might have millions of items
to pack into hundreds or thousands of bins, and for such problems the trade off between
time and space issues (using memory to keep track of how much room is left in the
many partially filled bins) can be significant.
If you experiment with problems similar to this one and with different sized bins
and longer lists of items to pack, you will notice a problem that often occurs. Large
or medium size items occurring late in a list are hard to pack since there is little
room left over in the partially filled bins to accommodate them. This suggests a different
approach to solving bin packing problems. First sort
the items in the list in decreasing order (i.e. largest items down to smallest items)
and then use one of the four algorithms described above, using the newly generated
decreasing time list. Sorting numbers by size is something 2nd graders should practice. Bin packing provides a meaningful context. (The sorted list for the problem above
is: 8, 7, 6, 5, 4, 2, 1.) This gives rise to four new algorithms: next fit decreasing,
first fit decreasing, worst fit decreasing and best fit decreasing. Usually, this
approach will use fewer bins (but not always!) but there is a price to pay. One needs
to sort what are sometimes very long lists first, which can be time consuming. (Is
the trade-off between the extra time to sort worth the fact that often fewer bins
will be needed?) Although first fit or best fit decreasing do not always give optimal answers,
there work remarkably well on most problems.
I began this discussion with commenting on the role mathematics is playing in scheduling
problems. Though some of the many applications of bin packing were mentioned above,
what does bin packing have to do with scheduling?
Machine Scheduling Independent Tasks
The problem of scheduling processors to accomplish a collection of tasks is extremely
complicated, even in the simple case we look at here, where the processors are all
identical. Some of the complications that are involved are that the tasks may have
a complex collection of requirements for the order in which they can be done. For example,
before one can put up the walls of a house, the foundation must be poured. In some
rare cases, however, the tasks are independent of one another, and, thus, can be
scheduled in any order whatsoever. (One example is processing jobs at a photocopy shop
after the shop has closed for the day, and all jobs are to be finished by the morning.)
Suppose we have a collection of independent tasks (each requiring a specific amount
of time) which we would like to schedule so that they are completed by a fixed time
W. We can think of this problem as a bin packing problem!. The items to be packed
are the tasks with their different times to accomplish, and the bins play the role
of the processors. The fact that each processor must finish no later than a particular time
corresponds to the (fixed) capacity of the bins. The goal is to find the minimum
number of bins that will be required, which corresponds in the scheduling context
to finding the minimum number of machines necessary to finish all the tasks by the fixed time
W (the capacity of the bins.)
Practicing arithmetic
The skills needed to solve bin packing problems are some logical thinking skills,
being able to compare sizes of numbers, and skill at basic addition and subtraction.
Mathematics educators are beginning to see a pattern of increased interest in mathematics for many students when contexts are provided for doing basic mathematics rather
than merely doing long collections of problems without any suggestions of the reason
one might ever have to carry out problems of this kind. Bin packing offers a nice
"playground" for seeing the applicability of some simple mathematics while at the same time
offering the opportunity for practicing basic arithmetic skills.
Practice:
Here is a problem that will give you a chance to check that you and your child understand
the 8 different algorithms.
Items to pack:
6,6,5,5,5,4,4,4,4,2,2,2,2,3,3,7,7,5,5,8,8,4,4,5
Bin size: 10
(Partial answers: next fit 17 bins; first fit 14 bins; worst fit 14 bins; first fit
decreasing 13 bins.) 13 bins is optimal.
Experiments: (If you have children at home who are in higher grades you might encourage
them to read these notes and try out these questions.)
1. Once you have mastered the 8 algorithms involved you can try experiments with other
bin sizes. What happens when the bin size is 9? What happens when the bin size is
11? Experiments of these kinds provide interesting practice at arithmetic, estimation
(will the number of bins go up or down when the bin size is changed from 10 to 9 or
11, and can you estimate by how much?), and logical thinking.
2. If you double the capacity of the bins will you halve the number of bins necessary?
3. If you halve the capacity of the bins will you double the number of bins necessary?
(Can you always carry out the packing in this case?)
4. Can you find an example where next fit requires fewer bins than first fit?
Can you find an example where first fit requires fewer bins than next fit?
5. Can you find an example where first fit requires fewer bins than worst fit?
Can you find an example where worst fit requires fewer bins than first fit?
6. Try making up a few problems of your own and exploring new algorithms of your invention
to solve bin packing!
References:
1. Graham, R., Combinatorial scheduling theory. In Lynn Steen (ed.), Mathematics Today,
Springer-Verlag, New York, 1978.
2. Graham, R., The combinatorial mathematics of scheduling, Scientific American, March,
1978, pp. 124-132.
3. Malkevitch, J., (et al.), For All Practical Purposes, 4th edition (also earlier
editions), W.H. Freeman, New York, 1997, pp. 102-106.
Acknowledgement
Some of this work was prepared with partial support from the National Science Foundation
(Grant Number: DUE 9555401) to the Long Island Consortium for Interconnected Learning
(administered by SUNY at Stony Brook, Alan Tucker, Project Director).
Figure 5