CS46A Lab

Analyzing an Algorithm

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

Work together as a group of four. Your group should have the following roles:

1. The facilitator makes sure that everyone plays their roles and keeps the discussion moving, staying within the time for each step. The facilitator also reports the group results back to the instructor during debriefing.
2. The simulator simulates relevant parts of a program (such as a robot, a drawing, or the state of objects or variables), by moving a token on a board, making a drawing, or updating the values of variables. The simulator should only simulate the steps that the director (see below) specifically requests. The simulator is also the scribe for the group.
3. The director directs the simulator, calling out the next action to be simulated (such as "turn left" or "change n to 10"). The director can also ask questions such as "is there a wall to the right?" or "what is the value of n"? The director should not look at the board or work sheet that the simulator keeps.
4. The driver enters code into the computer and executes it. In this lab, the driver also shares some of the directing duties.

You will not always play these roles. During general discussion, everyone participates.

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? Yields true if there is a wall directly in front of the robot, false otherwise.
• Right has wall? Yields true if there is a wall directly to the right of the robot, false otherwise.

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. [1 minute]. Assign group roles. The first person in the group assignment list is the facilitator, the second the simulator, the third the director, and the fourth the driver.
2. [10 minutes] Execute this program, starting with the following configuration.

   

   The director calls out the steps for the main program and “Find window” method. The driver calls out the operations for the “Go to wall” method. The simulator moves the robot on a sheet of paper, following the instructions given by the director/driver.

   Facilitator: Enforce these roles. Make sure that the director/driver properly calls out the directions from the flowchart, and that the simulator accurately moves the robot.

3. [5 minutes] As a group, describe in words 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. Be sure that everyone in the group agrees with these descriptions and can explain them. When you are done with the discussion, the simulator adds the results to the report
   • Facilitator: Dictate the group consensus for the main program to the simulator
   • Director: Dictate the group consensus for the “Go to wall” method to the simulator
   • Driver: Dictate the group consensus for the “Find window” method to the simulator
4. [10 minutes] Each group member should work alone on the following question for two minutes; then have the Facilitator call the group together to talk about the solutions.

   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!)

   Simulator: Add a description of the problem situation(s) that you found to the report.

5. [5 minutes] After you have found the problem situation(s) in step 4, think about how you did it. If you had to tell someone else how to look for problems like this, what would you say? Have each member of the group try to explain in his or her own words.

   Simulator: Add a brief summary of this discussion to the report.

6. [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.)

   Simulator: Write down the fix that the group agreed on.

7. [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, Karel 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?

   Simulator: Write down the problem situation and the suggested fix.

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 robot1 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?