Copyright © Cay S. Horstmann, Kathleen O’Brien 2009-2014
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

CS46A Lab

Analyzing an Algorithm

This lab has been adapted from a lab authored by Kent Beck at SDSU.

The Problem

Carol the robot moves along the lines of a grid. Here, we denote her position with an arrow whose tip points to the direction in which she moves. (This is just for diagramming purposes. You'll see later how she actually looks.)

She can carry out the following five operations:

• Move forward. The robot moves one step forward, in the direction she is facing.

  However, if you try to move Carol into a wall, she “crashes” (turns black and ceases to function). Don't do this.

• Turn left. The robot turns 90 degrees to the left, staying at the same location.
• Turn right. The robot turns 90 degrees to the right, staying at the same location.
• Front has wall or window? Yields true if there is a wall or window directly in front of the robot, false otherwise. (Her front sensor is a touch sensor that can't tell the difference between a wall or window)
• Right has wall? Yields true if there is a wall directly to the right of the robot, false otherwise. (Her side sensor is an optical sensor that can't tell the difference between a window and empty space.)

Carol has been placed into a rectangular room with a single window. The width and depth of the room, the position of the window, and Carol's position can be arbitrary. The following program has been designed to position Carol next to the window.

The program is presented in flowchart notation. The rectangles are actions to take. The hexagons denote method calls.

Part A. Simulation

1. Execute this program, starting with the following configuration.

   

   The scribe calls out the steps from the flowchart. The driver moves the robot on a sheet of paper, following the instructions given by the scribe.

2. Both of you: Develop a description, in English, how this program works. (Imagine that you are telling another person how to go to the window, using the same method as in the program.) Give separate descriptions for the main program and for each separate flowchart.
3. As a team, find a solution to the following: (Note that Carol stops at the window and can not go through it.)

   Question: In step 1, you should have successfully completed the program. (That is, Carol should have found the window and stopped beside it.) However, there can be many different starting situations—that is, different positions for the window and different starting locations for Carol. There is at least one starting situation for which the program does not work correctly. Can you find it? Is there more than one such problem situation? (Try different locations for the window and different starting positions for Carol. Use pencil and paper for sketches!)

4. After you have found the problem situation(s) in step 3, think about how you did it. If you had to tell someone else how to look for problems like this, what would you say?
5. Suppose you want to change the program so it works correctly in all situations, including the problem situation(s) you just discovered. How might you do this? (There may be more than one possible answer.)
6. Besides the problem you found in Step 3, there is at least one other starting situation in which the program does not work the way we might expect. In that situation, Carol does eventually find the window and stop; however, it makes an extra trip around the room before doing so. Can you find this problem situation? Scribe: What is the situation? How could you fix the program to make avoid the extra circuit?

Part B. Checking Your Solution

1. Driver: Download the lab7 project folder from here. Add this class. Run the project to make sure that it works. If it doesn't, ask the instructor or lab assistant for help.

   

   What does the program do?

2. Look into the run method and modify the call to makeRoom so that the window is on the left wall. How did you do that? Hint: You specify the center point of the window. (This means you change the values you pass to the method when you call it in RobotTest.java. DO NOT change the makeRoom method) Scribe: What is the call that you used?
3. Scribe: What happens when the program runs with that situation?
4. Modify the call to makeRoom so that the window is on one of the problem situations you identified in part A. ( Remember not to change the makeRoom method) Scribe: What is the call that you used?
5. Scribe: What happens when the program runs with that situation?
6. Look at the code of the findWindow method. Apply the fix that you identified in part A. Driver: What is your fix in Java code?
7. Scribe: What happens when you run the program with your fix?