ALEX Classroom Resource

  

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.

Unpacked Content
Evidence Of Student Attainment:
Students will:
  • use flowcharts to create a plan or algorithm.
Teacher 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
DLIT (2018)
Grade: 4
21) Develop, test, and refine prototypes as part of a cyclical design process to solve a simple problem.

Unpacked Content
Evidence Of Student Attainment:
Students will:
  • solve a simple problem by developing a prototype.
  • solve a simple problem by testing a designed prototype.
  • solve a simple problem by refining a tested prototype.
Teacher 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
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.

Unpacked Content
Evidence Of Student Attainment:
Students will:
  • create an algorithm to solve a problem.
  • detect and debug logical errors within an algorithm.
Teacher 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
DLIT (2018)
Grade: 5
3) Create an algorithm that is defined by simple pseudocode.

Unpacked Content
Evidence Of Student Attainment:
Students will:
  • create set of steps that is written in simple pseudocode.
Teacher 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
DLIT (2018)
Grade: 5
5) Develop and recommend solutions to a given problem and explain the process to an audience.

Unpacked Content
Evidence Of Student Attainment:
Students will:
  • develop and recommend solutions to a given problem.
  • explain the development process to an audience.
Teacher 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
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.

Unpacked Content
Evidence Of Student Attainment:
Students will:
  • develop prototypes as part of a cyclical design process to solve a complex problem.
  • test prototypes as part of a cyclical design process to solve a complex problem.
  • refine prototypes as part of a cyclical design process to solve a complex problem.
Teacher 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
DLIT (2018)
Grade: 7
5) Solve a complex problem using computational thinking.

Unpacked Content
Evidence Of Student Attainment:
Students will:
  • break a problem into parts or steps.
  • find patterns or trends.
  • create steps to solve the problem.
  • infer rules or principles associated with problem solving.
Teacher 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
DLIT (2018)
Grade: 7
30) Apply the problem-solving process to solve real-world problems.

Unpacked Content
Evidence Of Student Attainment:
Students will:
  • define a problem.
  • analyze the problem.
  • seek multiple solutions to the problem.
  • evaluate possible solutions to the problem.
  • select a best solution to the problem.
  • seek feedback on the solution.
Teacher 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.
Tags: algorithm, expression, minimal spanning trees, network, problem solving
License Type: Attribution Non-Commercial Share Alike
For full descriptions of license types and a guide to usage, visit :
https://creativecommons.org/licenses
Accessibility
Comments
  This resource provided by:  
Author: Aimee Bates
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.
Copyright © 2017, Alabama Learning Exchange
Alabama State Department of Education
Alabama State Department of Education