(31 points) Suppose you are given

k

sorted non-empty lists

A_(1),dots,A_(k)

that consist of

n

elements in total. Your task is to merge them into one big sorted list. We will use the merge procedure described in class, which can merge two lists into one in linear time, i.e., in

\\\\Theta (n_(1)+n_(2))

time where

n_(1)

and

n_(2)

are the sizes of the two input lists, respectively. You may assume that

k

is a power of 2 .\ (a) (5 points) Consider the following simple iterative algorithm: First merge

A_(1)

and

A_(2)

into one list, then merge the resulting list with

A_(3)

, then

A_(4),dots,A_(k)

. Show that the (worst-case) running time of this algorithm is

O(nk)

.\ (b) (2 points) Show that the

O(nk)

running time is tight, i.e., its running time is also

\\\\Omega (nk)

, thus

\\\\Theta (nk)

.\ (c) (2 points) What's the best-case running time of this iterative algorithm? Explain.\ (d) (14 points) Design a divide-and-conquer algorithm that has a running time better than

O(nk)

. Analyze the running time of your divideand-conquer algorithm. [Hint: Denote the sizes of the

k

input lists as

n_(1),dots,n_(k)

. Note that

n_(1)+cdots+n_(k)=n

. Use

T(i,j)

to denote the running time of your algorithm when it is recursively run on

A_(i),dots,A_(j)

. Then write a recurrence on

T(i,j)

and solve it for

T(1,k)

. ]\ (e) (8 points) Suppose we know that the size of

A_(i)

is

2^(i)

for

i=1,dots,k

. In this case, which algorithm is better, your divide-and-conquer algorithm or the iterative algorithm? Analyze the running times of these two algorithms to compare. Note that in this case we always have

n=1+2+4+cdots+2^(k)=2^(k+1)-1

, so the running time is a function of only one parameter, which can be either

n

or

k

.

4. (31 points) Suppose you are given k sorted non-empty lists A1,,Ak that consist of n elements in total. Your task is to merge them into one big sorted list. We will use the merge procedure described in class, which can merge two lists into one in linear time, i.e., in (n1+n2) time where n1 and n2 are the sizes of the two input lists, respectively. You may assume that k is a power of 2 . (a) (5 points) Consider the following simple iterative algorithm: First merge A1 and A2 into one list, then merge the resulting list with A3, then A4,,Ak. Show that the (worst-case) running time of this algorithm is O(nk). (b) (2 points) Show that the O(nk) running time is tight, i.e., its running time is also (nk), thus (nk). (c) (2 points) What's the best-case running time of this iterative algorithm? Explain. (d) (14 points) Design a divide-and-conquer algorithm that has a running time better than O(nk). Analyze the running time of your divideand-conquer algorithm. [Hint: Denote the sizes of the k input lists as n1,,nk. Note that n1++nk=n. Use T(i,j) to denote the running time of your algorithm when it is recursively run on Ai,,Aj. Then write a recurrence on T(i,j) and solve it for T(1,k). ] (e) (8 points) Suppose we know that the size of Ai is 2i for i=1,,k. In this case, which algorithm is better, your divide-and-conquer algorithm or the iterative algorithm? Analyze the running times of these two algorithms to compare. Note that in this case we always have n=1+2+4++2k=2k+11, so the running time is a function of only one parameter, which can be either n or k