=========================preview======================
(COMP171)comp171-wa1-sol.pdf
Back to COMP171 Login to download
======================================================
The Hong Kong University of Science & Technology
Department of Computer Science and Engineering
COMP 171: Data Structures and Algorithms
Written Assignment 1
Out on March 14, 2007
Due on March 28, 2007
Suggested solution

1. (a) (2 points) and


Solution: Clearly,


for n>=1,


for n>0,

So


(b) (2 points)
and

Solution: For n>=1,
, so

For n>=2, if n is even,

If n is odd,


, so


(c) (2 points)
and

Solution: Since
for x>0, setting x = log n, so


, the answer is


(d) (2 points) and


Solution: By elementary calculus, one can show that the function
is strictly increasing for x > max(c, e) (i.e. ). Thus, there exists such that


for . It follows that for , which implies that .




Similarly, for any constant there exists such that



for

Rearranging, we obtain for . Thus,


.
The answer is
.

(e) (2 points) and


Solution: for ,



Since
. The answer is
.

2. (a)
Since each time of running Step 5 and 6, the size of the queue is reduced by 3/4. Only one forth of the queue elements remain. Thus the returned value of Fun(Q) is



(b)


(c)



Or we can use another simpler argument by observing the entire dequeuing process, which is the major part of the running time of the algorithm. Since the n elements in the queue Q is dequeued one by one until it becomes empty, the running time should be of complexity of n dequeuing steps, which is O(n).

3.
To perform mergesort non-recursively, we may start with adjacent elements and merge them two at a time to form sorted lists of size 2. Then we merge two adjacent lists to form sorted lists of size 4, and so on. The leftover elements can be easily taken care of by merging onto the existing sorted lists in each iteration. The process continues until we have merged to a complete sorted list.

pseudo-code:
input : unsorted array A[1..n]
set k=1
do
From i=1 to floor[n/2k]
Merge(A[2k(i-1)+1..2k(i-1)+k], A[2k(i-1)+k+1,2k(i-1)+2k])
if ( floor[n/2k] not equal to n/2k)
Merge(A[2k(floor[n/2k]-1)+1..2k(floor[n/2k])], A[2k(floor[n/2k])+1..n])
k = k*2
while n/k>=1

The running time is



4.
Step 1. Initialize the stack. Read in the infix expression.
Step 2. Get one character from the expression.
Step 3. If it is a variable (operand), write it out. Go to Step 2.
Step 4. If it is a (, push it into stack. Go to Step 2.
Step 5. If it is a ), pop from the stack all the way to (, writing out all the operators in sequence (do not write out ( and ) ). Go to Step 2.
Step 6. If it is a C or +, keep popping the stack if its operator is +, - or * and write them out in sequence. Push the new operator into stack. Go to Step 2.
Step 7. If it is a *, keep popping the stack if its operator is *. Push the new * into the stack. Go to Step 2.
Ste