Minimal Spanning Trees

Learning Resource Type

Classroom Resource

Subject Area

Digital Literacy and Computer Science

Grade(s)

4, 5, 7

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.

Digital Literacy and Computer Science (2018) Grade(s): 4

DLCS18.4.5

Use flowcharts to create a plan or algorithm.

UP:DLCS18.4.5

Vocabulary

  • flowchart
  • plan
  • algorithm

Knowledge

Students know:
  • flowcharts are used in creating plan or algorithm.
  • strategies to use flowcharts to create a plan or algorithm.

Skills

Students are able to:
  • use flowcharts to create a plan or algorithm.
  • explain how flowcharts help in creating a plan or algorithm.

Understanding

Students understand that:
  • flowcharts are used in creating plan or algorithm.
  • flowcharts help to visualize a plan or algorithm.
Digital Literacy and Computer Science (2018) Grade(s): 4

DLCS18.4.21

Develop, test, and refine prototypes as part of a cyclical design process to solve a simple problem.

UP:DLCS18.4.21

Vocabulary

  • develop
  • test
  • refine
  • prototypes
  • cyclical design process

Knowledge

Students know:
  • strategies to brainstorm and develop prototypes as part of a cyclical design process to solve a simple problem.
  • strategies to test prototypes as part of a cyclical design process to solve a simple problem.
  • strategies to refine prototypes as part of a cyclical design process to solve a simple problem.

Skills

Students are able to:
  • develop, test, and refine prototypes as part of a cyclical design process to solve a simple problem.

Understanding

Students understand that:
  • some problems can be solved by developing prototypes.
Digital Literacy and Computer Science (2018) Grade(s): 5

DLCS18.5.2

Create an algorithm to solve a problem while detecting and debugging logical errors within the algorithm.

UP:DLCS18.5.2

Vocabulary

  • algorithm
  • debug
  • detect
  • logical errors

Knowledge

Students know:
  • an algorithm is a logical set of steps to solve a problem.
  • detecting and debugging logical errors within an algorithm will ensure the algorithm serves to solve a problem successfully.

Skills

Students are able to:
  • create an algorithm to solve a problem while detecting and debugging logical errors within the algorithm.

Understanding

Students understand that:
  • debugging an algorithm is searching for logical errors within the algorithm.
  • an algorithm is a set of steps to solve a problem.
  • how to create an algorithm to solve a problem while detecting and debugging logical errors within the algorithm.
Digital Literacy and Computer Science (2018) Grade(s): 5

DLCS18.5.3

Create an algorithm that is defined by simple pseudocode.

UP:DLCS18.5.3

Vocabulary

  • algorithm
  • pseudocode

Knowledge

Students know:
  • simple pseudocode resembles language used to communicate with computers.

Skills

Students are able to:
  • create an algorithm that is written in simple pseudocode.

Understanding

Students understand that:
  • an algorithm that is written in simple pseudocode is similar to an algorithm written using a programming language.
Digital Literacy and Computer Science (2018) Grade(s): 5

DLCS18.5.5

Develop and recommend solutions to a given problem and explain the process to an audience.

UP:DLCS18.5.5

Vocabulary

  • process

Knowledge

Students know:
  • steps of the problem-solving process.
  • many solutions exist to solve a problem.

Skills

Students are able to:
  • develop and recommend solutions to a given problem.
  • share their process with others.

Understanding

Students understand that:
  • problems can have multiple solutions.
Digital Literacy and Computer Science (2018) Grade(s): 5

DLCS18.5.28

Develop, test, and refine prototypes as part of a cyclical design process to solve a complex problem.

UP:DLCS18.5.28

Vocabulary

  • develop
  • test
  • refine
  • prototypes
  • cyclical design process

Knowledge

Students know:
  • how to use the design process to solve a complex problem.
  • strategies for creating a prototype as part of a cyclical design to solve a problem.
  • strategies for testing and refining prototypes as part of a cyclical design process to solve a complex problem.
  • characteristics of a cyclical design process.

Skills

Students are able to:
  • develop, test, and refine prototypes as part of a cyclical design process to solve a complex problem.

Understanding

Students understand that:
  • developing, testing, and refining are necessary steps in creating an effective prototype.
Digital Literacy and Computer Science (2018) Grade(s): 7

DLCS18.7.5

Solve a complex problem using computational thinking.

UP:DLCS18.7.5

Vocabulary

  • computational thinking

Knowledge

Students know:
  • smaller tasks are easier to solve than complex problems.
  • that trends in data can also speed up the problem-solving process.

Skills

Students are able to:
  • abstract portions of the problem and focus on smaller tasks to aid in solving a complex problem.

Understanding

Students understand that:
  • complex problems can be overwhelming.
  • by decomposing the complex problem into simpler problems, a solution is easier to reach.
Digital Literacy and Computer Science (2018) Grade(s): 7

DLCS18.7.30

Apply the problem-solving process to solve real-world problems.

UP:DLCS18.7.30

Vocabulary

  • problem-solving process

Knowledge

Students know:
  • the steps to the problem-solving process.

Skills

Students are able to:
  • select and dissect a problem.
  • seek solutions.
  • select a best alternative.

Understanding

Students understand that:
  • often there are multiple solutions to real
  • world problems.

CR Resource Type

Learning Activity

Resource Provider

CS Unplugged

License Type

Attribution Non-Commercial Share Alike
https://classic.csunplugged.org/minimal-spanning-trees/

Approved Date

ALSDE LOGO

This site may contain links to other websites or content belonging to or originating from third parties or links to websites and features in banners or other advertising. Such external links are not investigated, monitored, or checked for accuracy, adequacy, validity, reliability, availability, or completeness by us. WE DO NOT WARRANT, ENDORSE, GUARANTEE, OR ASSUME RESPONSIBILITY FOR THE ACCURACY OR RELIABILITY OF ANY INFORMATION OFFERED BY THIRD-PARTY WEBSITES LINKED THROUGH THIS SITE.
Alabama Learning Exchange © 2002-2023 by Alabama State Department of Education is licensed under Attribution-NonCommercial-ShareAlike 4.0 International

Design by Adaptive Theme