Java Reference
In-Depth Information
For example, the string “((())())()” contains properly nested pairs of paren-
theses, but the string “)()(” does not; and the string “())” does not contain
properly matching parentheses.
(a) Give an algorithm that returns
true
if a string contains properly nested
and balanced parentheses, and
false
if otherwise. Hint: At no time
while scanning a legal string from left to right will you have encoun-
tered more right parentheses than left parentheses.
(b) Give an algorithm that returns the position in the string of the first of-
fending parenthesis if the string is not properly nested and balanced.
That is, if an excess right parenthesis is found, return its position; if
there are too many left parentheses, return the position of the first ex-
cess left parenthesis. Return 1 if the string is properly balanced and
nested.
1.16 A graph consists of a set of objects (called vertices) and a set of edges, where
each edge connects two vertices. Any given pair of vertices can be connected
by only one edge. Describe at least two different ways to represent the con-
nections defined by the vertices and edges of a graph.
1.17 Imagine that you are a shipping clerk for a large company. You have just
been handed about 1000 invoices, each of which is a single sheet of paper
with a large number in the upper right corner. The invoices must be sorted by
this number, in order from lowest to highest. Write down as many different
approaches to sorting the invoices as you can think of.
1.18 How would you sort an array of about 1000 integers from lowest value to
highest value? Write down at least five approaches to sorting the array. Do
not write algorithms in Java or pseudocode. Just write a sentence or two for
each approach to describe how it would work.
1.19 Think of an algorithm to find the maximum value in an (unsorted) array.
Now, think of an algorithm to find the second largest value in the array.
Which is harder to implement? Which takes more time to run (as measured
by the number of comparisons performed)? Now, think of an algorithm to
find the third largest value. Finally, think of an algorithm to find the middle
value. Which is the most difficult of these problems to solve?
1.20 An unsorted list allows for constant-time insert by adding a new element at
the end of the list. Unfortunately, searching for the element with key value X
requires a sequential search through the unsorted list until X is found, which
on average requires looking at half the list element. On the other hand, a
sorted array-based list of n elements can be searched in log n time with a
binary search. Unfortunately, inserting a new element requires a lot of time
because many elements might be shifted in the array if we want to keep it
sorted. How might data be organized to support both insertion and search in
log n time?
