Points to remember: Youcanassumethatyouhaveaccesstothefunction BINARYSEARCH(A[low high] key) that searches for key in the subarray A[low high] and returns an index of key if key is present and returns 1 if key is not present. Quick summary: Brute force is a simple, straightforward, naive, and exhaustive search-based approach. Decrease-and-conquer is a recursive algorithm design tech nique where a function calls only one instance of itself on a smaller subproblem. 1. [10 points] Given a sorted array of numbers A[1 n], we would like to determine a value x such that both x and (2x 17) are in the array. If there is, print one such value x, else, print that there is no such value. (i) Design a On2 time, (1) extra space algorithm FINDX-NAIVE(A[1 n]) to solve the problem. (ii) Design a Onlogn time, (n) extra space algorithm FINDX-BETTER(A[1 n]) to solve the problem. (iii) Design a O(n) time, (1) extra space algorithm FINDX-BEST(A[1 n]) to solve the problem. 2. [10 points] Consider the algorithm called SIMPLESORT. Consider two example arrays of size 5 and show the array contents with values of i and j (approximately 25 steps for each example). Does this simple algorithm sort an array of unique elements? Does it sort an array even if there are duplicates? If the algorithm does sort, why do you think it sorts? If the algorithm does not sort an array give a counterexample and you will get 5 extra points as bonus points. SIMPLESORT(A[1 n]) 1. Input: Array to be sorted A[1 n] 2. Output: Sorted array in A[1 n] 3. for i 1tondo for j 1tondo 4. 5. 6. if A[i] < A[j] then SWAP(A[i]A[j]) 1 3. [10 points] Given an array of real numbers A[1 n], apair of indices (i j) is called an inversion if i A[j]. We want to count the total number of inver sions in a given array. (i) Design asimplenon-recursive algorithm COUNTINVERSIONS-NONRECURSIVE(A[1 n]) to solve the problem. (ii) Design a simple recursive algorithm COUNTINVERSIONS-RECURSIVE(A[1 n]) to solve the problem. 4. [10 points] Given an array of real numbers A[1 n], we want to compute and return the prefix sum array P[1 n] such that P[i] = A[1] A[2] A[3] A[i]. (i) Design a O(n) non-recursive algorithm PREFIXSUM-NONRECURSIVE(A[1 n]) to solve the problem. (ii) Design a O(n) recursive algorithm PREFIXSUM-RECURSIVE(A[1 n]) to solve the problem. 5. [10 points] Given a string S[1 2n] containing just the characters ’(’ and ’)’, de sign an algorithm ISVALIDSTRING(S[1 2n]) to determine if the input string is valid. An input string is valid if the open brackets are closed in the proper order. Example: (()) is valid; (())() is valid; )()) is invalid; ())) is invalid; ()(( is invalid. (Hint: Use a stack to solve the problem.) 6. [10 points] Given two natural numbers a and b, we want to compute the greatest common divisor (GCD) of a and b. (i) Design a simple non-recursive algorithm GCD(ab) to solve the problem. (ii) Design a simple recursive algorithm GCD(ab) to solve the problem. 7. [10 points] Apolynomial P(x) with asingle indeterminate x is written in the form: n P(x) = aixi = anxn an 1xn 1 a2x2 a1x a0 i=0 where ai for all i [0n] is a real constant. Assume that ai = A[i] for all i. We want to compute the univariate polynomial P(x) at a specific value of x. (i) Design a On2 algorithm EVALUATEPOLY(A[0 n] x) to solve the problem. (ii) Design a Onlogn algorithm EVALUATEPOLY(A[0 n] x)tosolvetheproblem. (Hint: Ideas from the slides are helpful) (iii) Design a O(n) algorithm EVALUATEPOLY(A[0 n] x) to solve the problem. (Hint: Use Horner’s method of representing the polynomial as follows.) P(x) = a0 x(a1 x(a2 x(a3 x(an 1 xan) ))) 8. [10 points] Given a sorted array A[1 n] and a value k, we want to return a pair of distinct indices such that the sum of elements at those indices equals k. That is, we want to return a pair of indices (i j), where 1 i < j n and A[i] A[j] = k. (i) Design a On2 algorithm PAIRSUM(A[1 n] k) to solve the problem. (ii) Design a Onlogn algorithm PAIRSUM(A[1 n] k) to solve the problem. 2 (iii) Design a O(n) algorithm PAIRSUM(A[1 n] k) to solve the problem. 9. [10 points] Given a sorted array A[1 n], we want to count the number of occur rences of value k in the array. (i) Design a O(n) algorithm COUNTFREQUENCY(A[1 n] k) to solve the problem. (ii) Design a O logn algorithm COUNTFREQUENCY(A[1 n] k) to solve the prob lem. (Hint: Modify binary search and use it.) 10. [10 points] Simulation problem. (i) Simulate a stack using queue(s). That is, show how to implement Push and Pop functions of stack using Enqueue and Dequeue methods of queue(s). (ii) Simulate a queue using stack(s). That is, show how to implement Enqueue and Dequeue functions of queue using Push and Pop methods of stack(s)