CS 6363.004: Algorithms Spring 2019 Assignment 1 Wed, Jan 30, 2019 You can write or type your answers. Submit on elearning. If you submit photos of your written assignment, make sure that they are readable and all pages are included. Use lower resolution so that each page is less than 256 KB. Submit a single pdf, docx or txt file with all the pages. If you solve optional problems, you can score additional points, but the net contribution from homework assignments to the weighted total used in grade calculations is capped at 20/100. Due: 11:59 PM, Sun, Feb 10 (on elearning). 1. Prove that log(n!) = Theta(n log n) using any method from class. 2. Solve the following recurrences using the given method. Assume T(1)=1. a. Iteration method: T(n) <= 2T(n/2) + 1, for n > 1. b. Substitution method: T(n) = T(n-1) + n^2, for n > 1. c. Master method (special case): Problem 4-1, parts a,c,e (p. 107). 3. Rewrite recursive binary search to solve the following problem: Given a sorted array A, and a value x, find the index i of A such that A[i] <= x < A[i+1]. Assume that A[0] = -infinity and A[n-1] = +infinity, where n = A.length. In other words, the function should return the index of the rightmost occurrence of x if x is in A, and the index of floor(x) if x is not in A. Prove that your algorithm is correct and analyze its running time. // Assume A has sentinels, A[0] = -infinity and A[n-1] = +infinity. int binarySearch(int[] A, int x): return binarySearch(A, 0, A.length-1, x) int binarySearch(int[] A, int p, int r, int x): // To do Optional problems (extra credit): 4. Prove that the following algorithm is incorrect for problem 3: binarySearch(A, p, r, x): n <-- r-p+1 if n <= 2 then return p else q <-- (p+r)/2 if x < A [q] then return binarySearch(A, p, q-1, x) else if x = A [q] then return q else /* x > A[q] */ return binarySearch(A, q+1, r, x) 5. Write a proof of correctness of the recurrence for E(j) that was written in class for the maximum subarray problem. Show that it runs in O(n) time. 6. Show how to implement the divide and conquer algorithm for the maximum subarray problem discussed in class (see Sec 4.1 in book) to run in O(n) time. Do not modify the main structure of the algorithm: divide into 2 halves, recurse and conquer.