Tourist Town: Dominating Sets
Source Institutions
-
Computer Science Unplugged
Add to listGo to activity
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.
- 5 to 10 minutes
- 45 to 60 minutes
- $1 - $5 per group of students
- Ages 11 - 18
- Activity, Lesson/Lesson Plan, Simulation
- English
Quick Guide
Materials List (per group of students)
- a copy of the blackline master Ice Cream Vans
- several counters or poker chips of two different colors
- an overhead projector transparency of the blackline master on page 150, or a blackboard to draw it on
Subjects
- Engineering and Technology
- Computing
- Computer Science
- Engineering
- Computer Engineering
- Technology
- Information and Communication
- Computing
- Mathematics
- Algebra
- Patterns
- Number and Operations
- Multiples and Factors
- Number Systems
- Problem Solving
- Representation
- Algebra
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
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:
- Creative Commons, Computer Science Unplugged, 1998
Funding Sources:
- Brian Mason Scientific and Technical Trust
- Google Inc.
