Java Reference
In-Depth Information
21.
If
t
(1)
=
1
t
(
n
)
=
2
*
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.
22.
Consider a checkerboard that has a dollar amount printed on each of its squares. You can place a checker on the
board anywhere you want and then move it across the board with standard diagonal moves. Once you reach the other
side, you are finished. You will collect an amount of money equal to the sum of the values written on the squares that
your checker traveled over.
a.
Give a recursive algorithm that will compute the maximum amount you can collect.
b.
Give an iterative algorithm that uses a stack to compute the maximum amount you can collect.
23.
Consider the recursive method given in Segment 7.21 that displays the contents of a chain of linked nodes in
backward order. Also consider the recursive method described in Exercise 5 that displays the contents of an array
in backward order.
a.
What is the time complexity of each of these two methods, and how do they compare?
b.
Write an iterative method that displays the contents of a chain of linked nodes in backward order.
What is this method's time complexity, and how does it compare to the complexities that you com-
puted in Part
a
?
P
ROJECTS
1.
The following algorithm finds the square root of a positive number:
Algorithm
squareRoot(number, lowGuess, highGuess, tolerance)
newGuess = (lowGuess + highGuess) / 2
if
((highGuess - newGuess) / newGuess < tolerance)
return
newGuess
else if
(newGuess * newGuess > number)
return
squareRoot(number, lowGuess, newGuess, tolerance)
else if
(newGuess * newGuess < number)
return
squareRoot(number, newGuess, highGuess, tolerance)
else
return
newGuess
To begin the computation, you need a value
lowGuess
less than the square root of the number and a value
highGuess
that is larger. You can use zero as
lowGuess
and the number itself as
highGuess
. The parameter
tolerance
controls the
precision of the result independently of the magnitude of
number
. For example, computing the square root of 250 with
tolerance
equal to 0.00005 results in 15.81. This result has four digits of accuracy.
Implement this algorithm.
2.
Implement the two versions of the
solveTower
algorithm given in Segment 7.31. Represent the towers by either
single characters or strings. Each method should display directions that indicate the moves that must be made.
Insert counters into each method to count the number of times it is called. These counters can be data fields of
the class that contains these methods. Compare the number of recursive calls made by each method for various
numbers of disks.
3.
Repeat Project 5a of Chapter 5, but write a recursive implementation of the algorithm.
4.
Implement the algorithms that Exercise 22 describes.
