## Minimal Spanning Trees

Classroom Resource Information

Title:

Minimal Spanning Trees

URL:

https://classic.csunplugged.org/minimal-spanning-trees/

Content Source:

Other
CS Unplugged
Type: Learning Activity

Overview:

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 to a discussion of minimal spanning tree algorithms for optimizing networks.

Content Standard(s):
 Digital Literacy and Computer Science DLIT (2018) Grade: 4 5) Use flowcharts to create a plan or algorithm. Digital Literacy and Computer Science DLIT (2018) Grade: 4 21) Develop, test, and refine prototypes as part of a cyclical design process to solve a simple problem. Digital Literacy and Computer Science DLIT (2018) Grade: 5 2) Create an algorithm to solve a problem while detecting and debugging logical errors within the algorithm. Examples: Program the movement of a character, robot, or person through a maze. Define a variable that can be changed or updated. Digital Literacy and Computer Science DLIT (2018) Grade: 5 3) Create an algorithm that is defined by simple pseudocode. Digital Literacy and Computer Science DLIT (2018) Grade: 5 5) Develop and recommend solutions to a given problem and explain the process to an audience. Digital Literacy and Computer Science DLIT (2018) Grade: 5 28) Develop, test, and refine prototypes as part of a cyclical design process to solve a complex problem. Examples: Design backpack for a specific user's needs; design a method to collect and transport water without the benefit of faucets; design boats that need to hold as much payload as possible before sinking; design models of chairs based on specific user needs. Digital Literacy and Computer Science DLIT (2018) Grade: 7 5) Solve a complex problem using computational thinking. Digital Literacy and Computer Science DLIT (2018) Grade: 7 30) Apply the problem-solving process to solve real-world problems.
Tags: algorithm, expression, minimal spanning trees, network, problem solving