An enrichment and extension programme for primary-aged children



Download 3.32 Mb.
Page1/6
Date29.03.2017
Size3.32 Mb.
  1   2   3   4   5   6


Teacher’s Edition Parts IV, V and VI


An enrichment and extension

programme for primary-aged children

Created by

Tim Bell, Ian H. Witten and Mike Fellows

Adapted for classroom use by Isaac Freeman, based on work by Robyn Adams and Jane McKenzie

Illustrations by Malcolm Robinson, Gail Williams, Matt Powell and Isaac Freeman


Introduction

This book adds 8 more activities to the Teacher’s Edition of Computer Science Unplugged. These activities were in the original 1999 edition, but have been updated to the style developed for classroom use in the 2002 Teacher’s Edition.



This book is available for free download for personal and educational use thanks to a generous grant by Google, Inc. It is distributed under a Creative Commons Attribution-NonCommercial-ShareAlike licence, which means that you are free to share (copy, distribute, and transmit) the book. It also allows you to remix the book. These are only available under the following conditions: you include attribution to the authors, you do not use this book for commercial purposes, and if you alter, transform or build upon this work, you share under the same or similar license. More details of this license can be found online by searching: CC BY-NC-SA 3.0.

We encourage the use of this material in educational settings, and you are welcome to print your own copy of the book and distribute worksheets from it to students. We welcome enquiries and suggestions, which should be directed to the authors (see csunplugged.org).


This book is being translated into several other languages. Please check the web site for information about the availability of translations.

Contents


An enrichment and extension 106

programme for primary-aged children 106

106

Created by 106



Tim Bell, Ian H. Witten and Mike Fellows 106

Adapted for classroom use by Isaac Freeman, based on work by Robyn Adams and Jane McKenzie 106

Illustrations by Malcolm Robinson, Gail Williams, Matt Powell and Isaac Freeman 106

Part VI 1

Really hard problems—Intractability 1

The poor cartographer—Graph coloring

Tourist town—Dominating sets

Ice roads —Steiner trees

Part V 1

Sharing secrets and fighting crime-Cryptography 1

Sharing secrets—Information hiding protocols

The Peruvian coin flip—Cryptographic protocols

Kid Krypto—Public-key encryption

Part VI 1

The human face of computing-Interacting with computers 1

The chocolate factory—Human interface design

Conversations with computers—The Turing test


187

Part VI


Really hard problems—Intractability

Intractability

Are there problems that are too hard even for computers? Yes. We will see in Activity 20 that just having a conversation—chatting—is something computers can't do, not because they can't speak but because they can't understand or think of sensible things to say, but that’s not the kind of hard problem we’re talking about here - it's not that computers can’t have conversations, more that we don't know just how we do it ourselves and so we can't tell the computer what to do. But in this section we're going to look at problems where it's easy to tell the computer what to do—by writing a program—but the computer can't do what we want because it takes far too long: millions of centuries, perhaps. Not much good buying a faster computer: if it were a hundred times faster it would still take millions of years; even one a million times faster would take hundreds of years. That's what you call a hard problem—one where it takes far longer than the lifetime of the fastest computer imaginable to come up with a solution!

The activities in Part II on algorithms showed you how to find ways of making computer programs run more efficiently. In this section we look at problems for which no efficient solutions are known, problems that take computers millions of centuries to solve. And we will encounter what is surely the greatest mystery in computer science today: that no-one knows whether there's a more efficient way of solving these problems! It may be just that no-one has come up with a good way yet, or it may be that there is no good way. We don't know which. And that's not all. There are thousands of problems that, although they look completely different, are equivalent in the sense that if an efficient method is found to solve one, it can be converted into an efficient method to solve them all. In these activities you will learn about these problems.

For teachers

There are three activities in this section. The first involves coloring maps and counting how many colors are needed to make neighboring countries different. The second requires the ability to use a simple street map, and involves placing ice-cream vans at street corners so that nobody has to go too far to get an ice-cream. The third is an outdoor activity that uses string and pegs to explore how to make short networks connecting a set of points.

The activities provide a hands-on appreciation of the idea of complexity—how problems that are very simple to state can turn out to be incredibly hard to solve. And these problems are not abstruse. They are practical questions that arise in everyday activities such as mapping, school time-tabling, and road building. The computational underpinning rests on a notion called “NP-completeness” that is explained in the What's it all about? sections at the end of each activity. Although the activities themselves can be tackled in any order, these sections are intended to be read in the order in which they appear. By the time you reach the end you will have a firm grip on the most important open question in contemporary computer science.

The technical name for this part is “intractability” because problems that are hard to solve are called intractable. The word comes the Latin tractare meaning to draw or drag, leading to the modern usage of tractable as easy to handle, pliant, or docile. Intractable problems are ones that are not easily dealt with because it would take too long to come up with an answer. Although it may sound esoteric, intractability is of great practical interest because a breakthrough in this area would have major ramifications for many different lines of research. For example, most cryptographic codes rely on the intractability of some problems, and a criminal who managed to come up with an efficient solution could have a field day decoding secrets and selling them, or—more simply—just making phoney bank transactions. We will look at these things in Part V—Cryptography.


Activity 13

The poor cartographer—Graph coloring


Summary

Many optimization problems involve situations where certain events cannot occur at the same time, or where certain members of a set of objects cannot be adjacent. For example, anyone who has tried to timetable classes or meetings will have encountered the problem of satisfying the constraints on all the people involved. Many of these difficulties are crystallized in the map coloring problem, in which colors must be chosen for countries on a map in a way that makes bordering countries different colors. This activity is about that problem.
Curriculum Links

  • Mathematics: Number Level 2 and up. Exploring numbers in other bases. Representing numbers in base two.

  • Mathematics: Algebra Level 2 and up. Continue a sequential pattern, and describe a rule for this pattern. Patterns and relationships in powers of two.
Skills

  • Problem solving.

  • Logical reasoning.

  • Algorithmic procedures and complexity.

  • Communication of insights.
Ages

  • 7 and up
Materials

  • a whiteboard or similar writing surface.

Each student will need:

  • a copy of one or more of the worksheets,

  • movable small colored markers (e.g. counters or poker chips), and

  • four crayons of different colors (or colored pencils, felt tips etc.)

G
raph Coloring

Introduction

This activity revolves around a story in which the students have been asked to help out a cartographer, or map-maker, who is coloring in the countries on a map. It doesn't matter which color a country is, so long as it’s different to all bordering countries.

For example, this map shows four countries. If we color Northland red, then Westland and Eastland cannot be red, since their border with Northland would be hard to see. We could color Westland green, and it is also acceptable to color Eastland green because it does not share a border with Westland. (If two countries meet only at a single point, they do not count as sharing a border and hence can be made the same color.) Southland can be colored red, and we end up needing only two colors for the map.
In our story, the cartographer is poor and can't afford many crayons, so the idea is to use as few colors as possible.

Discussion

Describe the problem that the students will be working on, demonstrating the coloring process on a blackboard.

Give out a copy of the first worksheet. This map can be colored correctly using only two colors. Although restricting the number of colors to just two might sound particularly challenging, the task is quite simple compared with maps that require more colors because there is very little choice about what color each country can be.

Have the students try to color the map in with only two colors. In the process they may discover the “has-to-be” rule: once one country is colored in, any bordering country has to be the opposite color. This rule is applied repeatedly until all countries are colored in. It is best if the students can discover this rule for themselves, rather than being told it, as it will give them a better insight into the process.

As students complete each exercise they can be given the next sheet to try.

The students may also discover that it is better to use place-holders, such as colored counters, instead of coloring the countries straight away, since this makes it easier for them to change their mind.

For older students, ask them to explain how they know that they have found the minimum number of colors. For example, at least three colors are required for this map because it includes a group of three countries (the largest three), each of which has borders with the other two.

If a student finishes all the sheets early, ask them to try to devise a map that requires five different colors. It has been proved that any map can be colored with only four colors, so this task will keep them occupied for some time! In our experience students will quickly find maps that they believe require five colors, but of course it is always possible to find a four-color solution to their maps.

Worksheet Activity: Graph Coloring 1

Color in the countries on this map with as few colors as possible, but make sure that no two bordering countries are the same color.


Worksheet Activity: Graph Coloring 2

Color in the countries on this map with as few colors as possible, but make sure that no two bordering countries are the same color.

Worksheet Activity: Graph Coloring 3

Color in the countries on this map with as few colors as possible, but make sure that no two bordering countries are the same color.

Worksheet Activity: Graph Coloring 4

Color in the countries on this map with as few colors as possible, but make sure that no two bordering countries are the same color.


Variations and Extensions

There is a simple way to construct maps that require only two colors, as shown here. This map was drawn by overlaying closed curves (lines whose beginning joins up with their end). You can draw any number of these curves, of any shape, on top of each other, and you will always end up with a map that can be colored with two colors. Students can experiment with creating this type of map.

Four colors are always enough to color a map drawn on a sheet of paper or on a sphere (that is, a globe). One might wonder (as scientists are paid to do) how many colors are needed for maps drawn on weirder surfaces, such as the torus (the shape of a donut). In this case, one might need five colors, and five is always enough. Students might like to experiment with this.

There are many other entertaining variations on the map-coloring problem that lead off into directions where much is currently unknown. For example, if I am coloring a map on a sheet of paper by myself, then I know that if I work cleverly, four colors will be enough. But suppose that instead of working alone I am working with an incompetent (or even adversarial) partner, and we take turns at choosing the color for countries. Assume that I work cleverly, while my partner only works “legally” as we take turns coloring countries on the map. How many crayons need to be on the table in order for me in my cleverness to be able to make up for my partner's legal but not very bright (or even subversive) moves? The maximum number isn’t known! In 1992 it was proved that 33 crayons will always be enough, and in 2008 this was improved by a proof that 17 would be sufficient, but we still don't know that this many is ever actually required. (Experts conjecture that fewer than 10 colors are sufficient.) Students might enjoy acting out this situation, which can be played as a two-person game where you try to maximise the number of colours that your opponent needs.

In another variation of map coloring know as empire coloring, we start with two different maps on two sheets of paper having the same number of countries. Each country on one of the maps (say, the Earth) is paired with exactly one country on the other map (which might be colonies on the Moon). In addition to the usual coloring requirement of different colors for countries that share a border (for both maps) we add the requirement that each Earth country must be colored the same as its colony on the Moon. How many colors do we need for this problem? The answer is currently unknown.


What’s it all about?

The map coloring problem that we have explored in this activity is essentially to find the minimum number of colors—two, three, or four—that are necessary to color a particular map. The conjecture that any map can be colored using only four colors was formulated in 1852, but it was not proved until 1976. Computer science is full of unsolved problems, and knowing that the four-color theorem was proved after more than 120 years of attention from researchers is an encouragement to those working on other problems whose solution has eluded them for decades.

Map coloring belongs to a general class of problems known as “graph coloring.” In computer science, a graph is an abstract representation of relationships, as shown here.

As mentioned in Activity 9 on the Muddy City, the term graph is used in a different sense in mathematics to mean a chart displaying numerical data, such as a bar graph, but the graphs that computer scientists use are not related to these. In computer science, graphs are drawn using circles or large dots, technically called “nodes,” to denote objects, with lines between them to indicate some sort of relationship between the objects. The above graph happens to represent the map at the beginning of this activity. The nodes represent the countries, and a line between two nodes indicates that those two countries share a common border. On the graph, the coloring rule is that no connected nodes should be allocated the same color. Unlike a map, there is no limit to the number of colors that a general graph may require, because many different constraints may be drawn in as connecting lines, whereas the two-dimensional nature of maps restricts the possible arrangements. The “graph coloring problem” is to find the minimum number of colors that are needed for a particular graph.

In the graph on the right the nodes correspond to subjects in a school. A line between two subjects indicates that at least one student is taking both subjects, and so they should not be timetabled for the same period. Using this representation, the problem of finding a workable timetable using the minimum number of periods is equivalent to the coloring problem, where the different colors correspond to different periods. Graph coloring algorithms are of great interest in computer science, and are used for many real-world problems, although they are probably never used to color in maps!—our poor cartographer is just a fiction.

There are literally thousands of other problems based on graphs. Some are described elsewhere in this book, such as the minimal spanning tree of Activity 9 and the dominating sets of Activity 14. Graphs are a very general way of representing data and can be used to represent all sorts of situations, such as a map made up of roads and intersections, connections between atoms in a molecule, paths that messages can take through a computer network, connections between components on a printed circuit board, and relationships between the tasks required to carry out a large project. For this reason, problems involving graph representations have long fascinated computer scientists.

Many of these problems are very difficult—not difficult conceptually, but difficult because they take a long time to solve. For example, to determine the most efficient solution for a graph coloring problem of moderate size—such as finding the best way to timetable a school with thirty teachers and 800 students—could take years, even centuries, for a computer using the best known algorithm. The problem would be irrelevant by the time the solution was found—and that’s assuming the computer doesn't break down or wear out before it finishes! Such problems are only solved in practice because we are content to work with sub-optimal, but still very good, solutions. If we were to insist on being able to guarantee that the solution found was the very best one, the problem would be completely intractable.

The amount of computer time needed to solve coloring problems increases exponentially with the size of the graph. Consider the map coloring problem. It can be solved by trying out all possible ways to color the map. We know that at most four colors are required, so we need to evaluate every combination of assigning the four colors to the countries. If there are n countries, there are 4n combinations. This number grows very rapidly: every country that is added multiplies the number of combinations by four, and hence quadruples the solution time. Even if a computer were invented that could solve the problem for, say, fifty countries in just one hour, adding one more country would require four hours, and we would only need to add ten more countries to make the computer take over a year to find the solution. This kind of problem won't go away just because we keep inventing faster and faster computers!

Graph coloring is a good example of a problem whose solution time grows exponentially. For very simple instances of the problem, such as the small maps used in this activity, it is quite easy to find the optimal solution, but as soon as the number of countries increases beyond about ten, the problem becomes very difficult to do by hand, and with a hundred or more countries, even a computer can take many years to try out all the possible ways of coloring the map in order to choose the optimal one.

Many real-life problems are like this, but must be solved anyway. Computer scientists use methods that give good, but not perfect, answers. These heuristic techniques are often very close to optimal, very fast to compute, and give answers that are close enough for all practical purposes. Schools can tolerate using one more classroom than would be needed if the timetable were perfect, and perhaps the poor cartographer could afford an extra color even though it is not strictly necessary.

No-one has proved that there isn't an efficient way to solve this sort of problem on conventional computers, but neither has anyone proved that there is, and computer scientists are sceptical that an efficient method will ever be found. We will learn more about this kind of problem in the next two activities.


Further reading

Harel discusses the four-color theorem, including its history, in Algorithmics. More aspects of the map-coloring problem are discussed in This is MEGA-Mathematics! by Casey and Fellows. Kubale’s 2004 book, Graph Colorings, includes a history of the problem. There are many websites that cover this topic.

Solutions and hints

This is the only possible solution for the map on worksheet 1 (of course, the choice of colors is up to the student, but only two different colors are required).



The map at the top of worksheet 2 can be colored correctly using three colors, while the one at the bottom requires four. Here are two possible solutions.



The map on worksheet 3 is a simpler three-color map, with a possible solution shown here.



Solution for worksheet 4 using just two colors (shaded and white).



Activity 14

Tourist town—Dominating sets


Summary

Many real-life situations can be abstracted into the form of a network or “graph” of the kind used for coloring in Activity 13. Networks present many opportunities for the development of algorithms that are practically useful. In this activity, we want to mark some of the junctions, or “nodes,” in such a way that all other nodes are at most one step away from one of the marked ones. The question is, how few marked nodes can we get away with? This turns out to be a surprisingly difficult problem.

Curriculum Links

  • Mathematics Level 2: Position and orientation
Skills

  • Maps.

  • Relationships.

  • Puzzle solving.

  • Iterative goal seeking.
Ages

  • 7 and up
Materials

Each group of students will need:

  • a copy of the blackline master Ice Cream Vans, and

  • several counters or poker chips of two different colors.

You will need



  • an projector image of the blackline master Ice Cream Vans Solution on a whiteboard, or a whiteboard to draw it on.

D
ominating Sets

Introduction

The Ice Cream Vans worksheet shows a map of Tourist Town. The lines are streets and the dots are street corners. The town lies in a very hot country, and in the summer season ice-cream vans park at street corners and sell ice-creams to tourists. We want to place the vans so that anyone can reach one by walking to the end of their street and then at most one block further. (It may be easier to imagine people living at the intersections rather than along the streets; then they must be able to get ice-cream by walking at most one block.) The question is, how many vans are needed and on which intersections should they be placed?
Discussion

  1. Divide the students into small groups, give each group the Tourist Town map and some counters, and explain the story.
  2. Show the students how to place a counter on an intersection to mark an ice-cream van, and then place counters of another color on the intersections one street away. People living at those intersections (or along the streets that come into them) are served by this ice-cream van.


  3. Have the students experiment with different positions for the vans. As they find configurations that serve all houses, remind them that vans are expensive and the idea is to have as few of them as possible. It is obvious that the conditions can be met if there are enough vans to place on all intersections—the interesting question is how f
    ew you can get away with.

  4. The minimum number of vans for Tourist Town is six, and a solution is shown here. But it is very difficult to find this solution! After some time, tell the class that six vans suffice and challenge them to find a way to place them. This is still quite a hard problem: many groups will eventually give up. Even a solution using eight or nine vans can be difficult to find.

  5. The map of Tourist Town was made by starting with the six map pieces at the bottom of the Ice Cream Vans solution worksheet, each of which obviously requires only one ice-cream van, and connecting them together with lots of streets to disguise the solution. The main thing is not to put any links between the solution intersections (the open dots), but only between the extra ones (the solid dots). Show the class this technique on the board or using a projector.

  6. Get the students to make their own difficult maps using this strategy. They may wish to try them on their friends and parents–they will find that they can create puzzles that they can solve but others can’t! These are examples of what is called a “one-way function”: it's easy to come up with a puzzle that is very difficult to solve—unless you’re the one who created it in the first place. One-way functions play a crucial role in cryptography (see Activities 17 and 18).

Worksheet Activity: Ice Cream Vans

Work out how to place ice-cream vans on the street intersections so that every other intersection is connected to one that has a van on it.


Worksheet Activity: Ice Cream Vans Solution

Display this to the class to show how the puzzle was constructed.





Variations and extensions

There are all sorts of situations in which one might be faced with this kind of problem in town planning: locating mailboxes, wells, fire-stations, and so on. And in real life, the map won’t be based on a trick that makes it easy to solve. If you really have to solve a problem like this, how would you do it?

There is a very straightforward way: consider all possible ways of placing ice-cream vans and check them to see which is best. With the 26 street corners in Tourist Town, there are 26 ways of placing one van. It's easy to check all 26 possibilities, and it’s obvious that none of them satisfies the desired condition. With two vans, there are 26 places to put the first, and, whichever one is chosen for the first, there are 25 places left to put the second (obviously you wouldn’t put both vans at the same intersection): 26 × 25 = 650 possibilities to check. Again, each check is easy, although it would be very tedious to do them all. Actually, you only need to check half of them (325), since it doesn’t matter which van is which: if you’ve checked van 1 at intersection A and van 2 at intersection B then there’s no need to check van 1 at B and van 2 at A. You could carry on checking three vans (2600 possibilities), four vans (14950 possibilities), and so on. Clearly, 26 vans are enough since there are only 26 intersections and there’s no point in having more than one van at the same place. Another way of assessing the number of possibilities is to consider the total number of configurations with 26 intersections and any number of vans. Since there are two possibilities for each street corner—it may or may not have a van—the number of configurations is 226, which is 67,108,864.

This way of solving the problem is called a “brute-force” algorithm, and it takes a long time. It’s a widely held misconception that computers are so fast they can solve just about any problem quickly, no matter how much work it involves. But that’s not true. Just how long the brute-force algorithm takes depends on how quick it is to check whether a particular configuration is a solution. To check this involves testing every intersection to find the distance of the nearest van. Suppose that an entire configuration can be tested in one second. How long does it take to test all 226 possibilities for Tourist Town? (Answer: 226 is about 67 million; there are 86,400 seconds in a day, so 226 seconds is about 777 days, or around two years.) And suppose that instead of one second, it took just one thousandth of a second to check each particular configuration. Then the same two years would allow the computer to solve a 36-intersection town, because 236 is about 1000 times 226. Even if the computer was a million times faster, so that one million configurations could be checked every second, then it would take two years to work on a 46-intersection town. And these are not very big towns! (How many intersections are there in your town?)

Since the brute-force algorithm is so slow, are there other ways to solve the problem? Well, we could try the greedy approach that was so successful in the muddy city (Activity 9). We need to think how to be greedy with ice-creams—I mean how to apply the greedy approach to the ice-cream van problem. The way to do it is by placing the first van at the intersection that connects the greatest number of streets, the second one at the next most connected intersection, and so on. However, this doesn’t necessarily produce a minimum set of ice-cream van positions—in fact, the most highly connected intersection in Tourist Town, which has five streets, isn’t a good place to put a van (check this with the class).

Let’s look at an easier problem. Instead of being asked to find a minimum configuration, suppose you were given a configuration and asked whether it was minimal or not. In some cases, this is easy. For example, this diagram shows a much simpler map whose solution is quite straightforward. If you imagine the streets as edges of a cube, it’s clear that two ice-cream vans at diagonally opposite cube vertices are sufficient. Moreover, you should be able to convince yourself that it is not possible to solve the problem with fewer than two vans. It is much harder—though not impossible—to convince oneself that Tourist Town cannot be serviced by less than six vans. For general maps it is extremely hard to prove that a certain configuration of ice-cream vans is a minimal one.

What’s it all about?

One of the interesting things about the ice-cream problem is that no-one knows whether there is an algorithm for finding a minimum set of locations that is significantly faster than the brute-force method! The time taken by the brute-force method grows exponentially with the number of intersections—it is called an exponential-time algorithm. A polynomial-time algorithm is one whose running time grows with the square, or the cube, or the seventeenth power, or any other power, of the number of intersections. A polynomial-time algorithm will always be faster for sufficiently large maps—even (say) a seventeenth-power algorithm—since an exponentially-growing function outweighs any polynomially-growing one once its argument becomes large enough. (For example, if you work it out, whenever n is bigger than 117 then n17 is smaller than 2n). Is there a polynomial-time algorithm for finding the minimum set of locations?—no-one knows, although people have tried very hard to find one. And the same is true for the seemingly easier task of checking whether a particular set of locations is minimal: the brute-force algorithm of trying all possibilities for smaller sets of locations is exponential in the number of intersections, and polynomial-time algorithms have neither been discovered nor proved not to exist.

Does this remind you of map coloring (Activity 13)? It should. The ice-cream van question, which is officially called the “minimum dominating set” problem, is one of a large number—thousands—of problems for which it is not known whether polynomial-time algorithms exist, in domains ranging from logic, through jigsaw-like arrangement problems to map coloring, finding optimal routes on maps, and scheduling processes. Astonishingly, all of these problems have been shown to be equivalent in the sense that if a polynomial-time algorithm is found for one of them, it can be converted into a polynomial-time algorithm for all the others—you might say that they stand or fall together.

These problems are called NP-complete. NP stands for “non-deterministic polynomial.” This jargon means that the problem could be solved in a reasonable amount of time if you had a computer that could try out an arbitrarily large number of solutions at once (that’s the non-deterministic part). You may think this is a pretty unrealistic assumption, and indeed it is. It’s not possible to build this kind of computer, since it would have to be arbitrarily large! However, the concept of such a machine is important in principle, because it appears that NP-complete problems cannot be solved in a reasonable amount of time without a non-deterministic computer.

Furthermore, this group of problems is called complete because although the problems seem very different—for example, map-coloring is very different from placing ice-cream vans—it turns out that if an efficient way of solving one of them is found, then that method can be adapted to solve any of the problems. That’s what we meant by “standing or falling together.”

There are thousands of NP-complete problems, and researchers have been attacking them, looking for efficient solutions, for several decades without success. If an efficient solution had been discovered for just one of them, then we would have efficient solutions for them all. For this reason, it is strongly suspected that there is no efficient solution. But proving that the problems necessarily take exponential time is the most outstanding open question in theoretical computer science—possibly in all of mathematics—today.

Further reading

Harel’s book Algorithmics introduces several NP-complete problems and discusses the question of whether polynomial-time algorithms exist. Dewdney’s Turing Omnibus also discusses NP-completeness. The standard computer science text on the subject is Garey & Johnson’s Computers and Intractability, which introduces several hundred NP-complete problems along with techniques for proving NP-completeness. However, it is fairly heavy going and is really only suitable for the computer science specialist.

Activity 15

Ice roads —Steiner trees


Summary

Sometimes a small, seemingly insignificant, variation in the specification of a problem makes a huge difference in how hard it is to solve. This activity, like the Muddy City problem (Activity 9), is about finding short paths through networks. The difference is that here we are allowed to introduce new points into the network if that reduces the path length. The result is a far more difficult problem that is not related to the Muddy City, but is algorithmically equivalent to the cartographer’s puzzle (Activity 13) and Tourist Town (Activity 14).
Skills

  • Spatial visualization.

  • Geometric reasoning.

  • Algorithmic procedures and complexity.
Ages

  • 7 and up
Materials

Each group of students will need

  • five or six pegs to place in the ground (tent pegs are good, although a coat hanger cut into pieces which are then bent over is fine),

  • several meters of string or elastic,

  • a ruler or tape measure, and

  • pen and paper to make notes on.

Ice Roads

Introduction

The previous activity, Tourist Town, took place in a very hot country; this one is just the opposite. In the frozen north of Canada (so the story goes), in the winter on the huge frozen lakes, snowplows make roads to connect up drill sites so that crews can visit each other. Out there in the cold they want to do a minimum of road building, and your job is to figure out where to make the roads. There are no constraints: highways can go anywhere on the snow—the lakes are frozen and covered. It’s all flat.

The roads should obviously travel in straight stretches, since introducing bends would only increase the length unnecessarily. But it’s not as simple as connecting all the sites with straight lines, because adding intersections out in the frozen wastes can sometimes reduce the total road length—and it’s total length that’s important, not travel time from one site to another.



In this figure, (a) shows three drill sites. Connecting one of them to each of the others (as in (b)) would make an acceptable road network. Another possibility is to make an intersection somewhere near the center of the triangle and connect it to the three sites (c). And if you measure the total amount of road that has been cleared, this is indeed a better solution. The extra intersection is called a “Steiner” point after the Swiss mathematician Jacob Steiner (1796–1863), who stated the problem and was the first to notice that the total length can be reduced by introducing new points. You could think of a Steiner point as a new, fictitious, drill site.


Discussion
  1. Describe the problem that the students will be working on. Using the example above, demonstrate to the students that with three sites, adding a new one sometimes improves the solution by reducing the amount of road-building.




  1. The students will be using four points arranged in a square, as illustrated in (a). Go outside and get each group to place four pegs in the grass in a square about 1 meter by 1 meter.

  2. Get the students to experiment with connecting the pegs with string or elastic, measuring and recording the minimum total length required. At this stage they should not use any Steiner points. (The minimum is achieved by connecting three sides of the square, as in (b), and the total length is 3 meters.)

  3. Now see if the students can do better by using one Steiner point. (The best place is in the center of the square, (c). Then the total length is 2√2 = 2.83 meters.) Suggest that they might do even better using two Steiner points. (Indeed they can, by placing the two points as in (d), forming 120 degree angles between the incoming roads. The total length is then 1 + √3 = 2.73 meters.)

  4. Can the students do better with three Steiner points? (No – two points are best, and no advantage is gained by using more.)

  5. Discuss with the students why these problems seem hard. (It’s because you don’t know where to put the Steiner points, and there are lots of possibilities to try out.)

Worksheet Activity: Steiner Tree Example 1

Find a way of linking these drill sites with the shortest possible ice roads.



Worksheet Activity: Steiner Tree Example 2

Find a way of linking these drill sites with the shortest possible ice roads.

Variations and extensions

  1. An interesting experiment for groups that finish the original activity early is to work with a rectangle about 1 meter by 2 meters (a). The students will find that adding one Steiner point makes things worse, but two give an improved solution. (The lengths are 4 meters for (b), 2√5 = 4.47 meters for (c), and 2 + √3 = 3.73 meters for (d).) See if they can figure out why the one-point configuration does so much worse for rectangles than for squares. (It’s because when the square is stretched into a rectangle, the amount of stretch gets added just once into (b) and (d), but both diagonals increase in (c).)


  2. Minimal Steiner tree for the first example


    Older students can work on a larger problem. Two layouts of sites to connect with ice roads are given in the worksheets. They can experiment with different solutions either using new copies of the worksheet, or by writing with removable pen on a transparency over the top of the sheet. Alternatively, the maps can be marked out on the ground using pegs. They can let the class know when they think they’ve set a new record for the shortest distance. (The figures on the right show the minimal solution for the first example and two possible solutions for the second, whose total
    Two possible Steiner trees for the second example

    length is quite similar.) The fact that there are two such similar solutions illustrates why these kinds of problem are so hard—there are so many choices about where to put the Steiner points!





  1. Ladder networks like this provide another way to extend the problem.

Some minimal Steiner trees for ladder networks are shown here.

The one for a two-rung ladder is just the same as for a square. However, for a three-rung ladder the solution is quite different—as you will discover if you try to draw it out again from memory! The solution for four rungs is like that for two two-rung ladders joined together, whereas for five rungs it is more like an extension of the three-rung solution. In general, the shape of the minimal Steiner tree for a ladder depends on whether it has an even or odd number of rungs. If it is even, it is as though several two-rung ladders were joined together. Otherwise, it's like a repetition of the three-rung solution. But proving these things rigorously is not easy.



  1. Another interesting activity is to construct soap-bubble models of Steiner trees. You can do this by taking two sheets of rigid transparent plastic and inserting pins between them to represent the sites to be spanned, as shown here.

Now dip the whole thing into a soap solution. When it comes out, you will find that a film of soap connects the pins in a beautiful Steiner-tree network.

Unfortunately, however, it isn't necessarily a minimal Steiner tree. The soap film does find a configuration that minimizes the total length, but the minimum is only a local one, not necessarily a global one. There may be completely different ways of placing the Steiner points to give a smaller total length. For example, you can imagine the soap film looking like the first configuration in Extension 2 when it is withdrawn from the liquid on one occasion, and the second configuration on another.

What’s it all about?

The networks that we’ve been working on are minimal Steiner trees. They’re called “trees” because they have no cycles, just as the branches on a real tree grow apart but do not (normally) rejoin and grow together again. They’re called “Steiner” trees because new points, Steiner points, can be added to the original sites that the trees connect. And they’re called “minimal” because they have the shortest length of any tree connecting those sites. In the Muddy City (Activity 9) we learned that a network connecting a number of sites that minimizes the total length is called a minimal spanning tree: Steiner trees are just the same except that new points can be introduced.

It’s interesting that while there is a very efficient algorithm for finding minimal spanning trees (Activity 14)—a greedy one that works by repeatedly connecting the two closest so-far-unconnected points—there is no general efficient solution to the minimal Steiner problem. Steiner trees are much harder because you have to decide where to put the extra points. In fact, rather surprisingly, the difficult part of the Steiner tree problem is not in determining the precise location of the Steiner points, but in deciding roughly where to put them: the difference between the two solutions to Example 2, for example. Once you know what regions to put the new points in, fine-tuning them to the optimum position is relatively simple. Soap films do that very effectively, and so can computers.

Finding minimal Steiner trees is part of a story that involved saving big money in the telephone business. Before 1967, when corporate customers in the US operated large private telephone networks, they leased the lines from a telephone company. The amount they are billed is not calculated on the basis of how the wires are actually used, but on the basis of the shortest network that would suffice. The reasoning is that the customer shouldn’t have to pay extra just because the telephone company uses a round-about route. Originally, the algorithm that calculated how much to charge worked by determining the minimal spanning tree. However, around 1967 it was noticed by a customer—an airline, in fact, with three major hubs—that if they requested a fourth hub at an intermediate point then the total length of the network would be reduced. The telephone company was forced to reduce charges to what they would have been if there was a telephone exchange at the Steiner point! Although, for typical configurations, the minimal Steiner tree is only 5% or 10% shorter than the minimal spanning tree, this can be a worthwhile saving when large amounts of money are involved. The Steiner tree problem is sometimes called the “shortest network problem” because it involves finding the shortest network that connects a set of sites.

If you have tackled the two preceding activities, the cartographer’s puzzle and tourist town, you will not be surprised to hear that the minimal Steiner tree problem is NP-complete. As the number of sites increases, so does the number of possible locations for Steiner points, and trying all possibilities involves an exponentially-growing search. This is another of the thousands of problems for which it simply isn’t known whether exponential search is the best that can be done, or whether there is an as-yet-undiscovered polynomial-time algorithm. What is known, however, is that if a polynomial-time algorithm is found for this problem, it can be turned into a polynomial-time algorithm for graph coloring, for finding minimal dominating sets—and for all the other problems in the NP-complete class.

We explained at the end of the previous activity that the “NP” in NP-complete stands for “non-deterministic polynomial,” and “complete” refers to the fact that if a polynomial-time algorithm is found for one of the NP-complete problems it can be turned into polynomial-time algorithms for all the others. The set of problems that are solvable in polynomial time is called P. So the crucial question is, do polynomial-time algorithms exist for NP-complete problems—in other words, is P = NP? The answer to this question is not known, and it is one of the great mysteries of modern computer science.

Problems for which polynomial-time algorithms exist—even though these algorithms might be quite slow—are called “tractable.” Problems for which they do not are called “intractable,” because no matter how fast your computer, or how many computers you use together, a small increase in problem size will mean that they can’t possibly be solved in practice. It is not known whether the NP-complete problems—which include the cartographer’s puzzle, tourist town, and ice roads—are tractable or not. But most computer scientists are pessimistic that a polynomial-time algorithm for NP-complete problems will ever be found, and so proving that a problem is NP-complete is regarded as strong evidence that the problem is inherently intractable.








“I can't find an efficient algorithm, I guess I'm just too dumb.”

“I can't find an efficient algorithm, because no such algorithm is possible.”

“I can't find an efficient algorithm, but neither can all these famous people.”

What to do when you can't find an efficient algorithm: three possibilities

What can you do when your boss asks you to devise an efficient algorithm that comes up with the optimal solution to a problem, and you can’t find one?—as surely happened when the airline hit upon the fact that network costs could be reduced by introducing Steiner points. If you could prove that there isn’t an efficient algorithm to come up with the optimal solution, that would be great. But it’s very difficult to prove negative results like this in computer science, for who knows what clever programmer might come along in the future and hit upon an obscure trick that solves the problem. So, unfortunately, you’re unlikely to be in a position to say categorically that no efficient algorithm is possible—that the problem is intractable. But if you can show that your problem is NP-complete, then it’s actually true that thousands of people in research laboratories have worked on problems that really are equivalent to yours, and also failed to come up with an efficient solution. That may not get you a bonus, but it’ll get you off the hook!

Of course, in real life these problems still need to be solved, and in that case people turn to heuristics – algorithms that don’t guarantee to give the best possible solution, but do give a solution within a very small percentage of the optimal. Heuristic algorithms can be very fast, and the wastage of not finding the best possible solution can be fairly small, so they are good enough to get on with the job. It’s just frustrating to know that there might be a slightly better timetable, or a slightly better layout of a network or roads.

Further reading

The cartoon is from Garey and Johnson's classic book Computers and Intractability.

The “Computer recreations” column of Scientific American, June 1984, contains a brief description of how to make Steiner trees using soap bubbles, along with interesting descriptions of other analog gadgets for problem solving, including a spaghetti computer for sorting, a cat's cradle of strings for finding shortest paths in a graph, and a light-and-mirrors device for telling whether or not a number is prime. These also appear in a section about analog computers in Dewdney's Turing Omnibus.

Part V




Share with your friends:
  1   2   3   4   5   6


The database is protected by copyright ©hestories.info 2019
send message

    Main page