Ice Roads: Steiner Trees


Source Institutions

Source Institutions

Add to list Go to activity
Activity link broken? See if it's at the internet archive
In this outdoor activity, learners use pegs (like tent pegs) and string or elastic to simulate drill sites and roads in Northern Canada. Learners are challenged with figuring out how to connect the roads to all the drill sites while keeping the total road length to a minimum. They'll discover that intersections or "Steiner" points provide efficiency between points within a network. Use this activity to introduce learners to computer science themes including Steiner trees, algorithms, and NP-complete problems. Variations, extensions, background information, and solutions are included in the PDF.

Quick Guide


Preparation Time:
Under 5 minutes

Learning Time:
30 to 45 minutes

Estimated Materials Cost:
$5 - $10 per group of students

Age Range:
Ages 11 - 18

Resource Types:
Activity, Lesson/Lesson Plan, Simulation

Language:
English

Materials List (per group of students)


  • five or six pegs to place in the ground (tent pegs are good, although a coat hanger cut into pieces which are then bent over is fine)
  • several meters of string or elastic
  • a ruler or tape measure
  • pen and paper to make notes on

Subjects


  • Engineering and Technology
    • Computing
      • Computer Science
    • Engineering
      • Computer Engineering
      • Transportation Engineering
    • Technology
      • Information and Communication
      • Transportation
      • Construction
  • Mathematics
    • Algebra
      • Patterns
    • Geometry
      • Plane Geometry
    • Measurement
    • Representation
  • The Nature of Technology
    • The Design Process
      • Problem Solving

Informal Categories


  • Computers
  • Outdoor Activity
  • Transportation

Audience


To use this activity, learners need to:

  • see
  • read
  • be mobile
  • touch

Learning styles supported:

  • Involves teamwork and communication skills
  • Uses STEM to solve real-world problems
  • Involves hands-on or lab activities

Other


Foreign language versions of this resource:

Components that are part of this resource:

Includes alignment to state and/or national standards:

This resource is part of:

Access Rights:

  • Free access

By:

  • Bell, Tim ; Witten, Ian ; Fellows, Mike

Rights:

Funding Sources:

  • Brian Mason Scientific and Technical Trust
  • Google Inc.