CMPS 211 Exam 2 with Solution, Spring 2016

AUB-CMPS 211-Spring 2015-16 March 29th, 2016 Quiz 2 Instructors: F. Abu Salem and A. Al Zaatari Name: Duration: 1 hour This exam is closed notes. Question 1 (15%) Let A = {1, 2, 3} and B = {1, 2, 5, 10}. (a) (5%) Find A∪B and A∩B. (The answer does not depend on the choice of universal set) Solution: (a) A∪B = {x | (x ∈ A) ∨ (x ∈ B)} = {1, 2, 3, 5, 10}. 2.5 pts A∩B = {x | (x ∈ A) ∧ (x /∈ B)} = {3}. 2.5 pts (c) ∀x ∈ A ∃y ∈ B (x|y). Alternatively: ∀x ∈ A ∃y ∈ B ∃n ∈ Z (y = nx). 2.5 pts This statement is false since 3 ∈ A and ¬(3|1) ∧ ¬(3|2) ∧ ¬(3|5) ∧ ¬(3|10). 2.5 pts (d) ∃x ∈ A ∀y ∈ B x|y. 2.5 pts This statement is true since 1 ∈ A and (1|1) ∧ (1|2) ∧ (1|5) ∧ (1|10). 2.5 pts F-1 Question 2 (15%) Let f : Z → Z be the function defined by f(n) = �n 3 � . Solution: (a) f(1) = 1, f(3) = 1, f(4) = 2 and f(100) = 34. Hence f({1, 3, 4, 100}) = {1, 2, 34}. 2.5 pts (b) f −1({−1, 10}) = � n ∈ Z | �n 3 � ∈ {−1, 10} � . 1 pt So for n ∈ Z, we have (1 pt): n ∈ f −1({−1, 10}) ↔ ( � n 3 � = −1) ∨ ( � n 3 � = 10) ↔ (−2 < n 3 ≤ −1) ∨ (9 < n 3 ≤ 10) ↔ (−6 < n ≤ −3) ∨ (27 < n ≤ 30). This means that f −1({−1, 10}) = {−5, −4, −3, 28, 29, 30}. 0.5 pts (c) f is not an injection since f(1) = f(2) = 1 even though 1 ̸= 2. 2.5 pts In other words, there are distinct elements of Z having the same image by f. 2.5 pts (d) f is a surjection since for all n ∈ Z, we can find a preimage k = 3n for which f(3n) = n. 2.5 pts Hence every integer n has at least one preimage. (Note that the other preimages of n are 3n − 1 and 3n − 2.) 2.5 pts F-2 Question 3 (20%) Use strong induction to show that every positive integer n can be written as the sum of distinct powers of two, that is, as a sum of a subset of integers 20 = 1, 21 = 2, 22 = 4, . . ., etc. When attempting to infer P(k + 1) from previous instances of that same predicate, consider the following hints: • Hint 1: Treat the cases when k is even or odd separately. • Hint 2: When k is odd, use the fact that k+1 2 is an integer. Solution Base Case: Take k = 1 the first positive integer, k can be written as k = 20 = 1. Therefore P(k) is true. 4 pts Inductive Step: Assume That the hypothesis holds for all positive integers up to and including k, in other words: ∀i ∈ N∗ (i ≤ k) → P(i) 2 pts We need to show that P(k + 1) holds. We proceed by cases on k. • if k is even, then k + 1 is odd. By the inductive hypothesis, k can be written as a sum of powers of 2: k = 2m1 + 2m2 + ... + 2mn Therefore we can write k + 1 as: k + 1 = 2m1 + 2m2 + ... + 2mn + 1 = 2m1 + 2m2 + ... + 2mn + 20 Therefore P(k + 1) holds. 7 pts • if k is odd, then k + 1 is even, therefore k+1 2 is a positive integer, and k+1 2 < k + 1. By the inductive hypothesis, k+1 2 can be written as a sum of powers of 2: k + 1 2 = 2m1 + 2m2 + ... + 2mn However k + 1 = 2 k+1 2 . Which can be writter as: k + 1 = 2(2m1 + 2m2 + ... + 2mn) = 2 × 2m1 + 2 × 2m2 + ... + 2 × 2mn k + 1 = 2m1+1 + 2m2+1 + ... + 2mn+1 Therefore P(k + 1) holds. 7 pts F-3 Question 4 (15%) Use mathematical induction to prove that n� i=1 1 (2i)(2i+2) = n 4(n+1) Solution Let P(n) = “ n� i=1 1 (2i)(2i+2) = n 4(n+1) ′′. 3 pts Base case: Take n = 1, then: n � i=1 1 (2i)(2i + 2) = 1 2(2 + 2) = 1 4(1 + 1) = n 4(n + 1) 3 pts Inductive step: Show P(n) → P(n + 1). Assume that n� i=1 1 (2i)(2i+2) = n 4(n+1). Write: n+1 � i=1 1 (2i)(2i+2) = n� i=1 1 (2i)(2i+2) + n+1 � i=n+1 1 (2i)(2i+2) 3 pts = n 4(n+1) + 1 4(n+1)(n+2) 3 pts = n(n+2) 4(n+1)(n+2) + 1 4(n+1)(n+2) = n2+2n+1 4(n+1)(n+2) = (n+1)2 4(n+1)(n+2) = n+1 4(n+2) = n+1 4((n+1)+1) 3 pts Therefore, P(n + 1) = “ n� i=1 1 (2i)(2i+2) = n 4(n+1) ′′ is established. F-4 Question 5 (35%) Given a list (tuple) of integers A = (a1, . . . , an), the pre-fix sum (cumulative sum) of A is another list (tuple) S = [s1, . . . , sn] such that si = a1 + . . . + ai. For example, given A = [1, 5, 9, 12, 100], we have S = [1, 6, 15, 27, 127]. (a) (10%) Develop the algorithm (in pseudo-code), which, given a list (tuple) of integers A, pro- duces their pre-fix sum S. Procedure prefixsum(a1, ..., an): Let s1, ..., sn be the list that will contain the prefix sum. s1 := a1 for i := 2 to n si := si−1 + ai return s1, ..., sn (b) (2.5%) Can you run your alogrithm in-place (that is, you produce the output in the same data structure as that hosting your input?)? Explain why or why not. After iteration i, the entry ai is no longer needed. This claim is valid for all iterations. So, the algorithm can run in-place, that is, we can procuce the output in the same array as the input. Procedure inplace-prefixsum(a1, ..., an): for i := 2 to n ai := ai−1 + ai return a1, ..., an F-5 (c) (5%) State a loop invariant for the algorithm. At the start of iteration i, we have: sk = k � j=1 aj = a1 + ... + ak ∀k < i For the in place version, the invariant becomes: ak = i � j=1 aj = a1 + ... + ak ∀k < i (d) (10%) Prove the loop invariant for the algorithm. Initialization: At the start of the first iteration i = 2, we have s1 = a1 = 1� j=1 aj. 3 pts Maintenance: Assume that the invariant holds at the beginning of an iteration i: sk = k � j=1 aj = a1 + ... + ak ∀k < i We want to show it holds after that iteration. At the end of iteration i, si gets updated to si−1 + ai according to the algorithm. But i − 1 < i, Therefore by the invariant si−1 = i−1 � j=1 aj = a1 + ... + ai−1. Thus we get: si = si−1 + ai = a1 + ... + ai−1 + ai = i� j=1 aj Since s1, ..., si−1 were not changed, therefore at the end of the iteration: sk = k � j=1 aj = a1 + ... + ak ∀k ≤ i 4 pts Termination: It is obvious that the loop terminates when i = n + 1 > n. Upon Termination we have: (i = n + 1) ∧ (∀k < i sk = k � j=1 aj = a1 + ... + ak) sk = k � j=1 aj = a1 + ... + ak ∀k ≤ n Therefore s = s1, ..., sn contains the prefix sum for a = a1, ..., an. The same proof applies for the in place algorithm by changing s to a. 3 pts F-6 (e) (5%) Develop the run-time of the algorithm in terms of the input size. The algorithm executes one assignment outside of the for loop s1 = a1. The for loop contains n − 1 iterations, each of these iterations contain one assignment and one addition. Total run time requires 2(n − 1) + 1 = 2n + 1 operations ∈ Θ(n). The in place version has an equivalent for loop, but it does not have an assignment before it. Total run time for in place requires 2(n − 1) operations ∈ Theta(n). (f) (2.5%) Determine the amount of space required by the algorithm in terms of the input size. In addition to the input list a, the algorithm requires space for the result list s = s1, ..., sn. Overall, the algorithm requires space for n + n = 2n ∈ Θ(n) items (variables). n for s and n for the input a. The in place algorithm operates only on the input without requiring auxiliary space (no s). Overall, the in place algorithm requires space for n items (variables) which are the input list a1, ..., an. F-7