Assignment

1. Trace the operation of Quicksort on the list [23, 17, 21, 3, 42, 9, 13, 1, 2, 7, 35, 4]. Show the list order and the stack of (first, last, pivot) values at the start of every call. Count the number of comparisons and swaps that are done.

//Winograds Method
matMuftWragrad(A, B, C, m0, m1, m2)
for(i = 1; i ≤ m0; i++)
RF[i] = 0
for(k=1;kRF[i] = RF[i] + A[i][k] * A[i][k + 1]
for(j = 1; j ≤ m2; j++)
CF[j] = 0
for(k = 1; k < m1; k += 2)
CF[j] = CF[j] + B[k][j] B[k + 1)(j]
for(i = 1; i ≤ m0; i++)
for(j = 1; j ≤ m2; j++)
C[i][j] = -RF[i] - CF[j]
for(k=1;kC[i][j] = -C[i][j] + (A[i][k] + B[k +  1][j]) * (A[i][k + 1] + B[k][j])

2. Give the factorization of the equation x⁷ + 4x⁶ + 3x⁵ - x⁴ + 2x³ + 5x - 9 that results from Horner's method. Also show the result value for each pass of Homer's method using the input x = 3 with the given polynomial.

3. The following algorithm is a variation of the standard polynomial evaluation method. How many (a) additions and (b) multiplications are performed by the algorithm for a polynomial of degree n?

eval(x)
pow = 1
for(i = n; i ≥ 1; --i)
pow = pow * x
result = 0
powsave = pow
for(i = 1; i ≤ n; i++)
result = result + a[i] * (powsave / pow)
pow = pow / x
return (result)

4. You are to use the algorithm for Winograd's Method given on Handout #5 to multiply the following two matrices:

a. Give the contents of the the CF and RF arrays.

b. For each result element Cu give the value of the cross products. Show your work.

c. Add the row factor, column factor, and the cross product term together to get the final value , and show the resulting C array.

d. How many additions did you perform, and how many multiplications did you perform.

e. How many useless additions and multiplications did you perform? (A useless operation is one in which one of the operands is 0.)

5. Show the steps in the Gauss-Jordan algorithm for the following system of linear equations:

3x₁ + 6x₂ + 2x₃ =5
x₁ + 4x₂+ 2x₃=7
2x₁+ 5x₂ + 4x₃=9