Problem 3 abcd

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 your