An algorithm is a step-by-step method for
solving a problem. This
activity takes a closer look at two of algorithms that can be used
to solve the Ice Cream Stands problem. Students have a chance to
think about ways to evaluate the effectiveness and the efficienty of an
algorithm.
Instructions
Explain to the students that the reason why finding
a solution to the Ice Creams Stands problem was so
hard is that problems like this are very hard in general. A set of
step-by-step directions for finding a solution to a problem is called an algorithm . No one has found a good (fast)
algorithm for solving problems like the Ice Cream Stands problem.
Tell students that you are going to take a look at the best algorithm
known for solving this problem. It's pretty simple: check every single
possible way to arrange the ice cream stands. When you've done that, pick
the best one. This is called a Brute Force
Algorithm .
Ask students whether they think that this plan for solving the problem
will work out well. Of course the answer depends on how many possibilities
there are to check. Have students discuss how they could find that out.
You will need a different algorithm -- a step-by-step recipe -- for
checking all of the possibilities and making sure that none are left out.
Have students design an algorithm for checking all the possibilities
for locating ice cream stands in the town of Iceberg. How many
possibilities will have to be checked? (This is not an easy question to
answer, but one well worth spending time on!
Students are likely to suggest that the Brute Force Algorithm is
acceptable because all the possibilities could be checked by a computer.
It is true that finding an algorithm that will solve a problem
is the first step to enlisting the aid of a computer in your work. Have
the students imagine that they have a computer that can find and check one
possibility in one second. With what size of graph or map does checking
all the possibilities become impossible in a reasonable amount of time?
Another kind of algorithm that mathematicians often look for when
trying to find one that will work for a problem is called a greedy algorithm . A greedy algorithm for
the Ice Cream Stands Problem would be to first find
the intersection or intersections that have the most streets coming into
them, and put ice cream stands there. Then put ice cream stands at the
intersections with the next highest number of streets coming in to them,
and so forth. How does this algorithm work for the Ice Cream Stands
problem? Will this algorithm produce a minimum dominating set
for the map of Iceberg ?
Have students review the strategies that they used when solving the
Ice Cream Stands problem. Do their strategies suggest other algorithms
that might work? For problems like this one, where there is no reliable
"best way" to solve it, mathematicians usually try several kinds of
algorithm just to see what kinds of solutions can be produced. Sometimes
those solutions will give them ideas for other things to try. Sometimes
they have to be content with the best solution they can find, never knowing
if there is a better one.
If mathematicians know more than one algorithm that might work,
another thing that they try sometimes is to switch back and forth from one
algorithm to the other. Would an approach like that work for the Ice Cream
Stands problem?
Using Brute Force to solve a problem involves checking all the
possibilities. Is it possible to draw a map for the Ice Cream Stands
problem where the number of possibilities you would have to check is
infinite?
