Roamer, Algorithms and the Computing Curriculum

  • Published February 21, 2014
  • By Dave Catlin

What is an algorithm? An algorithm is a set of step-by-step actions that will solve a problem. This definition does not adequately explain what it really is. In the way of a preview of Roamer and the Computing Curriculum Packages, I will try and add some substance to the answer and I will provide a simple Roamer activity that will show you how you can teach the concept in a concrete practical way.

What is an Algorithm?

Step-by-step actions that solve a problem is as good as any answer you will get, but understanding it is better done with a practical example. Algorithms, exist without computers, but computers do not exist without algorithms. So while we do not need to think of algorithms in terms of computer activity, it is convenient for us to look at a task that computers do regularly. We are going to look at “sorting algorithms”. The computer has a list of things it wants to sort into size order. Imagine you have a list of all the children in your class, and next to their names was their height.

Sort the list opposite out, but as you are doing it, think about the step-by-step actions you are taking. Can you discern a pattern.  Assume you are doing this in a word processor, so you can insert rows wherever you want. Click here for an exemplar answer to this sorting problem.

Anna 1.20m
John 1.35m
Claire 1.33m
Robert 1.23m
Phillip 1.38m
Georgina 1.26m

 

Sorting Algorithms

Bubble Sort Algorithm

The Bubble sort algorithm takes the first two numbers in a list if the second number is bigger than the first, it checks the second and the third. If the third number is bigger than the second number it swaps them. It then checks the third and fourth. It performs this process through the whole set of numbers. Once it has got to the last two numbers, then it starts again with the first two numbers. It continues this process until it can pass through the entire list without swapping any numbers.

The quick sort algorithm takes a different approach.  The steps are:

  1.  Pick an element, called a pivot, from the list
  2. Reorder the list so that all elements with values less than the pivot come before the pivot, while all elements with values greater than the pivot come after it
  3. Repeat the process with each sub group until the list is in order

 

Quick Sort Algorithm

 

Algorithms and Programs

You can see in the examples above there is a step by step procedure for putting the information in order.  While the problem to be solved is essentially the same, the algorithms to sort out the lists are dramatically different.  Also notice that the algorithm is not a program.  A program is an implementation of the algorithm using a computer language.

Amazing Roamer

The Amazing Adventures of Myrtle the Turtle

I’ve dragged this activity out of the archives. It was written in 1984 by Anth Ginn a London Primary school teacher and illustrated by Malcolm Livingstone. It was the first set of activities we did with the Valiant Turtle. It is still valid and Malc’s great cartoons are too good to be lost in our warehouse.  You can access the complete activity and the support resources free of charge in the Roamer Activity Library.

In this Roamer activity students will explore some basic algorithms for getting Roamer through a maze.

Present the students with the maze below.  Their challenge is to find an algorithm that they can use to get Roamer through the maze.  You  found an algorithm to the student height sorting problem, by solving the problem and trying to identify a pattern in the way you solved it.  Programming Roamer step-by-step will help students think about a rule that will help them find an algorithm.

Roamer, Educational Robot, Valiant Technology

You can make this simple maze, quickly and easily using tape on the Roamer Clear Grid Mat.

 

Mazes have fascinated people for thousands of years.  Psychologists use them in intelligence text experiments with animals like rats.  Can they find a way through the maze a get to the food?  In the early days of robotics, engineers used the problem as an exercise in developing the construction of the robot (what sensors were needed) and the Artificial Intelligence required by a robot  to autonomously find its way through a maze.  That is they wanted to discover and test the algorithms that would solve this problem.

Roamer can go forward 2, then turn left 90 and go forward 1.  Then it needs to make a decision.  Does it continue going forward, or does it turn left?  At each junction a decision has to be made.  The algorithm is a rule that the robot could use to make the decision at every junction.  There are two rules that can be used to solve this maze: the left-hand and right-hand rules.  The left-hand rule tells the robot to always follow the left-hand wall.   The right-hand rule is follow the right-hand wall.

These algorithms will not work with all mazes.  There are lots of interesting educational challenges we can do with maze problems.  The version of Amazing  Roamer used in the Roamer Olympics focussed on negotiating a maze with the smallest possible number of instructions.   The real advanced maze challenge is the Micro Mouse Competitions.  Its Roamer’s ambition to be able to enter.

I want to take part in a Micro Mouse competition when I grow up.

Roamer

The Keep watching GO and the Activity Library for further developments.

Micro Mouse USA

Micromouse Online

You have to log in to Comment.