CSC 225 ALGORITHMS AND DATA STRUCTURES I
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]
2021-12-03