Lab 4: Recursion 'Power'

Copyright RIT 2007
$Id: writeup.xml,v 1.17 2009/09/25 13:38:54 vcss233 Exp $

Goal

The primary purpose of this lab is to give you some experience writing programs that utilize recursion.

Overview

Ask Dr. Tiger

Objectives

Pre - Lab Work

  1. Read chapter 3.5 in the Goodrich and Tamassia book.

  2. Review your class notes.

  3. Read some facts about the Tower of Hanoi from http://www.lhs.berkeley.edu/java/tower/towerhistory.html

  4. See an example of the Tower of Hanoi http://www.lhs.berkeley.edu/java/tower/tower.html

In-Lab Activities

Each lab you will do is separated into a set of activities. Each activity has specific deliverables you must submit for credit and each activity is graded separately.

Activity #1

In this activity you will write a recursive program that calculates m to the nth power. Instead of directly using the Math.pow() function or iteratively multiplying m n times, you will compute the result recursively by performing successive multiplication operations. Your program must obtain the numbers m and n from the command line. If the program invocation has the wrong number of command line arguments, it shall print the following error message on standard error and terminate: 

Usage: java MToTheNth m n

The name of the class you will write to implement this program is MToTheNth. The main method of this class processes the command line arguments and then calls a method, mToTheNth(), that uses recursion to compute the power. The declaration for the method mToTheNth() is given below: 

private static int mToTheNth( int m, int n )

Before calling the method mToTheNth(), the program first checks to see if m is a positive integer, and if n is non-negative. The base, m, must be greater than 0, and the exponent must be greater than -1. If n is 0, the result is 1 and the method returns. Otherwise, if n is not 0, compute the result by multiplying m by the result of calling mToTheNth with m and n-1.

Before calling the recursive method, print the math expression the recursion will solve. For example, the program would print 

2 * 2 * 2 =

prior to printing the result of the call to mToTheNth( 2, 3 ).

You will not receive credit if you do not use recursion for both computing the result and printing the multiplied numbers.

The output of your program must be formatted as shown in the sample runs below: 


% java MToTheNth 
Usage: java MToTheNth m n 

% java MToTheNth abc 3
Invalid argument For input string: "abc"
 
% java MToTheNth -1 3
Arguments may not be negative: -1 is incorrect.
 
% java MToTheNth 1 -3
Arguments may not be negative: -3 is incorrect.
 
% java MToTheNth -1 -3
Arguments may not be negative: -1 and -3 are incorrect.
 
% java MToTheNth 2 5 
2 * 2 * 2 * 2 * 2 = 32 

% java MToTheNth 5 0 
1

% java MToTheNth 5 1 
5 = 5

NOTE: The error message in the second example above is correct. The "For" is capitalized. That part of the error message comes from the exception produced by Integer.parseInt(); your program must add the prefix text.

How To Submit

When you are convinced that your program is correct, submit your work using the following command: 


	try grd-233 lab4-1 MToTheNth.java

Activity #2

The "power set" is a set containing all its possible subsets. For example, the power set of { x, y } is { {}, {x}, {y}, {x, y} }, using brace notation for the sets.

In this activity you will write a program that takes a set of strings from the command line and prints the power set of those strings. The PowerSet program will use string notation for the power set members. The empty string, "", will represent the null set, and the string "a" represents the set containing the letter a. The concatenation of strings will represent other subsets. For example, the subset composed of sets "a" and "b" would be "ab".

Fetch the required materials from http://www.cs.rit.edu/~vcss233/pub/lab04/Binaries/lab4.jar and unpack the jar.

Below are sample runs of the program showing the required output of the PowerSet program: 


% java PowerSet 
{ "" }
 
% java PowerSet x
{ "", x }
 
% java PowerSet a b
{ "", a, b, ab }

% java PowerSet a b c
{ "", a, b, c, ab, ac, bc, abc }

To ensure a consistent order of output, this lab includes a PowerComparator to use with the collection of subsets. The comparator is in the lab jar file.

Your solution must use recursion. You may use the collections in java.util.

One way to generate the power set is outlined below:

Concrete examples are in the example outputs earlier. Here are some more illustrations of the process of generating power sets.

The input set { b } generates the power set { "", b }.

If { a, b } is the input set, generate the power set as follows: 


generate s2, the power set of (input set minus first item) ==> { "", b } 
generate s3, the concatenation of "a" to each item in s2   ==> { a, ab }
result set returned is the union of s2 and s3              ==> { "", a, b, ab }
(the comparator sorts the result set returned.)

The class that you will write to implement this program will be named PowerSet. The PowerSet program will also be structured recursively; the main method processes the command line arguments and then calls a method to compute the power set. You may also find it useful to have some helper methods.

How To Submit

After you have tested your program, and are sure that it works, submit it using the following command: 


	try grd-233 lab4-2 PowerSet.java

Grade Computation

Grade Breakdown: