SUNY Geneseo Department of Computer Science
CSci 240, Spring 2007
Prof. Doug Baldwin
Due Tuesday, February 6
This lab will be easiest to do if you can use a number of Java features and library classes that are in no way unique to recursion, but are useful in a number of settings. Those features that you have not necessarily encountered before are summarized here, and more fully described in external documents referenced below.
Several exercises involve generating random numbers. Java has two main ways of generating random numbers: the Random class, and the Math.random method. The latter is really just a narrow interface to one of the features of the former. Thus, although the Random class is slightly more complicated to use than Math.random, in the long run it will probably be more useful to you in this lab.
A summary of the Random class can be found at http://cs.geneseo.edu/~baldwin/reference/random.html, and complete documentation is included in the documentation for the standard Java library at http://java.sun.com/j2se/1.5.0/docs/api/
The most elegant solution to the first exercise involves defining and using a Java "interface." An interface in Java is a mechanism for declaring certain messages that other classes must provide methods for; instances of these classes can then be assigned to variables or parameters that are formally declared to be instances of the interface.
A brief introduction to interfaces is provided in Appendix A (see section A.5) of our textbook. A somewhat more detailed, but still introductory, discussion is available at http://cs.geneseo.edu/~baldwin/reference/java-interface.html.
Write recursive Java methods that solve each of the following problems. You can, if you wish, put all of these methods into a single program, or you can write separate programs for each.
One of the classic problems in numeric computing is finding so-called "zeros" of functions -- values of x at which a function f(x) is 0. One of the simplest algorithms for finding zeros is the "bisection" algorithm, which works as follows: Start with values x1 and x2 such that it is known that the sign of f(x1) is different from the sign of f(x2) (i.e., f(x1) is negative and f(x2) is positive, or vice versa). Calculate the value, x3 midway between x1 and x2: x3 = (x1 + x2) / 2. If f(x3) is within some user-specified tolerance of 0, return x3 as a zero of the function. Otherwise, if f(x3) differs in sign from f(x1), find and return a zero between x1 and x3. Otherwise find and return a zero between x3 and x2.
Write a recursive Java method that uses bisection to find a zero of a function. Parameters to your method should be x1, x2, the function, and the tolerance. The cleanest way to pass a function to your method is probably to define a "function" interface in Java (see the discussion of interfaces in the "Background" section above), which you can use to declare the function parameter to your method. This interface only needs to declare one message that functions accept, namely one that causes them to compute their value at a given x. You can then define several classes that implement this interface, each class calculating a different function in response to the "calculate your value" message, and pass instances of these classes to your zero-finding method in order to exercise it.
A palindrome is a string that reads the same forwards and backwards. For example, "radar" and "racecar" are simple palindromes, and "Able was I ere I saw Elba" is more elaborate example (attributed, probably apocryphally, to Napolean, who was briefly exiled to the island of Elba).
Write a method that recursively generates random palindromes. The desired length of the palindrome, in characters, should be a parameter to your method.
To help you design a recursive method for generating palindromes, consider the following definition of "palindrome:"
You might find it helpful to define a string of characters that serves as the "alphabet" from which palindromes are generated, and then pick a random character out of this string whenever you need a character to place in a palindrome.
Most landscapes in computer graphics are generated as so-called "fractal terrains." This exercise introduces you to the basic idea behind these terrains.
Imagine a square patch of terrain, e.g., a piece of a hillside. This patch has certain elevations at its corners. Elevations at other points (e.g., the center of the patch, the centers of its edges) will be different from and yet related to these elevations -- for example, the elevation at the center of a patch of hillside will probably be lower than the highest corner, yet higher than the lowest corner; indeed, the center's elevation might be nicely approximated by the average of the elevations of the corners, plus or minus some random offset. The larger the patch is, the more leeway there is for the "random offset" to act -- in a square mile patch, the center might have an elevation considerably different from the elevation of the corners, in a square inch there will be much less variation. The key idea behind fractal terrain generation is thus to calculate elevations for a patch of simulated terrain by recursively dividing the terrain into four quadrants, whose corners have elevations that are the averages of the elevations of the adjacent corners of the original patch, with random offsets (which can be either positive or negative) whose size depends on the size of the original patch. More precisely, the algorithm can be thought of as follows:
Given elevations for the northeast, northwest, southeast, and southwest corners of a patch...
If the sides of the patch are long enough...
Calculate an elevation for the center of the north side as the average of the northeast
and northwest elevations, plus a random number scaled by the length of the north side
Similarly calculate elevations for the centers of the south, east, and west sides, using
distinct random numbers for each
Calculate an elevation for the center as the average of all four corner elevations, plus
a random number scaled by the length of patch's diagonal
Recursively generate elevations within the northeast quadrant, using as corner elevations
those of the northeast corner, the center of the north side, the center of the original
patch, and the center of the east side.
Similarly, recursively generate elevations within the northwest, southeast, and southwest
quadrants.A simple approach to coding this algorithm stores elevations in the cells of an n-by-n array, and identifies corners by indices in the array. A patch is then really a square section within this array, and "long enough" sides are simply sides of length more than 1 (i.e., sides whose corners aren't immediately adjacent).
Once all the cells in this array have elevations calculated, you can use the array to draw a "map" of the resulting terrain: For each cell in the array, draw a small square on the monitor. Color this square according to the elevation of the corresponding cell -- e.g., blue for negative elevations ("below sea level"), green for slightly positive ones ("low-lying forest"), brown for moderately positive ones ("mountains"), and white for the highest ("snow-capped peaks").
Using the above ideas, write Java code that draws maps of imaginary terrains. With sufficiently large arrays and small squares on the monitor for each cell (in the limit, each cell can correspond to a single pixel), you can produce tolerably realistic-looking maps. For best results, the random offsets needed by the algorithm should be taken from a normal distribution (e.g., the nextGaussian message to a Random object); multiply the value returned by nextGaussian by a scale factor that is proportional to the length of a side or diagonal, as suggested above. You will want to initialize your elevation array by manually setting elevations for its corners (at least -- for more control you could also manually set elevations for the center and the centers of the sides, and apply the algorithm separately to each quadrant).
I will grade this exercise in a face-to-face meeting with you. Make an appointment to meet with me at some time convenient for you, as long as that time is before the end of the due date above. Meetings only need to be 15 minutes long. You can make an appointment by signing up on the copy of my schedule on the bulletin board outside my office.
I would like to read and run your program during our meeting. To do this, you can either bring the program to my office on a laptop computer, or we can go to a lab during the meeting.