Correctness of algorithms

After Hansel and Gretel overheard their parents plan to leave them behind in the forest, Hansel gathered pebbles that he dropped along the way so that they can later show them the way back to their home.

There are different ways to trace back the pebbles. To find out which work, you will act out Hansel and Gretel’s journey home using different algorithms.¹

Write down your observations for each algorithm and answer the questions after you execute each algorithm.

Algorithm 1

The plan they try first is to repeatedly find the closest pebble and move to it. Now, thinking about it carefully, act out Hansel and Gretel’s actions.

1. Form a group of 2 or 3.

2. Drop “pebbles” (they can be pieces of paper, pencils, or any other kind of small object) across the classroom with different distances between them.

3. Starting from the last pebble dropped, execute the algorithm:

   Repeatedly find the closest pebble and move to it.

How does this algorithm work? Is it effective in returning Hansel and Gretel to their home? Did you follow the instructions exactly? If you did, you would have found that you could not move at all – the closest pebble would have been the one that you were standing on!

Algorithm 2

The second plan after getting stuck on the first pebble is this. Find the closest pebble, not including the pebble you’re currently on, and move to it. Once again:

1. Form a group of 2 or 3.

2. Drop several pebbles.

3. Starting from the last pebble dropped, execute the algorithm:

   Repeatedly find the closest pebble not including the one you’re currently on and move to it.

How does this algorithm work in comparison to the first algorithm? Do you return home? Depending on how far apart you originally placed the pebbles, you may have only been able to move backwards if the pebble that would have moved further towards home was farther away than the pebble you had just moved from.

Based on this information, Hansel and Gretel amend their algorithm once again.

Algorithm 3

The final plan they devise after getting stuck in between pebbles is the following. Find the pebble closest to you that was not visited before and move to it. For the last time:

1. Get into a group of 2-3

2. Drop a number of pebbles.

3. Starting from the last pebble dropped, try this algorithm:

   Repeatedly find the closest pebble not visited before and move to it.

How does this algorithm work in comparison to the others? Do you return home? You should have been able to get home successfully.

Summary

Discuss and write down: What did you learn from this exercise?