Problem 4

b. (2.5 marks) Give the set of all natural numbers q for which F) 2 1.69-2, Justify briefly. c. (2.5 marks) Does your answer to b imply that F(n) E O(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 algorithm maintain? Pick up one of them and show the properties of Initialization, Maintenance, and Termination. Note: Follow the hint to develop such a method. Then, work out the rest by following"week 02 slides" The next two questions require the knowledge and some skills described in "week 03 slides" Problem 5. (20 marks) a. (15 marks) Problem 3-4 (CLRS p.62). Answer all 8 questions 7em a