CS 4349.002. Advanced Algorithm Design and Analysis Spring 2019 Assignment 1 Wed, Jan 23 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 3. Total: 40. By answering optional problems, it is possible to score up to 80/40. 1. Assume that T(1)=1, if no base case is given. (a) Solve using the iteration method: T(n) = 2 T(n/2) + 1, for n > 1. (b) Solve using the Master method: Problem 4-1, parts c,d,e (p. 107). You may use the version of the Master method from class or the more general version given in the text book. 2. Write a proof by induction to show the correctness of the binary search code given below: // Find index of x in sorted array A[p..r]. Return -1 if x is not in A[p..r]. int binarySearch ( A, p, r, x ): // Pre: A[p..r] is sorted if p > r then return -1 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) Optional problems (for extra credit): 3. Problem 3-4 (p. 62). 4. The following recurrence arises in the design of sorting networks. Prove using substitution method that the solution to the following recurrence is S(n) = O(n log^2(n)): S(n) = 2 S(n/2) + n log(n), for n > 1, S(1) = 1.