CS 5 Fall 2009
Lab Assignment #4
Due Wednesday, November 11

This assignment will give you practice in recursion.

You are back to working on your own.

Problem 1: A recursive power method for Java

In this problem, you will define a method public static double power(double x, int n) that returns the value of xn. The parameters x and n may each be positive, negative, or zero. Your method should be recursive, with no loop of any kind. Nor should it call any method in the Math class in any way. In fact, from the time that power is called to the time that power returns, it should execute only code that you write.

Your method should have four cases, three of which make recursive calls. The four cases should be based on the following facts, which apply to integer exponents n:

  1. When n = 0, we have x0 = 1 for all x.

  2. When n is negative, xn = 1/x–n for all x and n.

  3. When n is positive and even, xn = xn/2 * xn/2 = (xn/2)2.

  4. When n is positive and odd, xn = x(n–1)/2 * x(n–1)/2 * x = (x(n–1)/2)2 * x.
Note that for case 3, you should recursively compute xn/2 only once. Similarly, for case 4, you should recursively compute x(n–1)/2 only once. For both cases 3 and 4, do not square the result of the recursive call by calling power(..., 2), where "..." just stands for the first actual parameter of the call. Instead, use the time-honored technique of squaring a number by simply multiplying it by itself.

I have supplied a short driver program, Power.java, that allows you to test your method power. Copy it, and fill in the missing method. The driver compares your result to the result computed by the builtin method Math.pow. Don't worry about how the result is formatted; let Java's toString method format it in the way it thinks best.

Don't forget to test all the cases in your method, i.e., negative values of x and n, etc. What can you say about the efficiency of your power method? How many multiplications does your method power use to compute the value of x512? Write your response to this question to the bottom of your listing for this program. Explain how you got it (analyzed it, used a counter in your program, ran the debugger and counted, etc.).

Turn in test runs that show all the cases at work.

Problem 2: Barycentric subdivision

Finite-element methods, surface approximation in graphics, and other applications require us to subdivide a large area into small triangles. Often the subdivision must be adaptive, with the triangles in one region being smaller than those in another region. Researchers have devised several methods for this problem. One method is barycentric subdivison. A large triangle is broken into four smaller triangles by connecting the midpoints of the three sides:

We then separately consider each of the three "corner" triangles (i.e., the three triangles not in the middle), and we further subdivide each corner triangle until the triangle gets really small.

Your task is to use barycentric subdivision within an applet that takes the coordinates of the three corners of a triangle as parameters and creates the following sort of pattern:

I have provided most of the applet, which you can run here. Click three points, and a triangle is barycentrically subdivided. If you drag one of the corners of the triangle, the triangle is updated, along with its barycentric subdivision. Click three new points, and you get a new triangle and its barycentric subdivision.

Start with Barycentric.java. You have to fill in the body of the method drawBarycentric. This method should be recursive.

The base case of the recursion is when any of the edges of the triangle is shorter than 10 pixels. In this case the recursive method should return without subdividing further.

Here are a couple of simple geometric facts that you might find helpful:

  1. The distance between points p and q is the square root of ((p.x – q.x)2 + (p.y – q.y)2). The distance method, which I have provided, returns this value.

  2. The midpoint of points p and q is the point ((p.x + q.x)/2, (p.y + q.y)/2).

Hand in window snapshots from two different triangles that your program subdivides.

Problem 3: A recursive order-statistic method

The kth order statistic of a set of n elements is the kth smallest element. For example, the minimum of a set of n elements is the 1st order statistic, the maximum is the nth order statistic, and the median is the (n/2)th order statistic. In this problem, you will write a recursive method to find the kth order statistic in an array of doubles.

An easily-described way to find the kth order-statistic is to sort the array into increasing order, and return the element in the (k–1)st position. (We have to subtract 1 because arrays have 0-origin indexing.) The problem with this method is that we have to sort, and we will see later in this course that sorting n elements takes time proportional to n log2 n. (Actually, we will only see that we can achieve a time of n log2 n; you'll need to take CS 25 to see that in fact n log2 n is the best we can do unless we know something else about the values in the array.)

But there is another way to find the kth order statistic, and on average, it takes time proportional to n. (Proving this running time requires mathematics beyond the scope of CS 5.) This method saves a factor of log2 n over the sorting-based method. This faster method is recursive. It has the header

public static double select(double [] values, int p, int r, int k) A call returns the value of the kth smallest element of the subarray values[p..r], that is, the subarray of values starting at index p and ending at index r. (This subarray has r–p+1 elements.) In the initial call to this method, p is 0 and r is n–1, so that values[p..r] is the entire array. The subarray under consideration shrinks in each recursive call, i.e., the difference between p and r is smaller in each recursive call.

A given call works as follows:

  1. The base case occurs when the subarray consists of only one element. That element must be the one we want. We return its value. (We assume that if the subarrray consists of only one element, then k is 1. We don't worry about what to do if k is not 1.)

  2. The recursive case occurs when the subarray consists of more than one element. We do the following:

    1. Partition the array into subarrays values[p..q–1] and values[q+1..r] such that every element in values[p..q–1] is less than or equal to values[q], which is less than every element in values[q+1..r]. We'll see in a moment how to perform this partitioning.

    2. Determine the size of the subarray values[p..q] of "smaller" values. Let's call this size z.

    3. If z equals k, then values[q] must be the kth smallest element of values[p..r]. We return this value.

    4. Otherwise, if z is greater than k, then we know that the kth smallest element of values[p..r] must be in the subarray values[p..q–1]. In fact, it's the kth smallest element of this subarray. We find it recursively, and then we return it.

    5. Otherwise, z is less than k. There are fewer than k elements in the subarray values[p..q], and so the kth smallest element of values[p..r] must be in the subarray values[q+1..r]. But it is not the kth smallest element of values[q+1..r], since we have already ruled out the z elements of values[p..q]. What we want is the (k–z)th smallest element of values[q+1..r]. We find it recursively, and then we return it.
In past years, many CS 5 students have been confused over a few simple matters. Here are some helpful reminders:

I have supplied a driver program, Select.java, that allows you to test your method select. Copy it, and fill in the missing method. The driver asks for an array size, randomly fills the array with doubles between 0 and 1000, prints out the array, calls select, and checks the answer.

Select.java also supplies a method

private static int partition(double [] a, int p, int r) that performs the partitioning. That is, it rearranges the elements of a[p..r] into the subarrays a[p..q–1] and a[q+1..r], and it returns the index q that marks the partition. If you look at the code, you'll see that it uses some randomization in deciding how to partition. We'll examine this method later in the course, when we study the quicksort sorting algorithm.

Your job is to fill in the body of the method select and submit three test runs that show it works. Make one test run be on a short array (10 elements or less), one on a medium-sized array (between 10 and 100 elements), and one on a large array (over 100 elements).

The main method checks your answer, so that you'll see a complaint in your output if you got the wrong answer.

You'll also need to add FieldFormat.java to your project.

Extra credit

An extra credit program that you might consider is a graphical animation of the Towers of Hanoi. I will leave it up to you how you might design and implement it.

General directions for turning in your homework

  1. Turn in a clean listing (i.e., a printout of your source code) of each program.

  2. Hand in the output that we have requested. For Problem 1, also remember to discuss the number of multiplications needed by your power method to compute x512.

  3. Send a Blitz to the special homework account for your section leader containing your Java files. You have done this enough times that we will have a zero-tolerance policy for mistakes.

  4. If the timestamp on your Blitz is after 1:45 PM on Wednesday, November 11, there will be an automatic 16-point deduction. If the timestamp is after 5:00 PM on Thursday, November 12, we will not accept your assignment and you will get a 0.

  5. Package the listings and output together, all clearly marked and containing your name. Put them in an envelope that is at least 8.5 x 11 inches, and don't forget to put your name and your section leader's name on the outside of that envelope as well. We will not accept your assignment if it is not in an envelope. If you cannot afford an envelope, please see me or a TA and we will get you one. Put the envelope in the HW HANDIN box of your section leader by the start of class on November 11. If you hand it in after the start of the class on November 11, you will need to get it directly to your section leader. If you Blitz your electronic version on time but your envelope is late, there will be a 1-point deduction if we get it by 5:00 on Wednesday, or a 2-point deduction if we get it by 5:00 on Thursday. After 5:00 on Thursday, we will not accept it, and there will be a 6-point deduction.

    It is your responsibility to round up the envelope before the assignment is due.

Grading

Your section leader will grade this assignment looking for the following things:
Back to Lab Assignments
Thomas H. Cormen <thc@cs.dartmouth.edu>
Last modified: Mon Nov 9 17:27:26 2009