Can somebody please help me with these problems? These are from the textbook Fou
ID: 671151 • 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.
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).
Explanation / Answer
13) We’re doing a three-way merging version of Mergesort.
You may write the pseudocode according to your preferred style, as long as it is clear and correct! I have marked comments with a “#” sign.
Inputs: positive integer n ; array of keys S indexed from 1 to n.
Outputs: the array S containing the keys in nondecreasing order.
procedure MERGESORT3 (n ; var S);
# var will ensure that the changes we make to S will be retained.
const
third = floor (n=3);
var
U: array [1::third];
V : array [1::third];
W: array [1::(n 2 third)];
U V : array [1::(2 third)];
# This array will consist of the keys in both U and V in sorted
# (nondecreasing) order. This is a stepping stone to merging all three
# sorted sublists.
begin
if n = 2 then
sort(S)
# We assume you know how to write the code for this case
# (when S has only two elements).
elseif n > 1 then
copy S[1] through S[third] to U;
copy S[third + 1] through S[2 third] to V ;
copy S[2 third + 1] through S[n] to W;
MERGESORT3(third; U);
MERGESORT3(third; V );
MERGESORT3(n 2 third; W);
MERGE(third; third; U; V ; U V );
# The inputs to MERGE are: h and m (the lengths of the two sorted # arrays to be merged), the arrays themselves, and the var-ed array that # will contain the keys in the two smaller arrays in sorted (nondecreasing) # order. MERGE is O(h + m 1), which means that it is O(n) in the # larger context of MERGESORT3.
MERGE(2 third; n 2 third; U V ; W; S);
end
end;
The master theorem will aid us in our time complexity analysis. Let us consider W(n), the worst-case time complexity function. The recurrence relation is: W(n) = 3W(n=3) + O(n) (don’t worry about floors and ceilings here). Remember that MERGE is O(n), with its worst-case W(n) (n) ; the copy operations are also O(n), if you would like to count those. So, we will use the master theorem with a = 3; b = 3; and f (n) (n) and O(n). Then, nlogba = nlog33 = n1 = n. We are in case 2 of the master theorem, and thus W(n) (nlgn). E
16)