Question
Transcribed Text
Problem 1
Using iteration, obtain a tight asymptotic bound for T(n) given by the following recurrence. You
may assume that n is a power of 3.
T(n) = {
(
)
Problem 2
a). Show how to compute ac, ad+bc and bd using three multiplications, given reals a, b, c and d.
Note that since (ax+b)(cx+d) =abx2
+(ad+bc)x+bd, this result allows us to multiply two degreeone polynomials using three real multiplications).
b). Develop a divide-and-conquer algorithm for multiplying two degree-n polynomials
A(x)=anx
n
+….+a1x+a0 and
B(x)=bnx
n
+…+b1x+b0 in O(
) time, and prove the bound of the running time by writing and
analyzing a recurrence relation. You may assume that n is a power of 2. Your algorithm takes as
input coefficients an,…,a0, bn,….,b0 and outputs the coefficients c2n,…c1,c0 of the polynomial
C(x)=A(x)*B(x).
Note that is trivial to do this in O(n2
) time.
Solution Preview
These solutions may offer step-by-step problem-solving explanations or good writing examples that include modern styles of formatting and construction of bibliographies out of text citations and references. Students may use these solutions for personal skill-building and practice. Unethical use is strictly forbidden.
By purchasing this solution you'll be able to access the following files:
Solution.docx.
Return to homework library