Java Reference
In-Depth Information
4.
The schedule of activities for a room consists of an
activity list
. Each activity has a description, a start time, and an
end time. You can add activities to the list, but they must be compatible with the other activities. Two activities are
incompatible if their time intervals overlap. Specify the ADT activity list.
5.
Imagine you are working for a geologist who has records for earthquakes that occurred during the past 50 years.
Each record includes a date, location, strength, and duration. Design and specify an ADT for this collection of data.
6.
Explain how you can use the ADT sorted list in the implementations of the ADTs described in Exercises 4 and 5.
7.
Consider an array-based implementation of the sorted list. To implement the method
add
, you must add an entry to
a sorted array so that the array remains sorted.
a.
Describe the steps in this implementation.
b.
On which sort have you based your logic?
c.
Analyze the worst-case efficiency of this implementation of
add
.
8.
Figure 16-5 tabulates the worst-case efficiencies of the sorted list operations for both array-based and linked
implementations. Derive these Big Oh expressions.
9.
Figure 16-9 tabulates the worst-case efficiencies of the sorted list operations when implemented using an instance
of the ADT list. Derive these Big Oh expressions.
10.
Consider an array-based implementation of the sorted list. Let the array
list
be the data field that represents the
list's entries. If a constructor is given an array of unsorted list entries, the constructor must place them into
list
in
sorted order. To do so, it could repeatedly use the sorted list's
add
method to add the entries to the sorted list (and
hence to the array
list
) in their proper order. Or it could copy the entries to
list
and sort them by using a sort
algorithm from Chapters 8 and 9.
a.
If you use the first approach, what sort are you actually using?
b.
Would you ever want to use the second approach? Explain.
11.
Consider the implementation of the sorted list that uses an instance of the ADT list. In particular, consider the
method
contains
. One implementation of
contains
could invoke
getPosition
(see Question 13 at the end of
Segment 16.24). Another implementation could simply invoke
list.contains
. Compare the efficiencies of these
two implementations.
12.
Write a linked implementation of the sorted list method
contains
. Your search of the chain should end when it
either locates the desired entry or passes the point at which the entry should have occurred.
13.
Compare the efficiency of the method
contains
that Exercise 12 describes with that of the list's version
of
contains
.
14.
Segment 9.2 of Chapter 9 described how to merge two sorted arrays into one sorted array. Add an operation to the
ADT sorted list that merges two sorted lists. Implement the merge in three ways, as follows:
a.
Use only sorted list operations.
b.
Assume an array-based implementation.
c.
Assume a linked implementation.
P
ROJECTS
1.
Complete the linked implementation of the ADT sorted list that was begun in this chapter. Use iteration instead of
recursion.
2.
Repeat Project 1, but use recursion wherever possible.
3.
Implement the ADT sorted list by using an array to represent the ADT's entries. Use array resizing so that the
sorted list can grow as large as necessary.
