1. (12 points) Weiss problem 5.15, fragments 1-4 only, part (a) only for each fragment. P 194-195
2. (12 points) Weiss Exercise 5.21 (Worst-case running time for each part).
3. (15 points) Weiss Exercise 6.5. Be sure to begin thinking about this one early. You may have to come back to it a few times before you figure out what to do. P 247. Here is a longer explanation:
The goal of this problem is to implement a collection data type that provides three operations and does them efficiently:
push(obj); adds obj to the collection.
obj = pop(); removes and returns the most recently-added object.
obj = findMin(); returns the smallest object (assume that all
of the objects in the collection are comparable).
A single stack
can do the first two operations in constant time, but not the third.
But if our implementation uses TWO stacks to represent a collection,
it is possible to do each of the three operations in constant time.
Is should be obvious that our new data structure's push
method will have to do more work (than the push operation for
an ordinary stack would have to do) in order for findMin to
also be a constant-time operation. All you need to do is show the
code for a constructor and the three operations. You may assume that
there is already a Stack class that has its own push, pop, and top
methods. The code for each of the three methods that you must
provide is short. I hope that by making things a bit more specific,
it will make it easier for you to get started on this problem.
To further assist you in understanding this problem, I am giving you
a framework in which your answers could go: A class declaration with
stubs for the three methods you are supposed to write. Each of
those methods should be constant time (no loops or recursion)
public
class
StackWithMin<E> {
private Stack<E>
public
StackWithMin() {
this.stack1
=
new
Stack<E>();
this.stack2
=
new
Stack<E>();
}
public
void
push(E element) {
/* You fill in the details */
}
public
E pop() {/*
You fill in the details */
}
public
E findMin() {/*
You fill in the details */
}
}