Please answer

Q4) (20 pts) Consider the array (assigned to you) that is reverse sorted. (a) Run a binary search algorithm to determine the index of first occurrence of search key K (assigned) (b) Run a binary search algorithm to determine the index of last occurrence of search key K. For each of (a) and (b), show the details of the iterations (such as the values of the left index, right index, middle index, the comparison and the decision made to move either the left index or the right index, etc for each iteration). Q5) (20pts) Consider the array (assigned to you) that has a sequence of negative integers (0). Run a binary search algorithm in two stages to determine the number negative integers, number of 0s and the number of positive integers. For each stage of the binary search algorithm: (a) Show the appropriate initial values for the left index (LI) and right index (RI). (b) State the invariant property that will be maintained for the LI and RI vis-a-vis the f(x) values for the entire algorithm. (c) Provide a pseudo code of the binary search algorithm, including the scenarios when you will move the LI and RI (d) Show your iterations in detail (incl. the latest vales for LI and RI; the middle index; the comparison and the decision to move either the LI or the RI for that iteration) Q6 - 15 pts) Given a concave up unimodal array of unique integers, your task is to run a binary search algorithm to find the minimum element. a) Write a pseudo code for your binary search algorithm to determine the minimum in a concave up unimodal array of unique integers. b) Like the slides discussed in class for concave down unimodal array, show the two scenarios that would arise for which you would need to move either the left index to the right or the right index to the left in pursuit of finding the minimum element in a concave up unimodal array of unique integers. c) Show your execution of the binary search algorithm on the array assigned. You need to show the initial and the iteration-level values of the left index, right index and middle index as well as your decisions to reduce the search space in each iteration. Q7 - 20 pts) Consider the following pseudo code discussed in class for a recursive algorithm to determine the index where the maximum element is in an array. Algorithm FindMaxIndex(Array A, int leftlndex, int rightlndex) // returns the index of the maximum element in the array A for // index positions ranging from leftlndex to rightindex Your task in this question is to develop a recursive algorithm (by modifying the above pseudo code) to count the number of odd integers in an array. a) Write a pseudo code for a recursive function CountOdd that takes an array A, left index and right index as its arguments to determine the number of odd integers in the index range spanning from left index to right index (inclusive of the two end indexes). b) Show your working of the algorithm (similar to how it is shown in the slides to find the index for the maximum element) to determine the number of odd integers in the array (assigned to you), spanning from index 0 to 9 . c) Identify the basic operation in your recursion. Write a recurrence relation to determine the number of times the basic operation is executed for an array of size ' n '. Also, write the terminating condition. d) Solve the recurrence relation of (c) using Master Theorem