Consider the following algorithm Poly(A,a) --------------- 1. n = degree of polynomial (with coef A[n],..,A[0]) 2....

Question

Question

Consider the following algorithm

Poly(A,a)

---------------

1. n = degree of polynomial (with coef A[n],..,A[0])

2. sum = 0

3. for i = n downto 0

4. sum = sum * a +A[i]

show all steps！！

(a) Determine the running time of the algorithm, your work should explain your answer

(b) what is the loop invariant property of the loop in line 3.

Answer 1

Answer #1

Answer 2

Similar Homework Help Questions

Consider the following algorithm (known as Horner's rule) to evaluate f(x) = sigma_i=0^x a, x^i; poly...

Consider the following algorithm (known as Horner's rule) to evaluate f(x) = sigma_i=0^x a, x^i; poly = 0; for(i=n; i>=0; i--) poly = x * poly + a_i a. Show how the steps are performed by this algorithm for x = 3, f(x) = 4x + 8x + x + 2. b. Explain why this algorithm works. c. What is the running time of this algorithm?
f(x) = 2.10 Consider the following algorithm (known as Horner's rule) to evaluate -ax': poly =...

f(x) = 2.10 Consider the following algorithm (known as Horner's rule) to evaluate -ax': poly = 0; for( i=n; i>=0; i--) poly = x * poly + ai a. Show how the steps are performed by this algorithm for x = 3, f(x) = 4x + 8x + x + 2. b. Explain why this algorithm works. c. What is the running time of this algorithm?
The polynomial addition C function of Program 2.6 padd is the code when the polynomial is used to...

The polynomial addition C function of Program 2.6 padd is the code when the polynomial is used to arrange the polynomial in the two arrangement methods of the polynomial described in the text 2.4.2. For the remaining method, when the expression polynomial is arranged by a coefficient, create a polynomial addition C function padd() corresponding to Program 2.6. 66 Arrays And Structures are zero are not displayed. The term with exponent equal to zero does not shouw able since x...

Poly-Poly + a[i] * power 6. (15%) Consider the nested loops shown below, where N is...

Poly-Poly + a[i] * power 6. (15%) Consider the nested loops shown below, where N is assumed to be a power of 2. i.e., N-2 for some positive integer k. i=N; while (i>-1){ while (j =N){ j-2 *j; i=i/2. a) Determine the number of outer iterations (associated with the outer while loop) to be executed? Show your work. b) For each outer iteration (for each value of i), determine the number of iterations of the inner while loop to be...
Consider the following algorithm. ALGORITHM Enigma(A[0.n - 1]) //Input: An array A[0.n - 1] of integer...

Consider the following algorithm. ALGORITHM Enigma(A[0.n - 1]) //Input: An array A[0.n - 1] of integer numbers for i leftarrow 0 to n - 2 do for j leftarrow i +1 to n - 1 do if A[i] = = A[j] return false return true a) What does this algorithm do? b) Compute the running time of this algorithm.
(15 points) Consider the algorithm for insertion sort shown below. The input to this algorithm is...

(15 points) Consider the algorithm for insertion sort shown below. The input to this algorithm is an earray A. You must assume that indexing begins at 1. 1: for j = 2: A.length do key = A i=j-1 while i > 0 and A[i] > key do Ali + 1] = Ai i=i-1 7: A[i+1] = key (a) Follow this algorithm for A[1..4) =< 7,9,6,8 >. Specifically, please indicate the contents of the array after each iteration of the outer...

2. The polynomial p of degree n that interpolates a given function f at n+1 prescribed nodes is u...

Please answer problem 4, thank you. 2. The polynomial p of degree n that interpolates a given function f at n+1 prescribed nodes is uniquely defined. Hence, there is a mapping f -> p. Denote this mapping by L and show that rl Show that L is linear; that is, 3. Prove that the algorithm for computing the coefficients ci in the Newton form of the interpolating polynomial involves n long operations (multiplications and divisions 4. Refer to Problem 2,...
i=n Consider the following procedure to evaluate a polynomial a;x' at x = C. i =...

i=n Consider the following procedure to evaluate a polynomial a;x' at x = C. i = 0 procedure poly(ca ,...an power + 1 y cao for i from iton power + power * y+y+a; power return y where + denotes assignment, * denotes multiplication. Evaluate 3x2 + x + 1 at x = 2 by stepping through the algorithm.
3. (12 points) Consider the following sum: n Sn = {(i + 1)(i +2) i=0 (a)...

3. (12 points) Consider the following sum: n Sn = {(i + 1)(i +2) i=0 (a) Use properties of summations to find a closed form expression for Sn. Simplify your answer into a polynomial with rational coefficients. Show your work, and clearly indicate your final answer. (b) Use weak induction to prove that your closed form works for every integer n > 0. Make sure you include all three parts, and label them appropriately!

6. [8 marks Consider the sequence 10, 11, ... defined by To = 0, 11 =...

6. [8 marks Consider the sequence 10, 11, ... defined by To = 0, 11 = 1, and ri = i-1 + 24-2 for all i > 2. Consider the following algorithm that attempts to compute the value In, given an n > 0. Algorithm 6 1: //pre: (n e Z) ^ (n > 0) 2: if n == 0 then 3: bro 1: else 5: a 0 6: 5+ 1 it1 //LoopInv: while i<n do ct a+b atb bc...