1. (a) (20 points) For each of the following recurrences, first check if master theorem is applicable, and if yes, calculate the complexity using it. 1. T (n) = 2t( n2 ) + n log n 2. T (n) = 0:3T ( n2 ) + n1 3. T (n) = 2T ( n2 ) + n3 4. T (n) = 7nT ( n2 ) + n4 5. T (n) = 4T ( n2 ) + n2pn 6. T (n) = 64T ( n8 ) − n2 log n 7. T (n) = 16T ( n4 ) + n2 (b) (10 points) Confirm the result for recurrence 1 using recursion tree (c) (10 points) Confirm the result for recurrence 3 using induction. 2. (10 points) Given an array of numbers, find a peak in the array, i.e, an element which is greater than or equals to the its neighbors (previous and the next number). The first and last elements have only one neighbor. Example: Input: 2 3 5 4 6 7 3 Returns: Either 5 or 7 (one is enough) 3. (15 points) . Now Extend the previous question to a 2D array: find an element that is greater than or equals to its neighbors (diagonal adjacent are not counted as neighbors, so each element has at most 4 neighbors to consider ) 4. (a) (5 points) Explain the traditional polynomial multiplication, and state its complexity (b) (15 points) Improve the complexity using Divide and Conquer method. 5. Given an array A[1; :::; n] of integers, design an algorithm that returns a pair i < j so that that A[j] − A[i] is maximum. (a) (10 points) Design an O(n lg n) algorithm (b) (10 points) Design and O(n) algorithm 6. You are given a sorted list of 2k+1 shoes with their product identification numbers (pid). The list includes k pairs and one single shoe. Each pair of shoes have the same pid. Design an algorithm that finds the single id in the list: (a) (5 points) Design an O(n) algorithm (b) (10 points) Design and O(lg n) algorithm Example Input: 5 5 12 12 18 18 19 21 21 50 50 Output: 19
