Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit




CSC 225 FALL 2021

ALGORITHMS AND DATA STRUCTURES I

MIDTERM EXAMINATION


 

1.  (i) In how many ways can the letters of the word DATAGRAM be arranged that have all the three A’s together? Explain your answer.  [2 Marks]

 

 

 

 

 

 

 

 

 

 

 

 

 

 

(ii) Determine z if z100  = o0(50)80 + o1(50)81 + o2(50)82 + x x x + o4(5)9(0)849 + o5(5)0(0)850 . Explain your answer.  [2 Marks]

 

 

 

 

 

 

 

 

 

 

 

 

(iii) In how many ways can we distribute eight identical white balls into four distinct containers so that no container is left empty? Explain your answer.  [2 Marks]


 

2.  Solve the following recurrence equation using top-down repeated substitution method.  You must show all the steps of the calculation.  Your final answer must be in the simplest closed form possible.  [4 Marks]

 

 

T (n)   =   2 if n = 1

=   T (n - 1) + 2 log n if n > 2


 

 

3.  (i) Order the following functions by increasing growth rate starting from slowest to fastest. Explain your reasoning.  [3 Marks]

 

nn , (log n)2 , ,n, n3 , 22log  , 4log 8

 

 

 

 

 

 

 

 

 

 

(ii) Prove that f(n) = 4 logn + log log n = Θ(log n). You must show your calcula- tions and write down the values of c1 . c2 . n0  clearly.  [3 Marks]


 

 

4.  (i) For the following input sequence, what will be the output after one round of SelectionSort, BubbleSort and InsertionSort?  By one round, we mean a one complete execution of the inner f●o loop for a particular choice of outer f●o loop variable.  [1.5 Marks]

 

2   5   9    1   7   3   4     6

SelectionSort:

 

BubbleSort:

 

InsertionSort:

 

(ii) Give a proof of correctness of rnssr≠ionIor≠  using the loop invariant method. That is, state a mathematical claim si  that is a loop invariant for InsertionSort at the end of round i, for 1 s i s n. Then prove that si  is true by induction on i.  [2.5 Marks]