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 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 height 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.

1) Main program

Here, the hexagons denote method calls. The flowcharts for the methods are below:

2) “Go to wall” method:

3) “Find window” method:

Part A. Simulation

1. [10 minutes] 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. [5 minutes] 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. [10 minutes] As a team, find a solution to the following:

   Question: In step 1, you should have successfully completed the program. (That is, Karel 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 Caroll. 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 Karel. Use pencil and paper for sketches!)

4. [5 minutes] 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. [5 minutes] 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. [10 minutes] 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? How could you fix the program to make it more efficient in this case?

Part B. Checking Your Solution

1. Driver: Download this project and unzip it somewhere. Be sure it is actually extracted. By default, Windows only gives you the illusion of extracting it. Start NetBeans. In NetBeans, select File->Open Project and select the extracted robot directory. 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 MyScene class. The performCustomSetup method calls makeRoom. Modify the call to makeRoom so that the window is on the left wall. How did you do that? (Note: The x-axis points towards you, and the y-axis points to your right.)
3. Modify the call to makeRoom so that the window is on one of the problem situations you identified in part A. What is the call that you used?
4. What happens when the program runs with that situation?
5. Look at the code of the findWindow method. Apply the fix that you identified in part A. What is your fix in Java code?
6. What happens when you run the program with your fix?