Java Reference
In-Depth Information
Repeat Exercise 8.21 for four numbers. Try to design an
O
(
N
2
log
N
)
algorithm. (
Hint:
Compute all possible sums of two elements, sort
these possible sums, and then proceed as in Exercise 8.21
.)
8.22
Repeat Exercise 8.21 for three numbers. Try to design an
O
(
N
2
)
algorithm.
8.23
In Exercise 5.41 you were asked to find the single integral solution to
A
5
+
B
5
+
C
5
+
D
5
+
E
5
=
F
5
with 0 <
A
8.24
N,
where
N
is 75. Use the ideas explored in Exercise 8.22 to obtain a solu-
tion relatively quickly by sorting all possible values of
A
5
+
B
5
+
C
5
and
F
5
- (
D
5
+
E
5
), and then seeing if a number in the first group is
equal to a number in the second group. In terms of
N,
how much
space and time does the algorithm require?
≤
B
≤
C
≤
D
≤
E
≤
F
≤
PROGRAMMING PROJECTS
8.25
Compare the performance of Shellsort with various increment
sequences, as follows. Obtain an average time for some input size
N
by generating several random sequences of
N
items. Use the same
input for all increment sequences. In a separate test obtain the average
number of
Comparable
comparisons and
Comparable
assignments. Set
the number of repeated trials to be large but doable within 1 hour of
CPU time. The increment sequences are
a.
Shell's original sequence (repeatedly divide by 2).
b.
Shell's original sequence, adding 1 if the result is nonzero but
even.
c.
Gonnet's sequence shown in the text, with repeated division by
2.2.
d.
Hibbard's increments: 1, 3, 7,
…
,
2
k
-
1
.
e.
Knuth's increments: 1, 4, 13,
…
,
(
3
k
-
1
)
⁄
2
.
f.
Sedgewick's increments: 1, 5, 19, 41, 109,
…
, with each term
having the form of either
94
k
⋅
-
92
k
⋅
+
1
or
4
k
-
32
k
⋅
+
1
.
Code both Shellsort and quicksort and compare their running times.
Use the best implementations in the text and run them on
a.
8.26
Integers
b.
Real numbers of type
double
c.
Strings
Write a method that removes all duplicates in an array
A
of
N
items.
Return the number of items that remain in
A
. Your method must run in
O
(
N
log
N
) average time (use quicksort as a preprocessing step), and
should make no use of the Collections API.
8.27
Search WWH ::
Custom Search