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.