You are given an array A of distinct integers of size n. The sequence A[1], A[2]

Question

You are given an array A of distinct integers of size n. The sequence A[1], A[2], A[n] is unimodal if for some index k between 1 and n the values increase up to position k and then decrease the reminder of the way until position n. Propose a recursive algorithm to find the peak entry k of a unimodal array by reading at most O(lg n) entries of A. Write the recurrence relation and solve it to show that the complexity of your algorithm is indeed O(lg n). Solve using repeated substitutions, the following recurrence equations with C(I) = 1, and show all your work. C(n) = 2C(n/2)+ log n An algorithm decomposes (divides) a problem of size n into b sub-problems each of size n/b where b is an integer. The cost of decomposition is n, and C(l) = l. Show, using repeated substitution, that for all values of b 2, the complexity of the algorithm is O(n lg n). Given two sorted arrays A and B, each of size n. Provide an algorithm to find the median of A B (union or combination of A and B) with the running time complexity of O(lg n ). Note that the median of array elements is a number such that half the elements (round down) are less than that number and half are at least as large as that number.

Explanation / Answer

1)Given: An array A of distinct integers of size n. The sequence A[1], A[2], A[n] is unimodal(i.e only one maximum value exists for the set) if for some index k between 1 and n the values increase up to position k and then decrease the reminder of the way until position n.

We have to find recursive algorithm to find the peak entry k of a unimodal array by reading at most O(lg n) entries of A.

a)The algorithm is as follows:

Recurse through A[n2 - 1], A[n2 ], A[n2 + 1] to determine if n2 is on the upslope (before k), downslope (after k), or is the peak.

If we are on the downslope, then recurse on indices 1 ….(n2 - 1) and if we are on the upslope, recurse on indices (n2 + 1 )… n

b)The recurrence relation to show the complexity of our algorithm is O(lg n).

The number of accesses of A is bounded by the recurrence T (n)<= T (n/2) + 3 for n>= 4 and T (3)<= 3. Substituting T (n) = 3 log2 n - 3 log2(32 ) =3 log2 n -15

solves the recurrence and gives the final complexity as O(log2 n) which is O(lg n) finally.

2) a)Solve using repeated substitutions, the following recurrence equations with C(I) = 1, and show all your work. C(n) = 2C(n/2)+ log n

Substitution method:

Base case,C(0)=2C(0)+log 0=0

C(1)=1

We guess the solution as C(n) = O(nlogn). Now we use induction

to prove our guess.

We need to prove that C(n) <= cnLogn. We can assume that it is true for values smaller than n.

C(n) = 2C(n/2) + logn

    <= cn/2Log(n/2) + logn

    = cnLogn - cnLog2 + logn

    = cnLogn - cn + logn

    <= (cn+1)Logn-cn

Hence , our guess is that C(n)<=cnlogn

Repeated substitution:

C(n) = 2C(n/2) + logn

        =2C(n/2^1)+log n/2^0

         =2C(n/2^2)+log n/2^1

        =2C(n/2^3)+log n/2^2

         =2C(n/2^4)+log n/2^3

       =2C(n/2^5)+log n/2^4

   C(n)   =2C(n/2^n-1)+log n/2^n-2

Let k=2^n,n =log2( k)

C(n)=2C(2n/k)+log(4 n/k)

      =2C(2n/k)+log (4n/k)

      =2C(2*log2 (k)/k)+4log ( n/k)

      =2C(1)+4 log (n/k)

=2*1+4log (n/k)

O(n)=log(n)

b)An algorithm decomposes (divides) a problem of size n into b sub-problems each of size n/b where b is an integer. The cost of decomposition is n, and C(l) = l. Show, using repeated substitution, that for all values of b >=2, the complexity of the algorithm is O(n lg n).

Total cost=n

No of subproblems=b of size n/b

Height of a recurrence tree=log n

               Level(b)        Per level cost of decomposition   

                  1(root)            n

                

                  2                2*(n/2)=n

                  4                 4*(n/4)=n

Total cost= n *logn +n   (for logn levels + 1 level)

T(n)=O(nlogn)

                 

T(n)= T(n/b)+b*nlogn

       For, b>=2 we need to prove the complexity as O(nlogn)

T(n)=T(n/2)+2nlogn

        Using repeated substitution,

T(n)=T(n/2^2)+2*n/2 log n/2

       =T(n/2^2)+n logn/2

      =T(n/2^4)+n/2^2 log n/2^3

      =T(n/2^8)+n/2^6 log n/2^7

     =T(n/2^k)+n/2^k-2 log n/2^k-1

Let n=2^k,

T(n)=T(n/n)+2n/2^k - 4 logn/2^k

        =T(1)++ cn/2^k - c logn/2^k (T(1)=1 given)

T(n)=O(nlogn)

3) Given :Two sorted arrays A and B, each of size n.

Median of array elements is a number such that half the elements (round down) are less than that number and half are at least as large as that number.

Provide an algorithm to find the median of A B (union or combination of A and B) with the running time complexity of O(lg n ).

Proof: If size of array is odd, then middle element is median

      If size of array is even, then average of both middle elements is median.

Size of merged array will be n+n=2n

  Algorithm:

For A :1 to mA

For B: mB to n

For A :mA to n

For B: 1 to mB

    

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.