- View more resources from this publisherQueen Mary University of London
Tour Guide (Companion to the Knight’s Tour Activity)
Containing two linked activities, these resources from the CS4FN team introduce graphs to represent inter-related data and algorithms to negotiate them.
Suitable for non-programmers being introduced to algorithms, the two challenges – the Knights Tour and the Tour Guide – are similar. Both use graphs as abstractions of data that present only the information that is critical to solving the problem – complexity is hidden. For the tour guide nodes represent tourist destinations while edges represent the routes between them. The Knights tour presents a modified chessboard, and ask if an algorithm can be found that allows the Knight to visit each square only once.
The students are challenged to plot out a Hamiltonian Cycle – i.e. to visit each node once. While the Tour Guide presents learners with a ready-made graph The Knights tour challenges them to draw their own – thereby abstracting a potentially difficult problem. Depth-first and breadth-first search methods – both graph traversal algorithms - are illustrated as ways to systematically draw graphs.
It turns out, ultimately, that the two graphs are identical, even though the problems appeared to be similar but different. Generalising the problem and representing it in different ways has allowed one solution to be applied to another, related, problem.
This activity would be appropriate for students of all ages, upper primary upwards.
Show health and safety information
Please be aware that resources have been published on the website in the form that they were originally supplied. This means that procedures reflect general practice and standards applicable at the time resources were produced and cannot be assumed to be acceptable today. Website users are fully responsible for ensuring that any activity, including practical work, which they carry out is in accordance with current regulations related to health and safety and that an appropriate risk assessment has been carried out.
Downloads
-
Tour guide (teachers' notes) 596.11 KB
-
Tour guide (textbook) 675.75 KB