Algorithms, the dominating set problem, and the NCTM Standards

The "Foundational Four"

Mathematics as Problem Solving, Mathematics as Communication, Mathematics as Reasoning, and Mathematical Connections are critical items throughout the NCTM Standards. They appear at every level because they form the core of what it means to do mathematics.

The questions below are examples of some of the questions that will come to mind when working on the Ice Cream Stands problem and its variations. When students think, talk, and write about these questions, all of the four Standards at the foundation of doing mathematics are reinforced.

Do I need to put an ice cream stand here?
Would it be a good idea to put an ice cream stand here?
How should I plan for my ice cream stands if I'm trying not to build very many?
What would be a good system for deciding where to put ice cream stands so that I could spend more time building them and less time trying to figure out where to build them?

Spatial Sense

At all levels, there is an NCTM Standard that talks about the development of spatial sense. The meaning of "spatial sense" that springs to mind most quickly is generally the sense of geometric space, particularly patterns and relationships that have to do geometric figures.

When you begin to look for a solution to the Ice Cream Stands problem, whether or not you choose to place an ice cream stand on a corner depends on the relationship in space between that corner, the other streetcorners indicated on the map, and the ice cream stands you have already "built". When you try to find a "best" or minimum solution for the problem, the spatial reasoning that you use becomes even more complex. Yet this particular brand of spatial reasoning is not geometric.

This is only one kind of non-geometric spatial reasoning which engages mathematicians. Other examples of different types of spatial reasoning are found in the activities with knots, graphs, finite state machines and map coloring.

Number sense, numeration, number relationships, and computation

Why not use a computer to solve the Ice Cream Stands problem? Just have it try each one of the possibilities and then pick the best one. It certainly seems like a reasonable idea. Actually, though, it's a terrible idea. But you have to have some savvy with numbers to realize that right away.

The issue here is computatonal complexity. On the one hand computers have taken away much of the drudgery associated with numerical computations. But when we give a computer something to do or to count, even though they work very fast, it is still possible to give them too much!

How much is too much? You have to look at the numbers. For the ice cream stands problem, this means asking how will we go about checking all the possibilities, and how many possibilities will we have to check. This is a very interesting and complex counting task. There are many ways to do it, but they all involve a series of relatively simple steps. This means that even very young and inexperienced students can take on the task, and students of all levels can see that the count of the number of possibilities is going to get overwhelmingly large quite fast?

Counting tasks such as these abound in computer science. Very often, procedures that seem simple can explode into a huge series of tasks, too many even for a computer to do. It is important for computer scientists to develop the right kind of number sense to know when to be alert for procedures that may do that.