Java Reference
In-Depth Information
4.
Consider an array
data
of
n
numerical values in sorted order and a list of numerical target values. Your goal is to
compute the smallest range of array indices that contains all of the target values. If a target value is smaller than
data[0]
, the range should start with
-
1. If a target value is larger than
data[n - 1]
, the range should end with
n
.
For example, given the array in Figure 18-10 and the target values (8, 2, 9, 17), the range is
-
1 to 5.
a.
Devise an efficient algorithm that solves this problem.
b.
If you have
n
data values in the array and
m
target values in the list, what is the Big Oh performance of
your algorithm?
c.
Implement and test your algorithm.
FIGURE 18-10
An array for Project 4
5
8
10
13
15
20
22
26
0
1
2
3
4
5
6
7
5.
One way to organize a collection of words is to use an array of sorted lists. The array contains one sorted list for
each letter of the alphabet. To add a word to this data structure, you add it to the sorted list that corresponds to the
word's first letter. Design an ADT for such a collection, including the operations
add
and
contains
. Define a Java
interface for your ADT. Then implement your interface as a class and test it. Use a text file of words to populate
your data structure.
A
NSWERS
TO
S
ELF
-T
EST
Q
UESTIONS
1.
public int
contains(T anEntry)
{
boolean
found =
false
;
int
result = -1;
for
(
int
index = 0; !found && (index < numberOfEntries); index++)
{
if
(anEntry.equals(list[index]))
{
found =
true
;
result = index;
}
// end if
}
// end for
return
result;
}
// end contains
2.
public static
<T>
boolean
contains(AList<T> theList, T anEntry)
{
boolean
found =
false
;
int
length = theList.getLength();
for
(
int
position = 1; !found && (position <= length); position++)
{
if
(anEntry.equals(theList.getEntry(position)))
found =
true
;
}
// end for
return
found;
}
// end contains
3.
The object o is compared with o1, then o2, o3, o4, and o5.
