CSE 373, Autumn 2002: Homework 2

Due 10/18/2002

For all program or data structure design problems such as the two below you must provide pseudocode (see the manual) and an adequate explanation of the methods. It is often helpful to include small examples demonstrating the methods. Straight pseudocode with no additional documentation is not enough. Your pseudocode can contain English if needed. Each problem should be answered on a separate sheets of paper so they can be graded by different TAs. Your name should be at the top of every page.

(10 points) A recursive version of Insertionsort works as follows. We have a list to sort. If the list is empty then there is nothing to do. Otherwise, sort all but the first element of the list recursively, then insert the first element of the list into its proper place in the the list by comparing it to members of the returned list which is already sorted.

Assume a node in the list has two fields: value which holds an integer, and next which is a pointer to a node. Design the recursive list version of Insertionsort(p : node pointer) : node pointer in pseudocode. Your function should be destructive.
Analyze the worst case time of your algorithm. Because it is recursive your time bound should first be defined by a recurrence, then the recurrence should be solved.

(10 points) Design an array based data structure for two stacks called a DualStack The two stacks should share the same array in an efficient manner. If there are MaxSize entries in the array then the IsFull function should only return true is all the entries in the array are occupied. Your operations should all be constant time.

Implement Push(S: DualStack pointer, i: integer, p : blob pointer) that pushes the blob pointed to by p onto the i-th stack in S (i = 0 or 1). Similarly, implement Pop, IsEmpty, IsFull.
Explain why such a nice data structure would not be possible for 3 stacks.

10 points) Consider the following general recurrence T(1) <= d and T(n) <= aT(n/b) + cn for a time bound. Show that:

If a < b then T(n) = O(n).
If a = b then T(n) = O(n log n).
If a > b then T(n) = O(n^{log_b a}) (n to the power log base b of a).