Can somebody please help me with these problems? These are from the textbook Fou
ID: 670921 • Letter: C
Question
Can somebody please help me with these problems? These are from the textbook Foundations of Algorithms by Richard Neapolitan and Kumarss Naimipour.
7. Use the divide-and-conquer approach to write an algorithm that finds the largest item in a list of n items. Analyze your algorithm, and show the results in order notation.
13. Write an algorithm that sorts a list of n items by dividing it into three sublists of about n/3 items, sorting each sublist recursively and merging the three sorted sublists. Analyze your algorithm, and give the results under order notation.
16. Suppose that, in a divide-and conquer algorithm, we always divide an instance of size n of a problem into 10 subinstances of size n/3, and the dividing and combining steps take a time in (n2) . Write a recurrence equation for the running time T(n), and solve the equation for T(n).
37. Use the divide-and-conquer approach to write a recursive algorithm that computes n!. Define the input size and answer the following questions. Does your function have an exponential time complexity? Does this violate the statement of case 1 given in Section 2.8? The statement of case 1 is: 1. An instance of size n is divided into two or more instances each almost of size n.
38. Suppose that, in a divide-andconquer algorithm, we always divide an instance of size n of a problem into n subinstances of size n/3, and the dividing and combining steps take linear time. Write a recurrence equation for the running time T(n), and solve this recurrence equation for T(n). Show your solution in order notation.
Thank you!
Explanation / Answer
7.
int findMax(keytype s[low...high], index low, index high)
{
if (low > high) return 0;
else if (low == high) return s[low];
else
{
int a = findMax(low, floor( (high - low) / 2) + low);
int b = findMax(floor( (high - low) / 2) + low + 1, high);
if(a > b)
{
return a;
}
else return b;
}
}
b.) There is no best, worst or average case. We then look for the every time complexity.
Let's look at an example:
[1 2 3 4 5 6 7 8]
0
[1 2 3 4] | [5 6 7 8]
n / 8 = n / 8 comparisons
[1 2] | [3 4] | [5 6] | [7 8]
n / 8 + n / 8 = n / 4 comparisons
[1] | [2] | [3] | [4] | [5] | [6] | [7] | [8]
n/8 + n/8 + n/8 + n/8 = n / 2 comparisons
So n / 2 + n / 22 + n / 23 +... + n / n (1) = T(n)
Try some values of n:
T(2) = 2 / 2 = 1
T(4) = 4 / 2 + 4 / 4 = 2 + 1 = 3
T(8) = 8 / 2 + 8 / 4 + 8 / 8 = 7
Thus, T(n) = n - 1
c.) Let's check. We can just use a straightforward loop comparison:
int findMax(low, high)
{
int max = 0;
for(index i = low; i <= high; i++)
if( list[i] > max )
max = list[i];
}
This will find the largest element in n - 1 comparisons, thus T(n) = n - 1. It's the same time complexity as the divide and conquer approach.