Question 1 (25pt)
Given the input , track the divide-and-conquer algorithm to find the maximum contiguous subarray. You need to show the recursive calls as a tree. The input and output for each recursive call should also be indicated as well.
Question 2 (25pt)
Given two polynomials and , track the algorithm to calculate . You need to show the recursive calls as a tree. The input and output for each recursive call should also be indicated as well.
Question 3 (20pt)
In the deterministic linear-time divide-and-conquer algorithm taught in class for the selection problem, the input array is divided into groups of 5 elements. Analyze the running time of the algorithm if the input array is divided into groups of 7. Does your algorithm run in linear time?
Question 4 (15pt)
A segment is a pair of positive integers , where . Two segments and intersect if .
Given a sequence of segments sorted increasingly by ’s ( if ) within the ( for all ), design a divide-and-conquer algorithm to justify if there are two segments intersect.
You need to
a)Describe your algorithm in a high-level presentation. (5pt)
b)Write down the pseudo code. (5pt)
c)Analyze the time complexity of your algorithm. (5pt)
Question 5 (10pt)
In lecture 3, we studied the divide-and-conquer algorithm for the polynomial multiplication problem. To let polynomials evenly split into sub-polynomials, the algorithm on page 17 (Line 4 - 7) nicely considers all the cases and uses the ceiling function (the last term in is ).
However, Goliath is lazy. He does not want to use any ceiling function or floor function in his implementation. To make his life easy, he simply assumes that
“The number of terms in the polynomials is always an integer power of .”
In other words, for some .
But, the polynomial multiplication problem in general contains polynomials whose number of terms is not an integer power of 2. Thus, you need to
a)Define a method to convert polynomials in general to polynomials whose number of terms is an integer power of 2. (5pt)
b)Discuss the consequence by doing so. Does it increase the time complexity comparing to the original algorithm (Algorithm 2 on page 17 in lecture 03)? Why? (5pt)
(Hint: please pay attention to the input size)
Assume Goliath’s implementation has the interface . You can consider that the algorithm with Goliath’s implementation works as follows.
请加QQ：99515681 邮箱：99515681@qq.com WX：codinghelp