Fundamental Algorithms Homework #1 Set on June 25, 2009 Due on July 2, 2009 to the TAs 1. [15 pts] Analyze the worst-case time complexity of the following algorithms, and give tight bounds using the Theta notation. You need show the key steps involved in the analyses. a) procedure matrixvector(n: integer); var i,j: integer; begin for i <- 1 to n do begin B[i] = 0; C[i] = 0; for j <- 1 to i do B[i] <- B[i] + A[i,j]; for j <- n downto i+1 do C[i] <- C[i] + A[i,j] end end; b) Algorithm MysteryPrint(A[1..n]); begin if n = 1 then print A[1] else begin print A[n]; call MysteryPrint(A[1..n-1]); call MysteryPrint(A[2..n]) end end; c) procedure whileloop(n: integer); var i,count: integer; begin count <- 0; i <- 1; while i < n do begin i <- 3*i; count <- count + 1 end end; 2. [10 pts] [Levitin, p. 60] Question 7 (a, c). 3. [10 pts] Insertion sort can be expressed as a recursive procedure as follows. Given A[1..n], we recursively sort A[1..n-1] and then insert element A[n] into the sorted array A[1..n-1]. Write a recurrence relation for the running time of this recursive version of insertion sort. Feel free to use the big-O notation and assume the worst case. Can you also solve the recurrence relation? Is your result the same as the one obtained by the summation analysis in the textbook (pp. 160-162)? 4. [15 pts] Give a tight asymptotic bound for T(n) in each of the following recurrences. Assume that T(n) is a constant for n <= 2. Justify your answers. a. T(n) = 16*T(n/4) + n^2 b. T(n) = 7*T(n/3) + n^2 c. T(n) = T(n-1) + n^2 You may solve these recurrences using either the Master Theorem or the backward substitution method. 5. [15 pts] Describe a Theta(nlog n) time algorithm that, given a set S of n integers and another integer x, determines if or not there exist two elements in S whose sum is exactly x. Analyze the running time of your algorithm to make sure that it is really Theta(nlog n) (it would be sufficient to show that the running time is O(nlog n)). Before you present the pseudo-code, use a few words to describe the basic ideas in your algorithm to help the reader understand your algorithm. Hint: Sorting and binary search. You can sort in Theta(nlog n) time by e.g. merge sort or heap sort.