Java Reference
In-Depth Information
figure 5.15
Return a String
representation of an
array.
public static String toString( Object [ ] arr )
{
String result = " [";
for( String s : arr )
result += s + " ";
result += "]";
return result;
}
PROGRAMMING PROJECTS
5.40
The Sieve of Eratosthenes is a method used to compute all primes
less than
N
. Begin by making a table of integers 2 to
N
. Find the
smallest integer,
i
, that is not crossed out. Then print
i
and cross out
i
,
2
i
, 3
i
, . . . When , the algorithm terminates. The running time
has been shown to be . Write a program to implement
the Sieve and verify the running time claim. How difficult is it to dif-
ferentiate the running time from
i
>
N
ON
(
log
log
N
)
O
(
N
)
and
O
(
N
log
N
)
?
The equation has exactly one integral
solution that satisfies . Write a pro-
gram to find the solution.
Hint:
First, precompute all values of
and store them in an array. Then, for each tuple , you
only need to verify that some
F
exists in the array. (There are several
ways to check for
F
, one of which is to use a binary search to check
for
F
. Other methods might prove to be more efficient.)
A
5
+++ +
B
5
C
5
D
5
E
5
=
F
5
5.41
0
<
ABCDEF
75
≤≤≤ ≤≤≤
X
5
(
ABCDE
,,, ,
)
Suppose we modify the code in Figure 5.5 by adding the following
lines immediately after line 15:
5.42
if( thisSum < 0 )
break;
This modification is suggested in the text and avoids examining any
sequence that begins with a negative number.
a.
If all the numbers in the array are positive, what is the running
time of the resulting algorithm?
b.
If all the numbers in the array are negative, what is the running
time of the resulting algorithm?
c.
Suppose all the numbers are integers uniformly and randomly
distributed between -50 and 49, inclusive. Write a test program to
Search WWH ::
Custom Search