Java Reference
In-Depth Information
5.
Suppose that you have several numbered billiard balls on a pool table. At each step you remove a billiard ball
from the table. If the ball removed is numbered
n
, you replace it with
n
balls whose number is
n
/ 2, where the
division is truncated to an integer. For example, if you remove the 5 ball, you replace it with five 2 balls.
Write a program that simulates this process. Use a bag of positive integers to represent the balls on the pool table.
Using Big Oh notation, predict the time requirement for this algorithm when the initial bag contains only the value
n
.
Then time the actual execution of the program for various values of
n
and plot its performance as a function of
n
.
6.
Repeat the previous project, but instead replace the
n
ball with
n
balls randomly numbered less than
n
.
7.
In mythology, the Hydra was a monster with many heads. Every time the hero chopped off a head, two smaller
heads would grow in its place. Fortunately for the hero, if the head was small enough, he could chop it off without
two more growing in its place. To kill the Hydra, all our hero needed to do was to chop off all the heads.
Write a program that simulates the Hydra. Instead of heads, we will use strings. A bag of strings, then, repre-
sents the Hydra. Every time you remove a string from the bag, delete the first letter of the string and put two cop-
ies of the remaining string back into the bag. For example, if you remove
HYDRA
, you add two copies of
YDRA
to
the bag. If you remove a one-letter word, you add nothing to the bag. To begin, read one word from the keyboard
and place it into an empty bag. The Hydra dies when the bag becomes empty.
Using Big Oh notation, predict the time requirement for this algorithm in terms of the number
n
of characters
in the initial string. Then time the actual execution of the program for various values of
n
and plot its performance
as a function of
n
.
A
NSWERS
TO
S
ELF
-T
EST
Q
UESTIONS
1.
If you follow the hint given in the question, you will get the sum of
n
occurrences of
n
+
1, which is (
n
+
1)
+
(
n
+
1)
+
. . .
+
(
n
+
1). This sum is simply the product
n
(
n
+
1). To get this sum, we added 1
+
2
+
. . .
+
n
to itself. Thus,
n
(
n
+
1) is 2 (1
+
2
+
. . .
+
n
). The desired conclusion follows immediately from this fact.
2.
Algorithm A: The loop iterates
n
times, so there are
n
additions and a total of
n
+
1 assignments. We ignore the
assignments.
Algorithm B: For each value of
i
, the inner loop iterates
i
times, and so performs
i
additions and
i
assignments.
The outer loop iterates
n
times. Together, the loops perform 1
+
2
+
. . .
+
n
additions and the same number of
assignments. Using the identity given in Question 1, the number of additions is
n
(
n
+
1)
/
2. The additional assign-
ment to set
sum
to zero makes the total number of assignments equal to 1
+
n
(
n
+
1)
/
2, which we ignore.
3
n
2
+
2
n
<
2
n
+
2
n
=
2
x
2
n
when
n
8. So 3
n
2
+
2
n
=
O(2
n
), using
c
=
2 and
N
=
8.
3.
≥
n
k
.
4.
5.
The inner loop requires a constant amount of time, and so it is O(1). The outer loop is O(
n
), and so the entire com-
putation is O(
n
).
6.
Twice as fast.
7.
Four times as fast.
8.
Let's tabulate the maximum number of times the inner loop executes for various values of
index
:
index
Inner Loop Iterations
0
n
- 1
1
n
- 2
2
n
- 3
. . .
. . .
n
- 2
1
As you can see, the maximum number of times the inner loop executes is 1
+
2
+
. . .
+
n
- 1, which is
n
(
n
- 1)
/
2.
Thus, the algorithm is O(
n
2
) in the worst case.
