User login


The Poor Cartographer: Graph Coloring


Source Institutions

    Computer Science Unplugged

Add to listGo to activity
The Poor Cartographer: Graph Coloring

In this activity, learners help a poor cartographer color in the countries on a map, making sure each country is colored a different color than any of its neighbors. Through this exercise, learners discover the "has-to-be" rule and the value of place-holders. This activity reveals the complexity of graph coloring algorithms in computer science. Variations, extensions, background information, and solutions are included in the PDF.

Quick Guide


Preparation Time:
5 to 10 minutes

Learning Time:
30 to 45 minutes

Estimated Materials Cost:
1 cent - $1 per group of students

Age Range:
Ages 6 - 18

Resource Types:
Activity, Lesson/Lesson Plan, Simulation

Language:
English

Materials List (per group of students)


Subjects


  • Engineering and Technology
    • Computing
      • Computer Science
    • Engineering
      • Computer Engineering
    • Technology
      • Information and Communication
  • Mathematics
    • Algebra
      • Patterns
    • Data Analysis and Probability
      • Probability
    • Problem Solving
    • Representation

Informal Categories


  • Arts and Crafts
  • Computers

Audience


To use this activity, learners need to:

  • see
  • see color
  • read
  • touch

Learning styles supported:

  • 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:

Funding Sources:

  • Brian Mason Scientific and Technical Trust
  • Google Inc.

Share


User Lists


This resource is part of these lists:

  • Thumbnail maps by lisa.paguaga@br... on 2015-03-16