Java Reference
In-Depth Information
8.
A palindrome is a string that reads the same forward and backward. For example
deed
and
level
are palindromes.
Write an algorithm in pseudocode that tests whether a string is a palindrome. Implement your algorithm as a static
method in Java. Exercise 11 and Project 1 in Chapter 5 asked you to describe how to do this using a stack.
9.
Segment 7.37 introduced the Fibonacci sequence. Computing this sequence recursively is inefficient and takes too
much time. Write two methods that each compute the
n
th
term in the Fibonacci sequence by using iteration instead
of recursion. One method should use an array to store the Fibonacci numbers. The other method should use three
variables to contain the current term in the sequence and the two terms before it.
What is the Big Oh for each of your iterative methods? Compare these results with the performance of the
recursive algorithm.
10.
For three disks, how many recursive calls are made by each of the two
solveTowers
algorithms given in Segment 7.31?
11.
Write a recursive method that counts the number of nodes in a chain of linked nodes.
12.
If
n
is a positive integer in Java,
n
%
10
is its rightmost digit and
n
/
10
is the integer obtained by dropping the
rightmost digit from
n
. Using these facts, write a recursive method that displays an integer
n
in decimal. Now
observe that you can display
n
in any base between 2 and 9 by replacing 10 with the new base. Revise your
method to accommodate a given base.
13.
Consider the method
getFrequencyOf
in the class
ArrayBag
, as given in Segment 2.17 of Chapter 2. Write a pri-
vate recursive method that
getFrequencyOf
can call, and revise the definition of
getFrequencyOf
accordingly.
14.
Repeat Exercise 13, but instead use the class
LinkedBag
and the method
getFrequencyOf
in Segment 3.16 of Chapter 3.
15.
Write four different recursive methods that each compute the sum of integers in an array of integers. Model your
methods after the
displayArray
methods given in Segments 7.15 through 7.18 and described in Question 5.
16.
Write a recursive method that returns the smallest integer in an array of integers. If you divide the array into two pieces—
halves, for example—and find the smallest integer in each of the two pieces, the smallest integer in the entire array will be
the smaller of the these two integers. Since you will be searching a portion of the array—for example, the elements
array[first]
through
array[last]
—it will be convenient for your method to have three parameters: the array and two
indices,
first
and
last
. You can refer to the method
displayArray
in Segment 7.18 for inspiration.
17.
Trace the call
f(16)
to the following method by showing a stack of activation records:
public int
f(
int
n)
{
int
result = 0;
if
(f <= 4)
result = 1;
else
result = f(n / 2) + f(n / 4);
return
result;
}
// end f
18.
Write a recursive algorithm in pseudocode that finds the second smallest object in an array of
Comparable
objects.
Implement your algorithm as a static method in Java.
19.
Consider the class
ArrayBag
, as given in Chapter 2. Implement the method
equals
for
ArrayBag
so that it calls a
private recursive method.
20.
If
t
(1)
=
2
t
(
n
)
=
1
+
t
(
n
-
1) for
n
>
1
find an expression for
t
(
n
) that is not given in terms of itself. Prove that your result is correct by using induction.
