1
$\begingroup$

I am new to this site, I hope to contribute. For now i have the following problem of recurrences in a subject of discrete mathematics:

Consider the algorithm, called StoogeSort in honor of the immortal Moe, Curly and Larry. The swap operation (x, y) exchanges the values of x and y.

Algorithm StoogeSort:
procedure StoogeSort(A[0...n −1])
    if n = 2 ∧ A[0] > A[1] then
        swap(A[0], A[1])
    else if n > 2 then
        m = ceil(2n/3)
        StoogeSort(A[0...m−1])
        StoogeSort(A[n−m ...n−1])
        StoogeSort(A[0...m−1])
    end
end

The problem demands the following:

  • Show that the algorithm correctly orders the array A of n elements.
  • Would it work correctly if we replaced ceil($\frac{2n}{3}$) with floor($\frac{2n}{3}$)? Justify your answer.
  • Give a recurrence for the number of comparisons between elements of A that StoogeSort performs with n elements.
  • Solve the recurrence for the number of comparisons. (Hint: skip functions ceil and functions floors, solve exactly the result.)
  • Show that you execute at most $ {n}\choose{2} $ swap operations. (Hint: How many comparisons are required to locate the element in position k if it is at Start?)

I intuit that item two works changing ceil by floor so if the length of the arrangement is odd it does not matter if I take the larger half at the beginning or after the middle of the arrangement but how do I show this?.

The other items I still have no idea how I could solve them. Thanks in advance

$\endgroup$
2
  • $\begingroup$ Examine what happens for A = [4,3,2,1] if you use floor instead of ceil. $\endgroup$
    – Paul Sinclair
    Commented May 7, 2019 at 0:25
  • $\begingroup$ For the first bullet, use induction: It is easy to see it works for 1 or 2 items. Prove that if it works for $n-1$ or fewer items, then it also works for $n$ items. For the 3rd & 4th bullets, $c_1 = 0, c_2 = 1$ and $c_n = 3c_m$. For the final bullet, show that any pair of items is never swapped more than once. $\endgroup$
    – Paul Sinclair
    Commented May 7, 2019 at 2:47

0

Reset to default

You must log in to answer this question.