Java Reference
In-Depth Information
than 10,000 of the array values are non-zero. Describe two different imple-
mentations for such arrays that would be more space efficient than a standard
two-dimensional array implementation requiring one million positions.
1.7 Imagine that you have been assigned to implement a sorting program. The
goal is to make this program general purpose, in that you don't want to define
in advance what record or key types are used. Describe ways to generalize
a simple sorting algorithm (such as insertion sort, or any other sort you are
familiar with) to support this generalization.
1.8 Imagine that you have been assigned to implement a simple sequential search
on an array. The problem is that you want the search to be as general as pos-
sible. This means that you need to support arbitrary record and key types.
Describe ways to generalize the search function to support this goal. Con-
sider the possibility that the function will be used multiple times in the same
program, on differing record types. Consider the possibility that the func-
tion will need to be used on different keys (possibly with the same or differ-
ent types) of the same record. For example, a student data record might be
searched by zip code, by name, by salary, or by GPA.
1.9 Does every problem have an algorithm?
1.10 Does every algorithm have a Java program?
1.11 Consider the design for a spelling checker program meant to run on a home
computer. The spelling checker should be able to handle quickly a document
of less than twenty pages. Assume that the spelling checker comes with a
dictionary of about 20,000 words. What primitive operations must be imple-
mented on the dictionary, and what is a reasonable time constraint for each
operation?
1.12 Imagine that you have been hired to design a database service containing
information about cities and towns in the United States, as described in Ex-
ample 1.2. Suggest two possible implementations for the database.
1.13 Imagine that you are given an array of records that is sorted with respect to
some key field contained in each record. Give two different algorithms for
searching the array to find the record with a specified key value. Which one
do you consider “better” and why?
1.14 How would you go about comparing two proposed algorithms for sorting an
array of integers? In particular,
(a) What would be appropriate measures of cost to use as a basis for com-
paring the two sorting algorithms?
(b) What tests or analysis would you conduct to determine how the two
algorithms perform under these cost measures?
1.15 A common problem for compilers and text editors is to determine if the
parentheses (or other brackets) in a string are balanced and properly nested.
