(COMP171)comp171mds04sol_gary.pdf

Back to COMP171 Login to download

======================================================

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