COMP1805 - Test 3 (Sample) last initial 20 points total Week of March 14 Winter 2016 Student Number Student Name Instructions: This is a closed book exam. No calculators, cell phones, laptops or any aids are allowed. All questions should be answered on this sheet in the space provided. Show your work. You have 45 minutes. 1. (5 pts) Compute the following sums. You do not have to fully simplify your answer but your answer cannot have a summation (symbol) in it. 18 (a) 1 = [basic counting of terms in a sum, 1 mark] i=3 n 2i2 = [different limits, 2 marks] (b) i=12 n (2i 4) = [slightly complicated summands, 2 marks] (c) i=1 n (2i 4) O(n2 ). 2. (4 pts) Prove that i=1 Use same sum as 1(c), 3 marks for using denitions correctly, 1 mark conclusion 3. (2 pts) Let f (n) = n7 , g(n) = n5 , h(n) = n3 and p(n) = n. For each statement, ll in the blank with the best answer from f (n), g(n), h(n) or p(n), that ts the statement. For example, part (a) is done for you. (a) 3n3 log n 15n + 2 O( g(n) ) 1 mark, solution not given in actual test (b) 7n4 n3 log n + 2 ( ) 1 mark 4. (5 pts) Consider the following pseudocode. How many times is the print subroutine called? Write your answer rst using sums and then compute the closed form it (e.g., the closed form of n i is n(n+1)/2). i=1 Assume that n is large enough for both loops to execute at least once. for i from 1 to n do for j from 2 to n*n do print 'Q' end do print newline end do 3 marks for converting code to correct sums, 2 marks for closed form 5. (4 pts) Prove that f (n) = 3n3 4n2 + 17 (n3 ). Show your work. 3 marks for correct usage of either denition, 1 mark conclusion 2