The collections api - Data Structures and Problem Solving Using Java - page 282

IN THEORY
6.2

Consider the following method, whose implementation is not shown:

// Precondition: Collection c represents a Collection of
// other Collections.
// c is not null; none of the collections are null
// str is not null
// Postcondition: returns the number of occurrences of
// String str in c.
public static
int count( Collection<Collection<String>> c, String str )

a. Provide an implementation of count .

b. Assume that Collection c contains N collections and that each of

those collections contains N objects. What is the running time of
count , as written in part (a)?

c. Suppose it takes 2 milliseconds to run count when N (specified) is

100. Assuming low-order terms are negligible, how long will it
take to run count when N is 300?

Can all of the following be supported in logarithmic time: insert ,
deleteMin , deleteMax , findMin , and findMax ?

6.3

Which of the data structures in Figure 6.43 lead to sorting algorithms
that could run in less than quadratic time (by inserting all items into
the data structure and then removing them in order)?

6.4

Show that the following operations can be supported in constant time
simultaneously: push , pop , and findMin . Note that deleteMin is not part
of the repertoire. Hint : Maintain two stacks—one to store items and
the other to store minimums as they occur.

6.5

A double-ended queue supports insertions and deletions at both the
front and end of the line. What is the running time per operation?

6.6

IN PRACTICE
6.7

Write a routine that uses the Collections API to print out the items in
any Collection in reverse order. Do not use a ListIterator .

Show how to implement a stack efficiently by using a List as a data
member.

6.8

Show how to implement a queue efficiently by using a List as a data
member.

6.9