Problem Class Questions for

1007 (Programming Principles) Week 2, 2005

1a. You have fifty books lined up on a shelf in random order. Determine an algorithm (sequence of instructions) to sort the books into alphabetic order by title, if any two books can be swapped at each step.

1b. Now determine an algorithm to sort the books if only books next to each other can be swapped. What is the minimum number of swaps needed to guarantee the books will be sorted regardless of their original order?

2a. You have fifty books lined up on a shelf in sorted order (sorted by title). If you search for a book by starting at the left hand end, and move right checking each book in turn, how many books do you need to check on average to find the one you are looking for?

2b. Now if you can look at the books in any order, determine an algorithm to search for a particular book that requires you to look at no more than 6 books to find the one you want.

3. Devise an algorithm to generate all possible permutations of the characters forming a word (that is all possible orderings of the characters making up a word). For example, given the word "the" your algorithm would generate "teh", "hte", "het", "eht", "eth" and "the" (in any order).

4. A simple robot can respond to the following commands:
robot.forward - the robot moves forward 10cm, stopping if it encounters an obstacle in front of it (it may not move at all if it is directly in front of an obstacle).
robot.left - the robot turns 90 degrees anti-clockwise without changing its location.
robot.right - the robot turns 90 degrees clockwise without changing its location.

The robot also has two sensors that can be queried:
robot.frontBumper - reports true if the robot is up against an obstacle and cannot move forward, otherwise it reports false.
robot.floorSensor - reports true if the floor below the robot is reflective, false if not.

The robot has no memory of its location, the direction it is facing or where it has been.

a. The robot is placed in a rectangular arena surrounded on all sides by a wall. The floor is covered with non-reflective tiles, except for one reflective tile placed at a location next to a wall. When the robot is over the reflective tile the floor sensor will report true. 
Develop an algorithm so that wherever the robot is placed in the arena, the robot will move until it is over the reflective spot.

Does changing the size of the arena affect your algorithm?

b. Modify your algorithm so that the robot will find the reflective tile wherever it is placed in the arena (not just next to a wall).

c. Assume the arena can be any shape, for example L-shaped. Does your algorithm from part b) still work whatever the shape of the arena? If not modify your algorithm.

If you believe you have a working algorithm, how do you know if will work for any possible shape? Can you prove it?

d. Extend your algorithm again, so that the robot will find the reflective tile when there are also immovable obstacles placed in the arena. The robot cannot move forward when it finds an obstacle and the frontBumper reports true. Does you algorithm always work or are there combinations of obstacles in certain positions that cause the algorithm to fail?

e. Assume the robot is not perfect so that it the distance it moves forward or the angle it turns through is imprecise. For example, the distance it moves forward may be 10cm ± 5%. If the amount of variation is 5%, 10% or 20% do your algorithms still work? If not modify them so they do. 
Is there a level of imprecision at which the movement of the robot essentially becomes random?

f. The robot is altered so that the robot.forward command causes the robot to keep moving forward until it hits an obstacle (the frontBumper sensor reports true). Assume the robot can still turn when it hits an obstacle. Do all your algorithms from parts a-e still work? Or do some or all need modifying?