Modify the Strassen’s matrix multiplication algorithm when n is not a power of 2 and analyze...

Modify the Strassen’s matrix multiplication algorithm when n is not a power of 2 and analyze its time complexity. 2. Show how to apply the fast Fourier Transform to multiply two polynomials A(x) = a0+a1x+a2x 2+· · ·+an-1x n-1 of degree n-1 and B(x) = b0+b1x+b2x 2+· · ·+b3n-1x 3n-1 of degree 3n - 1 when n is a power of 2. 3. Given an undirected graph G = (V, E), design an algorithm to find a minimal vertex cover C ? V so that for each (v, w) in E, at least one of v or w is in C, and there is no other vertex cover C ' ? C. Analyze its time complexity. 4. Given an undirected graph G = (V, E), a matching M is a subset of E so that for each v in V , at most one edge of M is incident on v. Show that the ordered pair (S, l) with S = E and l being the set of all matchings in G is not a matroid. 5. Given a number a, design a dynamic programming algorithm to compute a n for integer n > 0 and analyze its time complexity

Document Preview:

CSCE 629-600 Homework 2 (Due Feb. 13)
1. Modify the Strassen’s matrix multiplication algorithm when n is not a power of 2 and
analyze its time complexity.
2. Show how to apply the fast Fourier Transform to multiply two polynomials A(x) =
2 n-1 2 3n-1
a +a x+a x +···+a x ofdegreen-1andB(x) =b +b x+b x +···+b x
0 1 2 n-1 0 1 2 3n-1
of degree 3n-1 when n is a power of 2.
3. Given an undirected graph G = (V,E), design an algorithm to ?nd a minimal vertex
cover C ? V so that for each (v,w) in E, at least one of v or w is in C, and there is
'
no other vertex cover C ?C. Analyze its time complexity.
4. Given an undirected graphG = (V,E), a matchingM is a subset ofE so that for each
v inV, at most one edge ofM is incident onv. Show that the ordered pair (S,l) with
S =E and l being the set of all matchings in G is not a matroid.
n
5. Given a numbera, design a dynamic programming algorithmto computea for integer
n> 0 and analyze its time complexity.