=========================preview======================
(COMP171)comp171mds04sol_gary.pdf
======================================================
COMP 171
Spring 2004

Solutions for the Midterm

1. (a)7
(b)
0

(c)
It returns the array index of the maximum element.

(d)
Let T (n) be the running time of fun(). Obviously, we have (let n =2k),

T (n)=2T (n/2) + O(1) =4T (n/4) + 2O(1) + O(1) .
.
. =2kT (n/2k)+(2k.1 + ... +2+1)O(1) = nT (1) + (2k .1)O(1) = nO(1) + (n .1)O(1) = O(n).
2. The subsequent array contents are: Initialiation:
012345

36
28
24
22
19
14
9
After 1st step:
0 1 234 5

28
22
24
9
19
14
After 2nd step:
0 1 234 5

24
22
14
9
19
28
After 3rd step:
0 1 234 5

22
19
14
9
24
28
After 4th step:
012 3 4 5

19 9
14
22
24
28
After 5th step:
012 3 4 5

14 9
19
22
24
28
After 6th step:
01 2 3 4 5

9 14
19
22
24
28
3. (a) To implement the Stack ADT using two queues, Q1and Q2, we can simply enqueue elements into Q1 whenever a push call is made.
For pop calls, we can dequeue all elements of Q1 and enqueue them into Q2 except for the last element which we set aside in a temp variable. We then return the elements to Q1by dequeing from Q2 and enqueing into Q1. The last element that we set aside earlier is then returned as the result of the pop.
Note: The students may simply return the last element in Q1and in next operation, the roles of Q1and Q2 would be swapped.
(b) The push takes O(1) time to complete. Performing a pop takes
O(n)time.
Therefore for n pops and pushes, it takes O(n2)steps.

4. (a) i. Scan a once to .nd where x is. Swap it with the last element
of a and use it as the pivot to partition the array into two.
This is similar to the quicksort algorithm as follows:
A. Keep a left and right pointer in a. left goes from left
to right, until it .nds a number larger than or equal to x.
B. The right pointer in goes from right to left, until it .nds
a number smaller than x (or hits the left boundary of the
array).
C. Swap the elements pointed by left and right.
D. Repeat the process until left is on the right of right.
E. Swap x with left.
The rank of x is the index pointed by left.
ii. The .rst scan takes O(n) to .nd x. Since the total number of
steps taken by left and right is the array size, the partition
step is O(n). Therefore the total number of steps is O(n).
Note that a student may also go through the array and count
the number of elements less than x.This also takes O(n)
time.
(b) i. We .rst sort b in increasing order. Then use b[k/2] as the
pivot to partition the array into two using the algorithm given
aboveto.nd therankof b[k/2]. Now for the left sub-array
of a, we need to .nd the ranks of b[0...k/2-1],whereas
for the right sub-array of a, we need to .nds the ranks of
b[k/2+1...k-1].
For each of these sub-arrays, we recursively partition it until
all