Lesson 14: Steiner Trees
For this lesson, refer to CS Unplugged, Activity 15, page 151. This lesson is a nice contrast to the Muddy City lesson because the problem statement is similar, but the lack of constraints (the roads) makes it much more difficult. There appears to be no "greedy" approach, and no way to efficiently solve this problem is known.

Evaluation:

Ask students to compare and contrast the problems presented in this lesson (Icy Roads), and in the minimum spanning tree lesson (Muddy City, Lesson 13). Which problem seemed harder? Why? Which was easier to solve? Have the students describe their steiner tree solutions for 3 vertices and 4 vertices. How do these compare with the solution to a minimum spanning tree problem on a graph with 3 or 4 vertices?

Look for creativity as the students lay out the strings. Do they try unusual approaches, or are they "stuck" to the notion that the vertices are connected by edges? Have the students write down their various attempts, and record the results of each.

Standards:

  • K-4: 1, 2, 3, 4, 5, 9, 10.
  • 5-8: 1, 2, 3, 4, 7, 12, 13.
  • 9-12: 1, 2, 3, 4, 7, 12, 14.

Skills:

  • Problem solving / reasoning / communication / connections
  • Estimation of distances
  • Addition of distances
  • Measurement of distances
  • Spatial sense
This lesson is taken from Computer Science Unplugged (c) 1998, by Bell, Witten, and Fellows. See http://unplugged.canterbury.ac.nz/ for copyright restrictions.