CONCEPT EXERCISES
5.1 What is wrong with the following underlying method for calculating factorials?
/**
* Calculates the factorial of a non-negative integer, that is, the product of all
* integers between 1 and the given integer, inclusive. The worstTime(n) is O(n),
* where n is the given integer.
*
* @param n the non-negative integer whose factorial is calculated.
*
* @return the factorial of n
*
*/
public static long fact (int n)
{
if (n <= 1)
return 1;
return fact (n+1) / (n+1);
} // fact Get the solution of 5.1
5.2 Show the first three steps in an execution-frames trace of the move method after an initial call of
move (4, 'A', 'B', 'C'); Get the solution of 5.2
5.3 Perform an execution-frames trace to determine the output from the following incorrect version of the recPermute method (from Lab 9) after an initial call to permute ("ABC");
invokes recPermute ([‘A’, ‘B’, ‘C’], 0);
/**
* Finds all permutations of a subarray from a given position to the end of the array.
*
* @param c an array of characters
* @param k the starting position in c of the subarray to be permuted.
*
* @return a String representation of all the permutations.
*
*/
public static String recPermute (char[ ] c, int k)
{
if (k == c.length - 1)
return String.valueOf (c) + "\n";
else
{
String allPermutations = new String();
char temp;
for (int i = k; i < c.length; i++)
{
temp = c [i];
c [i] = c [k + 1];
c [k + 1] = temp;
allPermutations += recPermute (String.valueOf (c).toCharArray(), k+1);
} // for
return allPermutations;
} // else
} // method recPermute Get the solution of 5.3
5.4 Perform an execution-frames trace to determine the output from the following incorrect version of the recPermute method (from Lab 9) after an initial call to permute ("ABC");
invokes recPermute ([‘A’, ‘B’, ‘C’], 0);
/**
* Finds all permutations of a subarray from a given position to the end of the array.
*
* @param c an array of characters
* @param k the starting position in c of the subarray to be permuted.
*
* @return a String representation of all the permutations.
*
*/
public static String recPermute (char[ ] c, int k)
{
if (k == c.length - 1)
return String.valueOf (c) + "\n";
else
{
String allPermutations = new String();
char temp;
for (int i = k; i < c.length; i++)
{
allPermutations += recPermute (String.valueOf (c).toCharArray(), k+1);
temp = c [i];
c [i] = c [k];
c [k] = temp;
} // for
return allPermutations;
} // else
} // method recPermute Get the solution of 5.4
5.5 Use the Principle of Mathematical Induction (Appendix 1) to prove that the move method in the Towers of Hanoi example is correct, that is, for any integern > = 1, move (n, orig, dest, temp) returns the steps to move n disks from pole orig to pole dest.
Hint: for n = 1, 2, 3, . . . , let Sn be the statement: move (n, orig, dest, temp) returns the steps to move n disks from any pole orig to any other pole dest.
a. base case. Show that S1 is true.
b. inductive case. Let n be any integer greater than 1 and assume Sn−1 is true. Then show that Sn is true.
According the code of the move method, what happens when move (n, orig, dest, temp) is
called and n is greater than 1? Get the solution of 5.5
5.6 In an execution trace of the move method in the Towers of Hanoi application, the number of steps is equal to the number of recursive calls to the move method plus the number of direct moves. Because each call to the move method includes a direct move, the number of recursive calls to the move method is always one less than the number of direct moves. For example, in the execution trace shown in the chapter, n = 3. The total number of calls to move is 2n − 1 = 7. Then the number of recursive calls to move is 6, and the number of direct moves is 7, for a total of 13 steps (recall that we started at Step 0, so the last step is Step 12). How many steps would there be for an execution trace with n = 4? Get the solution of 5.6
5.7 Show that, for the recursive binarySearch method, averageTime(n) is logarithmic in n for a successful search.
Hint: Let n represent the size of the array to be searched. Because the average number of calls is a nondecreasing function of n, it is enough to show that the claim is true for values of n that are one less than a power of 2. So assume that n = 2k − 1, for some positive integer k.
In a successful search, one call is sufficient if the item sought is half-way through the region to be searched; two calls are needed if the item sought is one-fourth or three-fourths of the way through that region; three calls are needed if the item sought is one-eighth, three-eighths, five-eighths or seven-eighths of the way through the region;
and so on.
The total number of calls for all successful searches is
(1 ∗ 1) + (2 ∗ 2) + (3 ∗ 4) + (4 ∗ 8) + (5 ∗ 16) + ·· ·+(k ∗ 2k−1)
The average number of calls, and hence an estimate of averageTime(n), is this sum divided by n. Now use the result from Exercise 2.6 of Appendix 2 and the fact that
k = log2 (n + 1) Get the solution of 5.7
5.8 If a call to the binarySearch method is successful, will the index returned always be the smallest index of an item equal to the key sought? Explain. Get the solution of 5.8
PROGRAMMING EXERCISES
5.1 Develop an iterative version of the getBinary method in Section 5.3. Test that method with the same BinaryTest class (available on the book’s website) used to test the recursive version. Get the solution of 5.1
5.2 Develop an iterative version of the permute method (from Lab 9). Here is the method specification:
/**
* Finds all permutations of a specified String.
*
* @param s - the String to be permuted.
*
* @return a String representation of all the permutations, with a line separator
* (that is, "\n") after each permutation.
*/
public static String permute (String s)
For example, if the original string is “BADCGEFH”, the value returned would be
ABCDEFGH
ABCDEFHG
ABCDEGFH
ABCDEGHF
ABCDEHFG
and so on. Test your method with the same PermuteTest method developed in Lab 9 to test the recursive version.
Hint: One strategy starts by converting s to a character array c. Then the elements in c can be easily
swapped with the help of the index operator, [ ]. To get the first permutation, use the static method sort in the Arrays class of java.util. To give you an idea of how the next permutation can be constructed from the current permutation, suppose, after some permutations have been printed,
c = ['A', 'H', 'E', 'G', 'F', 'D', 'C', 'B']
What is the smallest index whose character will be swapped to obtain the next permutation? It is index 2, because the characters at indexes 3 through 7 are already in reverse alphabetical order: ‘G’ > ‘F’ > ‘D’ > ‘C’ > ‘B’. We swap ‘E’ with ‘F’, the smallest character greater than ‘E’ at an index greater than 2. After swapping, we have c = ['A', 'H', 'F', 'G', 'E', 'D', 'C', 'B']
We then reverse the characters at indexes 3 through 7 to get those characters into increasing order:
c = ['A', 'H', 'F', 'B', 'C', 'D', 'E', 'G'], the next higher permutation after ‘A’, ‘H’, ‘E’, ‘G’, ‘F’, ‘D’, ‘C’, ‘B’.
Here is an outline:
public static String permute (String s)
{
int n = s.length();
boolean finished = false;
char[ ] c = s.toCharArray();
String perms = "";
Arrays.sort (c); // c is now in ascending order
while (!finished)
{
perms += String.valueOf (c));
// In 0 ... n-1, find the highest index p such that
// p = 0 or c [p - 1] < c [p].
...
if (p == 0)
finished = true;
else
{
// In p ... n-1, find the largest index i such that c [i] > c [p - 1].
...
// Swap c [i] with c [p - 1].
// Swap c [p] with c [n-1], swap c [p+1] with c[n-2],
// swap c [p+2] with c [n-3], ...
...
} // else
} // while
return perms;
} // method permute
In the above example, p - 1 = 2 and i = 4, so c [p - 1], namely, ‘E’ is swapped with c [i],
namely, ‘F’.
Explain how strings with duplicate characters are treated differently in this method than in the recursive version. Get the solution of 5.2
5.3 Given two positive integers i and j, the greatest common divisor of i and j, written
gcd (i, j) is the largest integer k such that (i % k = 0) and (j % k = 0).
For example, gcd (35, 21) = 7 and gcd (8, 15) = 1. Test and develop a wrapper method and a wrapped
recursive method that return the greatest common divisor of i and j. Here is the method specification for the wrapper method:
/**
* Finds the greatest common divisor of two given positive integers
*
* @param i – one of the given positive integers.
* @param j – the other given positive integer.
* @return the greatest common divisor of iand j.
*
* @throws IllegalArgumentException – if either i or j is not a positive integer.
*
*/
public static int gcd (int i, int j)
Big hint: According to Euclid’s algorithm, the greatest common divisor of i and j is j if i % j = 0. Otherwise,
the greatest common divisor of i and j is the greatest common divisor of j and (i % j). Get the solution of 5.3
5.4 A palindrome is a string that is the same from right-to-left as from left-to-right. For example, the following
are palindromes:
ABADABA
RADAR
OTTO
MADAMIMADAM
EVE
For this exercise, we restrict each string to upper-case letters only. (You are asked to remove this restriction in the next exercise.)
Test and develop a method that uses recursion to check for palindromes. The only parameter is a string that is to be checked for palindromity. The method specification is
/**
* Determines whether a given string of upper-case letters is a palindrome.
* A palindrome is a string that is the same from right-to-left as from left-to-right.
*
* @param s – (a reference to) the given string
*
* @return true – if the string s is a palindrome; otherwise, false.
*
* @throws NullPointerException – if s is null.
* @throws IllegalArgumentException – if s is the empty string.
*
*/
public static boolean isPalindrome (String s) Get the solution of 5.4
5.5 Expand the recursive method (and test class) developed in Programming Exercise 5.4 so that, in testing to see whether s is a palindrome, non-letters are ignored and no distinction is made between upper-case and lower-case letters. Throw IllegalArgumentException if s has no letters. For example, the following are palindromes:
Madam, I’m Adam.
Able was I ’ere I saw Elba.
A man. A plan. A canal. Panama!
Hint: The toUpperCase() method in the String class returns the upper-case String corresponding to
the calling object. Get the solution of 5.5
5.6 .a. Test and develop a wrapper method power and an underlying recursive method that return the result of integer exponentiation. The method specification of the wrapper method is
/**
* Calculates the value of a given integer raised to the power of a second integer.
* The worstTime(n) is O(n), where n is the second integer.
*
* @param i – the base integer (to be raised to a power).
* @param n – the exponent (the power i is to be raised to).
*
* @return the value of i to the nth power.
*
* @throws IllegalArgumentException – if n is a negative integer or if i raised to
* to the n is greater than Long.MAX_VALUE.
*
*/
public static long power (long i, int n)
Hint: We define 00 = 1, so for any integer i , i 0 = 1. For any integers i> 0 and n > 0,
i n = i∗i n−1
b. Develop an iterative version of the power method.
c. Develop an underlying recursive version called by the power method for which worstTime(n) is logarithmic in n.
Hint: If n is even, power (i, n) = power (i * i, n/2); if n is odd, power (i, n) = i *
in - 1 = i * power (i * i, n/2).
For testing parts b and c, use the same test suite you developed for part a. Get the solution of 5.6
5.7 Test and develop a recursive method to determine the number of distinct ways in which a given amount of money in cents can be changed into quarters, dimes, nickels, and pennies. For example, if the amount is 17 cents, then there are six ways to make change:
1 dime, 1 nickel and 2 pennies;
1 dime and 7 pennies;
3 nickels and 2 pennies;
2 nickels and 7 pennies;
1 nickel and 12 pennies;
17 pennies.
Here are some amount/ways pairs. The first number in each pair is the amount, and the second number is the number of ways in which that amount can be changed into quarters, dimes, nickels and pennies:
17 6
5 2
10 4
25 13
42 31
61 73
99 213
/**
* Calculates the number of ways that a given amount can be changed
* into coins whose values are no larger than a given denomination.
*
* @param amount – the given amount.
* @param denomination – the given denomination (1 = penny,
* 2= nickel, 3 = dime, 4 = quarter).
*
* @return 0 – if amount is less than 0; otherwise, the number of ways
* that amount can be changed into coins whose values are no
* larger than denomination.
*
*/
public static int ways (int amount, int denomination)
For the sake of simplifying the ways method, either develop an enumerated type Coin or develop a coins method that returns the value of each denomination. Thus, coins (1) returns 1, coins (2) returns 5, coins (3) returns 10, and coins (4) returns 25.
Hint: The number of ways that one can make change for an amount using coins no larger than a quarter is equal to the number of ways that one can make change for amount—25 using coins no larger than a quarter plus the number of ways one can make change for amount using coins no larger than a dime. Get the solution of 5.7
5.8 Modify the maze-search application to allow an end user to enter the maze information directly, instead of in a file. Throw exceptions for incorrect row or column numbers in the start and finish positions. Get the solution of 5.8
5.9 Modify the maze-search application so that diagonal moves would be valid.
Hint: only the MazeIterator class needs to be modified. Get the solution of 5.9
