Problem 1 (8 marks, 1 page). Consider the algorithm mystery() whose input consists of an array...

Transcribed Image Text:

Problem 1 (8 marks, 1 page). Consider the algorithm mystery() whose input consists of an array A of n integers, two nonnegative integers l, u satisfying 0 lun1, and an integer k. We assume that n is a power of 2. Algorithm mystery(A[0,..., (n-1)], l,u,k) if l == u then if A[l] == k then return 1; else return 0; end if else m (l+u-1)/2]; return mystery(A, l, m, k) + mystery(A, m + 1,u,k); end if a) [2 marks] What does mystery(A[0..(n - 1)], 0, n 1, k) compute (0.5 mark)? Justify your answer (1.5 marks). b) [1 mark] What is the algorithmic paradigm that the algorithm belongs to? c) [2 marks] Write the recurrence relation for C(n), the number of additions required by mystery(A,0, n 1, k). d) [2 marks] Solve the above recurrence relation by the backward substitution method to obtain an explicit formula for C(n) in n. e) [1 mark] Write the complexity class that C(n) belongs to using the Big- notation. Problem 1 (8 marks, 1 page). Consider the algorithm mystery() whose input consists of an array A of n integers, two nonnegative integers l, u satisfying 0 lun1, and an integer k. We assume that n is a power of 2. Algorithm mystery(A[0,..., (n-1)], l,u,k) if l == u then if A[l] == k then return 1; else return 0; end if else m (l+u-1)/2]; return mystery(A, l, m, k) + mystery(A, m + 1,u,k); end if a) [2 marks] What does mystery(A[0..(n - 1)], 0, n 1, k) compute (0.5 mark)? Justify your answer (1.5 marks). b) [1 mark] What is the algorithmic paradigm that the algorithm belongs to? c) [2 marks] Write the recurrence relation for C(n), the number of additions required by mystery(A,0, n 1, k). d) [2 marks] Solve the above recurrence relation by the backward substitution method to obtain an explicit formula for C(n) in n. e) [1 mark] Write the complexity class that C(n) belongs to using the Big- notation.