How many multiplications did you perform

Assignment Help Data Structure & Algorithms
Reference no: EM131719638

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;k<m1;k+=2)
RF[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;k<m1;k+=2)
C[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 x7 + 4x6 + 3x5 - x4 + 2x3 + 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:

604_Matrix.jpg

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:

3x1 + 6x2 + 2x3 =5
x1 + 4x2+ 2x3=7
2x1+ 5x2 + 4x3=9

Reference no: EM131719638

Questions Cloud

Essay compare on the tale of sohrab : This is a closed reading essay without any outside sources other then the two above mentioned works
What are productivity apps : What are productivity apps and how can they increase productivity in the work environment.
People who have seen ufos tell their story : People Who Have Seen UFOs Tell Their Story, The probability of that extraterrestrial aliens actually are visiting Earth
Indirect exporting and joint venturing companies : What are some examples of direct exporting, indirect exporting and joint venturing companies?
How many multiplications did you perform : How many additions did you perform, and how many multiplications did you perform. How many useless additions and multiplications did you perform?
Discuss problem related to the relative frequencies : Based on a sample of 100 individuals, the values 1, 2, 3, 4, 5 are observed with relative frequencies 0.2, 0.3, 0.1, 0.25, 0.15.
Property manager for prestige ville : You are the Property Manager for Prestige Ville, and the Corporate office has provided you with information that must be shared with all tenants.
Complete list of adequacy criteria for moral judgments : "Although there is no complete list of adequacy criteria for moral judgments, moral judgments have certain requirements that should be followed".
What are the benefits of taking the time to prepare a plan : What are the benefits of taking the time to prepare a full lesson plan? Describe the ways in which this process would enrich your teaching

Reviews

Write a Review

Data Structure & Algorithms Questions & Answers

  Implement an open hash table

In this programming assignment you will implement an open hash table and compare the performance of four hash functions using various prime table sizes.

  Use a search tree to find the solution

Explain how will use a search tree to find the solution.

  How to access virtualised applications through unicore

How to access virtualised applications through UNICORE

  Recursive tree algorithms

Write a recursive function to determine if a binary tree is a binary search tree.

  Determine the mean salary as well as the number of salaries

Determine the mean salary as well as the number of salaries.

  Currency conversion development

Currency Conversion Development

  Cloud computing assignment

WSDL service that receives a request for a stock market quote and returns the quote

  Design a gui and implement tic tac toe game in java

Design a GUI and implement Tic Tac Toe game in java

  Recursive implementation of euclids algorithm

Write a recursive implementation of Euclid's algorithm for finding the greatest common divisor (GCD) of two integers

  Data structures for a single algorithm

Data structures for a single algorithm

  Write the selection sort algorithm

Write the selection sort algorithm

  Design of sample and hold amplifiers for 100 msps by using n

The report is divided into four main parts. The introduction about sample, hold amplifier and design, bootstrap switch design followed by simulation results.

Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd