CMI2011-B-06b

Question

Consider a plate stacked with several disks, each of a different diameter (they could all be, for instance, $\text{dosas}$ or $\text{chapatis}$ of different sizes). We want to sort these disks in decreasing order according to their diameter so that the widest disk is at the bottom of the pile. The only operation available for manipulating the disks is to pick up a stack of them from the top of the pile and invert that stack. (This corresponds to lifting up a stack $\text{dosas}$ or $\text{chapatis}$ between two big spoons and flipping the stack.)

How many steps will your algorithm take in the worst case?

Answer 1

This might sound too straightforward, but I guess the worst case performance would be O(2n) for 'n' elements.

Assumption : The given stack, only one operation is there, we can pick any arbitrary number of elements from the TOS and then flip them.

For worst case, we may assume that the desired element is not present at the bottom or top. It is present anywhere in the middle.

Consider a situation like this for the widest disk :

  ()                 (    )            ()

  ()                   ()              ()

  ()                   ()              ()

(     )       =>     ()     =>     ()   

  ()                   ()              ()

  ()                   ()            (     )

 (i.)                  (ii.)            (iii.)

Thus, we need two operations in worst case, to bring the current widest disk to bottom. Then, we will call the algorithm for the remaining elements, to make the second widest disk to the bottom.

Thus, in worst case, we need 2n operations for this.

Comments

For anyone who still not understood,

suppose a stack with five disks in it. the largest disks is somewhere in middle or middle-top. To send it to bottom we can only remove elements the TOS or invert the stack(but this won't work unless largest disks is already on top), so we have to bring it back to top (n operation for that) and then invert the stack( n operation for that, So total 2n operations)