Tourist Town: Dominating Sets

Add to list Go to activity
Activity link broken? See if it's at the internet archive
In this activity, learners use a fictitious map of "Tourist Town" and counters to problem solve how to place ice-cream vans on street intersections so that every other intersection is connected to one that has a van on it. Use this activity to introduce learners to computer science themes including nodes, dominating sets, exponential-time algorithms, polynomial-time algorithms, and NP-complete problems. Variations, extensions, background information, and solutions are included in the PDF.

Quick Guide

Preparation Time:
5 to 10 minutes
Learning Time:
45 to 60 minutes
Estimated Materials Cost:
$1 - $5 per group of students
Age Range:
Ages 11 - 18
Resource Types:
Activity, Lesson/Lesson Plan, Simulation
Language:
English

Materials List (per group of students)

Keywords

Subjects

  • Engineering and Technology
    • Computing
      • Computer Science
    • Engineering
      • Computer Engineering
    • Technology
      • Information and Communication
  • Mathematics
    • Algebra
      • Patterns
    • Number and Operations
      • Multiples and Factors
      • Number Systems
    • Representation
  • The Nature of Technology
    • The Design Process
      • Problem Solving

Informal Categories

  • Computers

Audience

To use this activity, learners need to:

  • see
  • see color
  • read
  • 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.