1. Analyze the time complexity of the following variant of merge sort: divide the array into...

 

Transcribed Image Text:

1. Analyze the time complexity of the following variant of merge sort: divide the array into three parts, sort each part recursively, and merge the results. 2. Design an algorithm to search for log n unsorted elements within a sorted list of n elements and analyze its time complexity. = 2n-1 3. Show how to apply the fast Fourier Transform to multiply two polynomials A(x) 90+a1x+a2x+...+an-12-1 of degree n-1 and B(x) = b+bx+b2x+ +b2n1221 of degree 2n-1 when n is a power of 2. 4. Show that the number of edges in a spanning forest of an undirected graph is n - c, where n is the number of vertices and c is the number of connected components. 5. Design an algorithm to find a maximal matching in an undirected graph and analyze its time complexity. A maximal matching is not necessarily a maximum matching but is a matching that is not a proper subset of any other matching. 1. Analyze the time complexity of the following variant of merge sort: divide the array into three parts, sort each part recursively, and merge the results. 2. Design an algorithm to search for log n unsorted elements within a sorted list of n elements and analyze its time complexity. = 2n-1 3. Show how to apply the fast Fourier Transform to multiply two polynomials A(x) 90+a1x+a2x+...+an-12-1 of degree n-1 and B(x) = b+bx+b2x+ +b2n1221 of degree 2n-1 when n is a power of 2. 4. Show that the number of edges in a spanning forest of an undirected graph is n - c, where n is the number of vertices and c is the number of connected components. 5. Design an algorithm to find a maximal matching in an undirected graph and analyze its time complexity. A maximal matching is not necessarily a maximum matching but is a matching that is not a proper subset of any other matching.