Java Reference
In-Depth Information
4.17 Write a recursive algorithm to compute the value of the recurrence relation
T(n) = T(dn=2e) + T(bn=2c) + n;
T(1) = 1:
Then, rewrite your algorithm to simulate the recursive calls with a stack.
4.18 Let Q be a non-empty queue, and let S be an empty stack. Using only the
stack and queue ADT functions and a single element variable X, write an
algorithm to reverse the order of the elements in Q.
4.19 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.
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
otherwise. Use a stack to keep
track of the number of left parentheses seen so far. 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. Use a stack to keep track of the number and positions of left
parentheses seen so far.
4.20 Imagine that you are designing an application where you need to perform
the operations
Insert
,
DeleteMaximum
, and
DeleteMinimum
. For
this application, the cost of inserting is not important, because it can be done
off-line prior to startup of the time-critical section, but the performance of
the two deletion operations are critical. Repeated deletions of either kind
must work as fast as possible. Suggest a data structure that can support this
application, and justify your suggestion.
What is the time complexity for
each of the three key operations?
4.21 Write a function that reverses the order of an array of n items.
4.7
Projects
4.1 A deque (pronounced “deck”) is like a queue, except that items may be added
and removed from both the front and the rear. Write either an array-based or
linked implementation for the deque.
