 Graphic by Keith Ohlfs |
|
|
Graphic by Keith Ohlfs |
|
The purpose of this problem set is to give you more experience with recursion, including practice with invocation trees, and writing recursive methods which return values.
There are 3 pieces to this problem set: the prelaboratory assignment, the laboratory assignment and the homework assignment. You are required to do all three parts. We recommend that you do the prelaboratory problem before your lab section, the laboratory problem during your lab section and the homework problems after completing the prelab and lab assignments.
Prelab Problem: Turn in your invocation tree diagram with the rest of your hardcopy submission. There is no softcopy submission for this part.
Laboratory Problem: Save the modified Hurdle1World.java file in the HurdleWorld folder. Upload the entire folder to your ps8 drop folder. Turn in a hardcopy of the Hurdle1World.java file.
Homework Problems : Save the modified HungryWorld.java file in the HungryWorld folder. Upload the entire folder to your ps8 drop folder. Turn in a hardcopy of the HungryWorld.java file. Save the modified PathFinderWorld.java file in the PathFinderWorld folder. Upload the entire folder to your ps8 drop folder. Turn in a hardcopy of the PathFinderWorld.java file.
Turn in only one package of hardcopy materials. Staple your files together with the cover page, and submit your hardcopy package by placing it in the box outside of Stanzi's office (E106, directly across from E101).
Reminders
As discussed in class, an invocation tree is an abbreviated version of a Jave Execution Model. It contains a node for each method called during the execution of a program. Each node contains the name of the method, the values of its parameters, and (where applicable) its result. There is an edge connecting each "parent" node to the "children" nodes for the method invocations encountered directly within the body of the parent. The children nodes are all shown at the same vertical level, arranged from left to right in the order of their execution.
For example, consider a recursive definition of the Fibonacci function:
public int fib (int n) {
if (n < 2) {
return n;
} else {
return fib(n-1) + fib(n-2);
}
}
Below is an invocation tree for the invocation fib(6). Each node has the form fib(n):r, where n is the parameter of the invocation of fib and r is the result returned by the invocation.
In this problem, you will draw an invocation tree for the invocation of a method that computes an element of Pascal's triangle. Pascal's triangle is a triangular arrangement of numbers whose outer edges consist of 1s and each of whose inner elements is the sum of the two numbers immediately above it to its right and left:
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
Let P(r,i) indicate the value of the ith element in the rth row of Pascal's triangle, where rows are numbered from top to bottom starting with 0, and elements in a row are numbered from left to right starting with 0. For example, P(4,0) = 1, P(4,1) = 4, and P(4,2) = 6.
Here is a recursive method that computes the value of P(r,i):
public int P (int r, int i) {
if ((i == 0) || (i == r)) {
return 1;
} else {
return P(r - 1, i - 1) + P(r - 1, i);
}
}
For this problem, you are to draw a complete invocation tree for the invocation P(6,4). Each node of your tree should have the form P(r,i):a, where r is the row number, i is the element number within a row, and a is the answer returned by the invocation. Be sure to draw your nodes small enough so that they all fit on a single piece of paper. All children of the same parent should appear at the same vertical level, as in the fib example above.
Task 1: In Problem Set 7, the buggles learned to jump hurdles of arbitrary height by using a recursive method. When a number of hurdles were placed at the base of a BuggleWorld grid, a buggle starting at position (1,1) could run across the base of the grid jumping all of the hurdles in its path until it reached a bagel (the finish line).
This assignment is similar to problem set 7; just as before, the buggles do not know the placement of the hurdles and do not know the length of the race. The difference is that the race committee has run out of bagels. So, the buggles must learn to stop the race by detecting the opposite wall. You may recall that the buggles learned to do this when they jumped hurdles of a known height. However, it is more difficult to detect the opposite wall with hurdles of arbitrary height, since the buggles do not know whether they are jumping a hurdle, or going up the wall! At least, that is, until they run into the top of the grid (which is, indeed, how you distinguish between the two).
Therefore, the buggle has the following behavior:
After the race, the grid should appear as:
To see a working applet, download the the ps8_programs folder from the CS111 download directory. Look in the HurdleWorld folder for the Test folder. Open the Hurdle1World.html file from the Test folder with the Applet Viewer. Experiment with the HurdleWorld to make sure you understand the requirements for task 1.
Next, open the HurdleWorld folder from the ps8_programs folder. Open the project window and the Hurdle1World.java file. This file contains a number of methods responsible for setting up the hurdle race. You do not need to understand these files to successfully complete this lab. The file also contains a run() method, and a Hurdler1 class containing four instance methods: runHurdles(), atFinishLine(), findTop(), and jumpHurdle(). You have been given the runHurdles(), atFinishLine(), and jumpHurdle() methods, which you should recognize as the recursive solution to jumping hurdles of arbitrary height from problem set 7. You need to fill in the findTop() method stub to detect the opposite wall. Notice that this method is recursive, and returns a boolean value. Let's work on how to write findTop() in Lab.
Task 2: As a second exercise, we will again use recursion with a return value, to count the number of hurdles that the buggle has jumped for a particular race. When the race is completed, the buggle should change color, and draw a line of length corresponding to the number of hurdles jumped, as shown:
To see a working applet, look in the HurdleWorld folder for the Test2 folder. Open the HurdleWorld2.html file from the Test2 folder with the Applet Viewer. Experiment with the HurdleWorld to make sure you understand the requirements of task 2.
Re-open the Hurdle1World.java file in the HurdleWorld folder from task 1. You will simply be adding your modifications for task 2 to this file. Specifically, change the runHurdles() method so that it:
You will also need to change the invocation of runHurdles() in the run() method. Let's work on this together in Lab.
This problem deals with a buggle that has the following behavior. The buggle starts out in the middle of the first row of a grid facing north. The grid cells are randomly populated with a user-specified number of bagels; however, the bagels are initially placed so that none are in the column in which the buggle initially faces. The buggle moves row-by-row from the bottom row to the top row, and performs the following action at every row:
For example, suppose the initial grid configuration is:
Then the final grid configuration should be:
To see a working applet, look in the HungryWorld folder for the Test folder. Open the HungryWorld.html file from the Test folder with the Applet Viewer. Experiment with the HungryWorld to make sure you understand the task.
Part a. Assume that you are provided with a public void eatRow() method that implements the row-eating behavior described by the three bullets above. Use this method to implement the following method:
public void eatRows() Apply the eatRow() method at every row in the grid as the buggle moves from the bottom row to the top row.
Part b. Assume that you are provided with the following methods:
public int countBagels() Return the number of bagels between the buggle and the wall it is facing. Calling this method should not change the state of the buggle. public void eatBagels() Eat all the bagels between the buggle and the wall it is facing, leaving behind a colored square in every cell that originally contained a bagel. Calling this method should not change the state of the buggle.
Using the above two methods, implement the public void eatRow() method mentioned in part a. Part c. Implement the public int countBagels() method described in part b. Part d. Implement the public void eatBagels() method described in part b.
In Problem Set 6, you taught a buggle to find a bagel in a maze by walking forward and turning so that her right hand was always on the wall. The result of the maze navigation process was rather unsatisfying, however. The buggle typically colored in large segments of the maze, most of which were blind alleys that did not lead to a bagel.
In this problem, you will implement a more elegant maze searching program in which the buggle, upon finding the bagel, draws the shortest path from the bagel back to its starting position (the lower left corner). The following graphic shows the final configuration of the grid after a sample search:
You should begin this problem by experimenting with the working applet in the Test subfolder of the PathFinderWorld folder within ps8_programs. Open the PathFinder.html file from the Test folder with the Applet Viewer. The buggle world grid should contain the initial maze shown above. Pressing Run creates an eastward facing buggle in the lower left corner and causes her to search for the bagel and ultimately draw a path back to her starting position and heading. After each successful search, pressing Reset draws a new random maze, and pressing Run will solve the new maze. Experiment with the PathFinderWorld to make sure you understand the correct operation of the search.
Even if you play with PathFinderWorld for a very long time, it will probably not be at all obvious to you how the buggle accomplishes her task. In a typical maze, the buggle seems to wander around for a while, exploring various blind alleys, until she happens to find the bagel. At that point she very purposefully draws the shortest line directly back to the starting position. How does she do it?
It turns out that the buggle is following a rather clever recursive strategy. Given that the maze doesn't contain any circular paths, the buggle can explore the whole maze in the following way:
// search for a bagel in a maze, and return to starting position.
// If none found, return false.
// Otherwise, put down the brush and leave a trail as you are
// retracing the shortest path to the starting position and return true.
public boolean findBagel() {
// base case: if there is a bagel, put down the
// brush and return true
// recursive case: explore left, front, and right.
// if a bagel is found in any of these directions,
// return true immediately without further exploration.
// return false if no bagel was found in any of the 3 directions.
// replace this stub with your own code:
return false;
}
Rather than defining everything in one method, I encourage you to use
the helper methods below. Note that these helper methods will have to
call findBagel() - this is an example of mutual
recursion.
// explore the front: if there is a wall in front, just return false.
// otherwise, go forward, search for a bagel recursively, and return
// the result after going backwards again.
public boolean exploreFront() {
// replace this stub with your own code:
return false;
}
// explore the left: similar to exploring the front, but need to turn left
// first (and then right again at the end).
public boolean exploreLeft() {
// replace this stub with your own code:
return false;
}
// explore the right: similar to exploring the front, but need to turn right
// first (and then left again at the end).
public boolean exploreRight() {
// replace this stub with your own code:
return false;
}
Hints: