Question

xxxxxxxxxxxxxxxxxxxxxxxxxxxxx

xxx In this year’s runner's competition, there are x contestants participating in the women's  100m freestyle. They are divided into y equal-size groups before the first round, each containing n runners.

xxx Imagine we obtained a list containing all of the times by each runner for the first round.  Construct a divide-and-conquer algorithm with Θ(mlogm) worst-case runtime complexity to generate a complete list of ascending time performances. HINT: You may need to use two functions.

xxxa) Provide the pseudocode for your algorithm.

xxx(b) Worst case runtime complexity for your algorithm? Use the Master Theorem.

Answer 1

Divide and Conquer is a strategy used to recursively split the data contents into individual data units, so that those individual data units can be easily solved and those individual solutions can be combined together to form the final solution.

• We have X number of contestants
• We have Y number of groups having equal number of runners
• Each group has N number of runners
• Therefore X = Y x N
• The list contains the time performances of all the athletes, (i.e) the list contains x number of time performances.
• Now we construct a divide and conquer algorithm to generate a list that contains the time performances of all the athletes sorted in ascending order.

a) Pseudocode for the algorithm:

Procedure divide(list)

    mid length(list) / 2

    left[] list[0] to list[mid]

    right[] list[mid+1] to list[length(list) -1]

    divide(left)

    divide(right)

    Display conquer(left,right)

end procedure

Procedure conquer(left,right)

    i 0

    while (left and right is not empty)

        if (left[i] < right[i]) then

      temp[i] left[i]

increment i

              remove left[i]

        else

              temp[i] right[i]

              increment i

              remove right[i]

          end if

    end while

     p length(temp)

    while (left is not empty)

         temp[p] left[]

     end while

     while (right is not empty)

         temp[p] right[]

     end while

    return temp[]

end procedure

Explanation of the pseudocode:

• In Procedure divide(list), the list contains all the time performances
• We divide the list into two equal halves by finding the mid element
• We defined two arrays named as left and right to store the divided arrays
• The process is a recursive one until we store a single data into an array, i.e each array contains one value
• We recursively called the function divide(left) and divide(right) to achieve that.
• Next we called the Conquer function to sort the individual values.
• If the left array value is lesser than the right array value, then that value gets stored to a temporary array.
• If the right array value is lesser than the left array value, then that value gets stored to a temporary array.
• Each and every value will be stored to the temporary array, if any values did not get stored in the temporary array, we use the while loop to store the remaining values {temp[] left[] and temp[] right[]}

Finally we are returning the temporary array to display/print the values in ascending order.

b) Masters method to find the worst time complexity:

If we have a divide and conquer recurrence of the form

T(n) = aT(n/b) + f(n)

where a ≥ 1, b > 1, and f(n) > 0 is asymptotically positive,

then we can apply the master method, which is based on the master theorem. We compare f(n) to n^log_ba under asymptotic (in)equality:

Case 1: f(n) = O(n^{log_ba - ε}) for some constant ε > 0.
(That is, f(n) is polynomially smaller than n^log_ba.)
Solution: T(n) = Θ(n^log_ba).
Intuitively: the cost is dominated by the leaves.

Case 2: f(n) = Θ(n^log_ba), or more generally (exercise 4.6-2): f(n) = Θ(n^log_balg^kn), where k ≥ 0.
(That is, f(n) is within a polylog factor of n^log_ba, but not smaller.)
Solution: T(n) = Θ(n^log_balgn), or T(n) = Θ(n^log_balg^k+1n) in the more general case.
Intuitively: the cost is n^log_balg^k at each level and there are Θ(lgn) levels.

Case 3: f(n)= Ω(n^{log_ba + ε}) for some constant ε > 0, and f(n) satisfies the regularity condition af(n/b) ≤ cf(n) for some constant c<1 and all sufficiently large n.
(That is, f(n) is polynomially greater than n^log_ba.)
Solution: T(n) = Θ(f(n)),
Intuitively: the cost is dominated by the root.