Ice Roads - Steiner Trees
Sometimes a small, seemingly insignificant, variation in the specification of a problem makes a huge difference in how difficult it is to solve. This activity, like the The Muddy City problem, is about finding short paths through networks. However, this activity allows for the introduction of new points into the network if it will reduce 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 The Poor Cartographer and Tourist Town.
The resource begins with an introduction and a series of tasks followed by variations and extensions. The resource concludes with further information on Steiner trees and blank worksheets for use in the activities.
This collection of twenty activities from Computer Science Unplugged is designed to aid the teaching and learning of computer science through engaging games and puzzles using cards, string, crayons and lots of running around.
Show health and safety information
|Subject(s)||Computing, Algorithmic Thinking|
|Age||7-11, 11-14, 14-16|
|Published||2000 - 2009|
|Log in to rate this resource|
- Computer Science Unplugged