Solution: Questions 1-4 and Question 5

1. (5 points)
   Shown below is an algorithm to evaluate the value of a polynomial p(x). Evaluate the running time of this algorithm, using the "direct evaluation" techniques shown in class (count the number of operations at each step, count the number of steps, solve). (We used these on insertion sort and merge sort.) Show your work. Justify your answer. Problem in text format: HW1.txt

   
   Let p(x) denote a polynomial of degree n-1, i.e.,  
   
   
                 n-1
   	p(x) = åaixi, an-1 ¹ 0.
                 i=1 
   
   
   Input: A[0..n-1], the array of coefficients, and x the point at which to
   evaluate.  The size of the input is the size of the array A (note that some
   lower degree coefficients may be 0.) 
   Output: The value p(x).
   
   
   
   The procedure:
   
   PolyEval(A,x)
     value = a0
     for i=1 to n-1
        term = A[i]
        for j=1 to i
   	term = term * x
        value = value + term
     return value
   
   
   

2. Also, the following problems from Lewis and Denenberg, Chapter 1
   • #14 (3 points)
   • #16 (3 points)
   • #17 (3 points)
   • #22 (3 points)
   • #23 (3 points)
   • #36 (6 points)
   • #47 (3 points)
3. and these problems from Lewis and Denenberg, Chapter 2
   • #15 (3 points)
   • #17 (3 points)
   • #19 (3 points)
4. Give tight asymptotic bounds for T(n) in each of the following recurrences. Assume that T(1) = 1. (Use the master method) (2 pts each)
   • T(n) = 8T(n/2) + Theta(n^3 log n)
   • T(n) = 3T(n/2) + Theta(n)
   • T(n) = 3T(n/2) + Theta(n^2)
   • T(n) = 16T(n/2) + Theta(n^3 log n)
   • T(n) = T(9n/10) + Theta(n)
5. Create an Excel spreadsheet of the follow functions and plot them for various values of n (I suggest n=1,2,4,8, 16, 32). In order to fit them all on one page, you may need to reduce the number of values of n for some functions. (1 point)
   • f(n) = 2^(2^n)
   • f(n) = 2^(n^2)
   • f(n) = n!
   • f(n) = e^n
   • f(n) = n^x (let x = 3)
   • f(n) = ln n