iate appropriate loop invariants and for each one show the properties of Initial
ID: 3881637 • Letter: I
Question
iate appropriate loop invariants and for each one show the properties of Initializaio Maintenance, and Termination a. (5 marks) Exercise 2.1-3 (CLRS p.22). b. (7 marks) Problem 2-2 (CLRS p.40-41). Caution: Do not forget to answer question d on page 41. Note: You should be able to tackle these problems by following "week 02 slides" Problem 3. (10 marks) Recall the sequence of Fibonacci numbers: F(0) = 0,F(1) = 1, and F(i) F(i-1) + F(i-2) for all i 2 2. a. (2.5 marks) Assume that t N such that F(t 2) 2 1.6-4 and F(t - 1) 1.6-3. Prove that F(t) 2 1.6t-2 b. (2.5 marks) Give the set of all natural numbers q for which F) 1.69-2. Justify briefly. c. (2.5 marks) Does your answer to b imply that F(n) E(1.6")? Explain briefly d, (2.5 marks) Does your answer to b imply that F(n) E (1.6")? Explain briefly. Note: You can tackle the first two subproblems anytime. For the last two, follow the "week 03 slides". Problem 4. (13 marks) Describe a method for finding both the minimum and maximum of n numbers using fewer than 3n/2 comparisons. (Hint: first construct a group of candidate minimums and a group of candidate maximums). Then, write a pseudocode for your method. What loop invariant(s) does yourExplanation / Answer
3a) Given F(t-2) >= 1.6t-4 -- (i) and F(t-1) >= 1.6t-3 -- (ii)
Adding (i) and (ii), we get F(t) >= 1.6t-4 + 1.6t-3 -- (iii)
=> F(t) >= 1.6t-4 + 1.6 x (1.6t-4) = (1 + 1.6) x 1.6t-4 = 2.6 x 1.6t-4 >= 2.56 x 1.6t-4 = 1.62 x 1.6t-4 = 1.6t-2
Hence, proved
3b) Clearly F(q) >= 1.6q-2 is true for q = 1,2 but not 0. Using the principle of mathematical induction and result from 3a, It is clear that F(q) >= 1.6q-2 will be true for all q >= 1. Hence, solution is {1, 2, 3, ...}
3c) 3b implies a lower bound on F(q) but it says nothing about the upper bound. Since O() notation stands for worst case i.e, upper bound, Hence, the given statement is False.
3d) F(n) >= 1.6n-2 implies F(n) >= 1.6-2 x 1.6n . Hence the given statement is True from the defination of Omega notation
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.