1a. You have fifty books lined up on a shelf in random order. Determine an algorithm 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. 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. 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. A reflective spot is placed on the floor at a location next to a wall. When the robot is over the spot 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.
b. Modify your algorithm so that the robot will find the reflective spot 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 spot 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.
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?