Minimal Spanning Trees | Computer Science Unplugged

PDFs

Can't find a translation? Check our projects page for status.

Networks are everywhere in modern society: roads, wires, water and gas pipes all connect one place to another. Computers are built of networks at many levels, from the microscopic connections between transistors in a chip to the cables and satellites that link the internet around the world. People who build networks often need to work out the most efficient way to make connections, which can be a difficult problem.

This puzzle shows students the decisions involved in linking a network between houses in a muddy city. It can lead on to a discussion of minimal spanning tree algorithms for optimizing networks.

Curriculum Links

Great Principles of Computer Science

Computation
Coordination

ACM K12 Curriculum

Level I (Grades 35) Topic 11: develop a simple understanding of an algorithm

New Zealand Curriculum

Mathematics Level 1: Position and Orientation
Give and follow instructions for movement that involve distances, directions, and half or quarter turns
Mathematics Level 2: Position and orientation
Create and use simple maps to show position and direction.
Technology Level 1: Planning for Practice
Outline a general plan to support the development of an outcome, identifying appropriate steps and resources

Extension

Mordechai (Moti) Ben-Ari from the Weizmann Institute of Science, Israel has programmed The Muddy City Minimal Spanning Trees Unplugged activity in Scratch which can be downloaded in a zip file of the complete set of activities . Please read the ReadMe.txt for documentation.
Blaine Booher from the University of Cincinnati has a variation on the Minimal Spanning Trees activity called Internet Routing where students learn a brief overview of the history of the internet and its impact on society. Students work to understand internet routing and how all of the computers on the internet are interconnected by using the analogy of roads in a town. This activity was developed for high school students.
NCTM Illuminations has an activity called Road Trip! to find the shortest path to save expenses that investigates three different methods to determine the shortest route: the Nearest Neighbour method, the Cheapest Link method, and the Brute Force method.
As another extension, try the online games from Wiliam Cook to demonstrate the Travelling Salesman Problem(TSP) below:
- TSP: 1 Player Game
- TSP: 2 Player Game

Other Resources

An older version of this activity can be downloaded in PDF format here. The content is similar to the current version, but there's some extra technical information.
Wikipedia: Spanning Tree.
See also Wikipedia: Travelling Salesman Problem : Given a list of cities and their pairwise distances, the task is to find a shortest possible tour that visits each city exactly once.
The Mathmaniacs web site has a similar activity (lesson 13)