Question

Let An = {ai} n i=1 denote a list of n distinct positive integers. The median mA of An is a value in An such that half the elements in An are less than m (and so, the other half are greater than or equal m). In fact, the median element is said to have a middle rank. (a) Develop an algorithm that uses Sorting to return mA given An. (6%) (b) Now assume that one is given another list Bn = {bi} n i=1 of n distinct positive integers whose median mB is already known. Develop an algorithm that returns the sum of the two elements with value closest to mB, such that one of them is greater than mB and the other is lower than mB. Although sorting Bn would yield a quick solution, we will see later on that this is a exhorbitantly slow process and one can solve the problem without sorting Bn in singnificantly faster time. Hence, in your solution, Do Not Sort Bn and propose a solution that goes without Sorting. (6%) (c) State a loop invariant for the algorithm you proposed in part (b) above.(6%) (d) Prove the loop invariant you proposed in part (c) above

Answer 1

please please thumbs up!!!

hope it will help uh out!!!

Solution::
(TYPED)
-------------------------------------------

Answer A:: ALGORITHMS

Algorithm partition (A_n, low, high)

    Input: a list of n integers and lowest & highest indexes

    Output: partitioning index

    pivot ← A[high]

    i ← low – 1

  for j = low to high-1

         if A[j] < pivot

            i ← i + 1

           swap A[i] and A[j]

swap A[i+1] and A[high]

   return (i+1)

Algorithm quicksort (A_n, low, high)

    Input: a list of n integers and lowest & highest indexes

    Output: nothing

       if low < high

         pi ← partition (A_n, low, high)

         quicksort (A_n, low, pi-1)

         quicksort (A_n, pi+1, high)

Algorithm median (A_n)

Input: a list of n integers

Output: median of the data

    quicksort (A_n, 0, n-1)

if n%2 ≠ 0

         return A[n/2]

   else

         return (A[n/2]+A[(n/2)+1])/2

---------------------------------------------------------

Answer :: B

Algorithm find_pair (A_n, m_B)

    Input: a list of n integers and its median

    Output: the two required numbers

    x ← -INF/2

     y ← +INF/2

for i = 0 to n-1

      for j = 0 to n-1

       if A[i]< m_B and A[j]> m_B and |m_B-(A[i]+A[j])| < |m_B –(x+y)|

                 x = A[i]

                 y = A[j]

    return (x,y)

---------------------------------------------------

Answer :: (C)

Here In Part (B)  It is true for every iteration that x < mB and y > mB.

_{--------------------------------------}

Answer :: (D)

Since, x and y are initialized to minus infinity and infinity respectively and they get changed to A[i] and A[j] respectively, in each iteration of the loop if at least both A[i] < m_B & A[j] >m_B are true, therefore both loop invariants should also be true.