## 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.

## Goals

Students will be able to:

• Write an algorithm for solving the minimum spanning tree (MST) problem.
• Use the terms algorithm, graph, node, and 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

## 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.

## Getting Started

How much do you think the Internet costs to build and maintain? 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 below 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).

#### Teacher's Tip: Description of Router Map

The Router Map diagram shown on this page consists of four small circles - each representing one router. The routers are named A, B, C and D. The routers A, B, and D form a large triangle, and the last router C is placed in the middle of this triangle. A dotted line is shown in between each routers to show the direct connection of the routers. The connections are A-B, A-C, A-D,B-C, B-D and C-D - indicating all possible direct connections among the four routers. The map also shows the cost of building each connection: A-B costs 2 million dollars, A-C costs 2 million, A-D costs 5 million, B-C costs 3 million, B-D costs 2 million, and C-D costs 1 million.

• Question 1 - Which connections would you choose to build to keep the total cost down?
• Question 2 - 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?

## Activity

Using the Activity Guide, discuss the following points with students.

• What are algorithms and why do we want them?
• Define the following terms for graph problems: Graph, Node, Edge, Cost, Cycle, Tree
• Explain the Minimum Spanning Tree problem

Next, give students some time to experiment with finding the MST on the Activity Guide's example graphs, and ask students to write an algorithm, or series of steps, that would find the MST for any graph

## Wrap Up

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. Try to act out the algorithm on the original graph, or a new one that you just make up.

Discuss: Compare and contrast your strategies with the one your peers presented. Was your algorithm clearly written and easy to understand? Were there two different algorithms that still solved the problem correctly?

#### Pro Tip

• How do you know when to stop? i.e. How do you know you’ve found the minimum?
• Can you define a strategy for considering an edge, then either keeping it or discarding it?
• This is a different concept form the one we learned in the ‘text-compression’. While text compression does not have clear algorithms, the MST has definite algorithms.
• 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.

## Assessment

#### Teacher's Tip: Router Map Diagrams

This assessment is done with the "Code Studio" program on the corresponding section of the Code.org CSP curriculum - high school level. If you would prefer to use a tactile map, you may benefit from using the tactile image enhancer machine (link) that makes these diagram into accessible tactile graphics. We have provided the template that could be used with the tactile image enhancer machine in the following links: Question 1 diagram (link), Question 2 diagram (link)

1. Label the graph with the appropriate terms.

• Node
• Edge
• Weight
• Tree
• Cycle

#### Teacher’s Tip: Description of the Diagram (above)

The diagram is a router connection map. The base of the map consists of 8 small circles - each representing a router location. The routers named a, b, c, d, e and f form a circular connection. Inside of this circle, there are routers g and h. Most of the routers connect to two adjacent two routers (connected by the line drawing), while some of them connect to multiple routers. One number is written on each of the connection lines. We have prepared the list of the router connection and the number written on each connection line in a downloadable Router Connection List (link). On this base map, 5 blank boxes (named A, B, C, D and E) are provided for you to fit the following answer keys. You are to choose the name of this map in box "A," the name of the connection line for the box "B," and the name for the small circle - that represent one router - for the box "C." Additionally, the lines that connect the routers e, g and h are colored yellow. You are to choose the name of this circular connect for the box "D." Finally, you are to choose the name of the number written on each line for the box "E."

2. Multiple Choice. 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.

#### Teacher's Tip: Description of the Five Diagrams (above)

The diagram above contains five identical graphs. Each graph has the same connections used in question 1, but have different connection line values. These differences are reflected in this downloadable Router Connection List 2 (link). Additionally, on each of the five graphs, a different router connection is highlighted. Below are the connections.

• The graph "A" shows the connection between: a-b, b-g, g-h, h-c, h-d, h-e and e-f
• The graph "B" shows the connection between: a-b, b-c, c-h, h-d, d-e, e-f and f-a
• The graph "C" shows the connection between: a-f, f-e, e-h, h-d, h-g, g-b and b-c
• The graph "D" shows the connection between: a-b, b-c, b-g, a-f, f-e, e-h and h-d
• The graph "E" shows the connection between: a-b, b-c, c-d, d-h, h-g, g-e, e-f and f-a

## Extended Learning

You might check out some real pseudocode and a visualization of the minimum spanning tree using the link below.

## Standards Alignment

• CSTA K-12 Computer Science Standards (2011): CT.L3B:3, CT.L3B:4, CT.L3B:6
• Computer Science Principles: 4.1.1 (B, H, I)
• Computer Science Principles: 4.1.2 (A, B, C, F, I)