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:

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.

Resources

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

The Router Map

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.

Activity

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

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

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.

Assessment 1 - router map diagram

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?

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.

Assessment 3-Router map diagrams

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.

Extended Learning

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

Standards Alignment