Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
CSC165H1S
1. [5 marks] Short answer. You do not need to show your work for any part of this question. (a) [1 mark] Let n 2 Z+. What is the largest natural number that can be expressed by a 2n-bit binary representation, if exactly n of the bits equal zero? Your answer may include a summation—you do not need to simplify this summation. Solution 2n1X i=n 2i. (Comment: this simplifies to 22n 2n). (b) [3 marks] For each statement below, check one box to indicate whether the statement is True or Talse. True False True False True False n2 2 O(1.2n) X n log2 n 2 O(n) X 10 + log2 n 2 ⇥(log10 n) X n3 n+ 10 n2 + 3 2 ⌦(n2) X 10 2 ⌦(log3 n) X 10n + 11n 2 O(10n+11) X (c) [1 mark] Consider the following function: 1 def f(n: int) -> int: 2 i = 0 3 s = 0 4 while s < 2 * n: 5 s = s + i 6 i = i + 2 7 return s Let k 2 N. Find an expression for sk, the value of variable s after exactly k loop iterations, assuming k iterations occur. Your answer may include a summation—you do not need to simplify this summation. Solution sk = kX j=0 2j = k2 + k Please do not write below this line. There is extra space at the back of the test paper.