CAS Community   >   Resources   >  

An introduction to tractable and intractable algorithms

A game-like introduction to algorithms, heuristics, and their complexity

Michel Wermelinger

Created by Michel Wermelinger
last edited May 23 2017 by Michel Wermelinger

The Jewels of Heuro is a free online activity that takes a gaming task (collecting jewels in a temple) to introduce the following concepts:

  • algorithms and heuristics
  • the travelling salesperson and the shortest path problems, and their theoretical and practical importance
  • brute-force and greedy algorithms
  • complexity of algorithms (quadratic, exponential)
  • Dijkstra’s algorithm for shortest path (just the gist)

The activity shows that two seemingly similar problems (shortest route and shortest path) are actually very different: one can only be tackled with heuristics, the other can be efficiently solved.

Duration: 30min

Level: Beginner - it doesn’t assume previous knowledge of algorithms, not does it involve any programming.

This is one of many Open University free educational resources aimed at the general adult public and I wrote it as such. Due to the subject matter, I believe this activity might be useful for AS/A-level Computing. In fact, it has been used by a publisher as part of a A-level worksheet on algorithms. Any feedback is most welcome.

This resource is copyright by The Open University. Modifying it or writing commercial teaching materials around it requires permission.

Feedback and Comments

Available when logged in (join via the front page, for free):
  • View 4 comments on this resource.
  • View resource history, links to related resources.
  • Leave feedback for the author(s), or help by editing the resource.