Unit1
Ch. 1
1
2
3
4
5
6
7
Ch. 2
8
9
10
11
12
13
14

Optional Lesson: Algorithms Detour - Minimum Spanning Tree

Overview

In this and the subsequent lesson, we consider some of the strategies used to construct networks and find paths for data in them. While this has a connection to ideas about the Internet, the focus of these lessons is on algorithms, formal techniques, and processes for solving problems. Students will explore and solve the Minimum Spanning Tree (MST) problem, first, in an unplugged fashion on paper. The real challenge is not in solving a particular instance of the minimum spanning tree, but to develop an algorithm, a clear series of steps, that if followed properly, will solve any instance of the problem. There is a possible misconception to look out for: the MST has a definite, verifiable optimal solution, as opposed to the Text Compression problem (from Unit 1), which does not.

Purpose

The MST is a problem in a field of study known as Graph Theory in mathematics and computer science. Problems involving graphs come up a lot in computer science, not only related to networking problems, but also in describing more sophisticated or interconnected relationships between data and information, for example, complicated scheduling problems, logistics, or even sociology problems, or interactions between molecules. Many real-world problems can be expressed or visualized as graphs.

The MST problem is interesting because it has an optimal best solution, and the algorithm for finding the MST on a graph is relatively straightforward to understand. The interesting thing about the MST is that a graph might have multiple “best” solutions, and there are several different algorithms for finding them.

Agenda

Getting Started

Extended Learning

Activity

Wrap-up

Assessment

View on Code Studio

Objectives

Students will be able to:

  • Write an algorithm for solving the minimum spanning tree (MST) problem.
  • Use the terms algorithm, graph, node, edge correctly.
  • Identify the minimum spanning tree on a given graph.
  • Explain the benefits of developing an algorithm for solving a problem versus solving an instance of a problem.

Preparation

  • Copies of Activity Guide

Links

Heads Up! Please make a copy of any documents you plan to share with students.

For the Teachers

For the Students

Support

Lesson Forum

Unit 1 Online Professional Learning Course

Report a Bug

Differentiation and other adjustments to this lesson

Teaching Guide

Getting Started

How much do you think the Internet costs to build and maintain?

Present this diagram on the board or projector.

Let’s say that you are in charge of not one router, but several, and your job is to connect them so that a) any packet can get from any router to any other router in your system, and b) you want to build these connections as cheaply as possible.

Say you are in charge of 4 routers placed at various locations in a region. The diagram shows the possible connections that could be made between any pair of routers and the associated cost of building a connection between them (in millions of dollars).

Question: Which connections would you choose to build to keep the total cost down?

Let students work it out in pairs or individually and share solutions. (See Key: Lesson Plan Activities for solutions.)

Question: Can you come up with a clear strategy, or process, for finding the minimal-cost connections you need, not only for this network, but any network, especially if the network were bigger?

Why do we care about coming up with a strategy or process for solving this problem, rather than just finding an answer?

Extended Learning

  • You might check out some real pseudocode and a visualization of the minimum spanning tree in action on VisuAlgo.
    • Go here: http://visualgo.net/mst.html
    • From the list of algorithms, choose “Kruskal’s Algorithm.”
    • You can see some of the other algorithms for solving the MST problem as well.

Activity

Transition to Activity Guide.

The Activity Guide - Algorithms, Graphs and the MST Problem - Activity Guide

  • Provides some initial background reading that covers:
    • What are algorithms and why do we want them?
    • Defining terms for graph problems: Graph, Node, Edge, Cost, Cycle, Tree
    • Explaining the Minimum Spanning Tree problem
  • Gives a few examples of graphs to experiment with finding the MST
  • Asks students to write an algorithm, or series of steps, that would find the MST for any graph.

Teaching Tips

It’s common for students to struggle at first and give a strategy that is essentially a restatement of the problem. For example: “My strategy is to randomly try edges until I find the set that connects all the nodes with minimal cost.” Don’t let them do this. While it’s fine to choose edges at random, what’s missing from this strategy is how or why an edge is kept as part of the set or discarded.

Some questions that might help students get started or make progress:

  • How do you know when to stop? i.e. How do you know you’ve found the minimum?
  • Which edge should you start with?
  • Can you define a strategy for considering an edge, then either keeping it or discarding it?

It’s possible students might make the wrong connections between this and the Text Compression activity from Unit 1, which also asked them to write out a process for solving that problem.

The difference between the two is that the Text Compression problem actually has no known efficient way for finding the best or optimal solution. To know the best solution you’d have to produce every possible compression for a piece of text and see which one came out the best. The only algorithms that exist do a decent job of compressing the text but they are just heuristics.

The minimum spanning tree has a definite best solution. The algorithm will always find the optimal solution. The interesting part is that since it’s possible that in choosing the next edge you have to pick randomly from a set of choices that are equally good, it means that the MSTs produced by the same algorithm might be different trees but they will have the same total cost.

Wrap-up

Go over the answers and discuss (See Key: Lesson Plan Activities for solutions.)

Establish that the minimum spanning tree for the first graph on the worksheet had a total cost of 25, and there were two possible solutions to the minimum spanning tree.

If necessary, act out the algorithm, or ask students to act out the algorithm on the original graph, or a new one that they just make up. Discuss: Ask students to compare and contrast their strategies with the one above.
Was your algorithm clearly written and easy to understand? Were there two different algorithms that still solved the problem correctly?

Teaching Tips

Here is an informal proof of the algorithm we wrote above. Note: you do not need to go over this with students, but many students might want to know why this works.

1) First you need 9 edges to make a spanning tree. Think about any configuration of 10 nodes with no edges connecting them. Say they are all in line, or one in the middle with others surrounding it. You’d need a minimum of 9 edges to string them all together. If there are n nodes, you always need one less (n-1) to minimally connect them.

2) If you take all of the edge weights from the graph and line them up in order:

2 2 2 3 3 3 3 4 4 4 4 5 5 5 5 6 6

We know that we need 9 of these edges to connect the 10 nodes. So let’s look at the 9 edges that we chose as a result of the algorithm:

2 2 2 3 3 3 3 4 4 4 4 5 5 5 5 6 6

These are the 9 lowest possible values we could select out of the entire list except for a 3. Why not one of those 3s? If you look at the graph there is a triangular set of edges with weights of 2, 2, and 3. Adding the 3 would make a cycle, so we can’t use it. Other than that 3, the 9 edges we’ve chosen are actually the 9 smallest numbers in the entire graph. There is no set of 9 edges that could possibly give us a lower total cost.

Assessment

Questions (also in Code Studio):

  1. Label the graph with the appropriate terms.

    • Node
    • Edge
    • Weight
    • Tree
    • Cycle

  2. What does a minimum spanning tree tell you about a graph?

    a) The shortest path from a particular point in the graph to another point in the graph.

    b) The shortest path between any two points for all points in the graph

    c) The fewest number and smallest total distance of connections necessary to connect all points in a graph

    d) Whether or not the graph represents a network

    e) The fewest number and smallest total distance of connections necessary to travel from one point to all the other points without having to visit a point twice

  3. The images below all show the same map (or graph) as the one depicted above, but have different paths between the points highlighted. Please choose the image that is highlighting a Minimum Spanning Tree for the map. NOTE: The “distance” between points is depicted by the number of line segments connecting any two points.

  • Levels
  • 1
  • (click tabs to see student view)
View on Code Studio

Student Instructions

Unit 1: Lesson 1 - Personal Innovations

Background

Welcome to Computer Science Principles! Computer science is all about being innovative—finding ways to solve problems. In this class, you will discover lots of connections between people and computing, explore how technology impacts absolutely everything in your life, and work with others in fun and creative ways. Today, you will take the first step in becoming an innovative computer scientist.

Lesson

  • You're an expert: teach us something you know
  • In a team, design a prototype for a technological innovation
  • Learn more about innovation in a video

Vocabulary

Prototype: A preliminary sketch of an idea or model for something new. It’s the original drawing from which something real might be built or created.

Resources

Standards Alignment

View full course alignment

CSTA K-12 Computer Science Standards (2011)

CT - Computational Thinking
  • CT.L3B:3 - Critically examine classical algorithms and implement an original algorithm.
  • CT.L3B:4 - Evaluate algorithms by their efficiency, correctness, and clarity.
  • CT.L3B:6 - Compare and contrast simple data structures and their uses (e.g., arrays and lists).

Computer Science Principles

4.1 - Algorithms are precise sequences of instructions for processes that can be executed by a computer and are implemented using programming languages.
4.1.1 - Develop an algorithm for implementation in a program. [P2]
  • 4.1.1B - Sequencing is the application of each step of an algorithm in the order in which the statements are given.
  • 4.1.1H - Different algorithms can be developed to solve the same problem.
  • 4.1.1I - Developing a new algorithm to solve a problem can yield insight into the problem.
4.1.2 - Express an algorithm in a language. [P5]
  • 4.1.2A - Languages for algorithms include natural language, pseudocode, and visual and textual programming languages.
  • 4.1.2B - Natural language and pseudocode describe algorithms so that humans can understand them.
  • 4.1.2C - Algorithms described in programming languages can be executed on a computer.
  • 4.1.2F - The language used to express an algorithm can affect characteristics such as clarity or readability but not whether an algorithmic solution exists.
  • 4.1.2I - Clarity and readability are important considerations when expressing an algorithm in a language.