ICS 261 -- Spring 2009 -- Homework 1, due Friday, January 23.

Recall from the lecture that the amortized time of an operation in a
data structure may be defined by specifying a potential function Phi
that maps states of the data structure to numbers, with Phi(x) >= 0 for
any state x and with Phi(initial state) = 0. Then the amortized time of
an operation is the actual time, plus a constant times the change to
phi. Increases to phi cause the amortized time to be larger than the
actual time, and decreases to phi cause the amortized time to be smaller
than the actual time.

1. For a binary heap, let Phi be n log n, where n is the number of items
currently in the heap.
(a) Show that with this definition, the insert operation in a binary
heap still takes O(log n) amortized time.
(b) Show that with this definition, finding and removing the minimum
element in a binary heap takes constant amortized time.
For both parts, the data structure should be unchanged; we are merely
analyzing it differently.

2. Suppose we wish to maintain a resizable vector data structure in
which the allowed operations are reading or writing the item at any
position in the vector, growing the length of the vector by one, and
shrinking the length of the vector by one. We represent the vector as a
record R with three slots R.l, R.a, and R.s, where R.l records the
length of the vector, and R.a points to an array of length greater than
or equal to R.l, and R.s records the length of R.a. Read and write
operations can be performed by accessing the appropriate position of
R.a, and grow and shrink operations can usually be performed only by
changing R.l, but a grow or shrink might need to replace R.a by a larger
or smaller array (copying all items to the replacement) whenever R.l and
R.s become two far apart from each other.
(a) Suppose that the resizing strategy is to increase the size of the
array to 2*R.l whenever R.l==R.s (that is, double the space whenever an
increase-length operation would overflow the array), and to reduce the
size of the array to 2*R.l whenever a R.l <= R.s/3 (to prevent the array
from taking too much unused space). Show that this resizing strategy
takes constant amortized time. (Hint: use a potential function that
measures the distance of R.l from R.s).
(b) Suppose that the resizing strategy is to increase the size of the
array to 2*R.l whenever a grow operation is performed with R.l==R.s
(that is, double the space whenever an increase-length operation would
overflow the array), and to reduce the size of the array to R.l whenever
a shrink operation is performed that would reduce R.l to less than
R.s/2. Is this algorithm efficient in an amortized sense? Why or why
not?
(c) Suppose that we never shrink the array R.a, and that we always
resize it to be a square of an integer k*k. Whenever we perform a grow
operation that would overflow the array (that is, that would make R.l
larger than R.s) we increase the size of the array to the next larger
square. Use a potential function of the form R.l - (R.s - R.l)^2 to show
that this resizing strategy uses O(sqrt n) amortized time per operation

3. (a) How much memory is required for the priority queue structure in
Dijkstra's algorithm, for a grah with n vertices and m edges, using a
binary heap?
(b) How much memory is required for the priority queue structure in
Dijkstra's algorithm, for a graph with n vertices and m edges, using a
data structure in which decrease-key operations are handled by
performing a lazy deletion of the item with the old key, followed by an
insertion of the same item with the new key?