Java Reference
In-Depth Information
4.
Implement the ADT sorted list by using an instance of
Vector
to represent the ADT's entries. Recall that Chapter 13
presented a similar implementation for the ADT list.
5.
Exercise 2 asked you to specify an ADT sorted list of unique items. Implement such an ADT using one of the
approaches described in this chapter or in the previous projects.
6.
Add an iterator to the ADT sorted list by defining an inner class within the class that implements the ADT.
7.
A
polynomial
in
x
is an algebraic expression that involves integer powers of
x
, as follows:
P
(
x
)
=
a
n
x
n
+
a
n
-1
x
n
-1
+
. . .
+
a
1
x
+
a
0
The
a
's are called
coefficients
. The
degree
of the polynomial is
n
, the highest exponent of
x
that appears in
P
(
x
).
Although
a
n
cannot be zero in a degree
n
polynomial, any other coefficient can be zero.
Specify an ADT polynomial that includes operations such as
getDegree
,
getCoefficient
,
setCoefficient
,
add
,
and
subtract
. Implement this ADT by using a sorted list. The sorted list should not contain any coefficients that are zero.
8.
Exercise 3 asked you to create an algorithm to find the mode of a sorted list. Let's add a method to the
implementation of a sorted list that finds the list's mode. The header of such a method could be
public
T mode()
Implement this method in three ways, as follows:
a.
Use only sorted list operations.
b.
Assume an array-based implementation.
c.
Assume a linked implementation.
9.
You can use a
substitution code
to encode a message. In this scheme, a
key
maps each letter to another letter. Each
letter in the
plain-text
message is replaced according to the key to produce the encoded message, or
cipher text
.
Suppose you are given some cipher text, but not the key. One method of breaking such a code is to count the fre-
quency of letters in the cipher text and then make guesses about the mapping based on the frequencies of letters in typical
English text. Write a program that reads characters from a file and uses a sorted list to find the frequency of each letter.
10.
Implement the ADT priority queue by using a sorted list to contain the priority queue's entries.
11.
Project 1 of Chapter 1 defines a set as a bag that does not allow duplicate entries. Implement the ADT set by using
a sorted list to contain its entries. Include the operations union, intersection, and difference, as described
respectively in Exercises 5, 6, and 7 of Chapter 1.
12.
In certain computer networks, a message is not sent as a continuous stream of data. Instead, it is divided into
pieces, called
packets
, and sent a packet at a time. The packets might not arrive at their destination in the same
order as the one in which they were sent. To enable the receiver to assemble the packets in their correct order, each
packet contains a sequence number.
For example, to send the message “Meet me at 6 o'clock” three characters at a time, the packets would appear
as follows:
1 Mee
2 t m
3 e a
4 t 6
5 o'
6 clo
7 ck
Regardless of when the packets arrive, the receiver can order the packets by their sequence numbers to determine
the message.
Given a text file containing the packets of data in the order they were received, write an application that reads the
file and extracts the message by using a sorted list. Design and create auxiliary classes such as
Packet
and
Message
.
