Re: The sky's the limit! (Quickort on posets.)

[Hosam Mahmoud <hosam@xxxxxxx>]

    Dear Marko:

	Sounds that there are nice problems there. Someone may ask what is
the motivation?

    *********************************************************************
    * Hosam M. Mahmoud                 |                                *
    * Department of Statistics         |Viens, prends la coupe,         *
    * The George Washington University |                                *
    * Washington, DC 20052             |                                *
    * U.S.A.                           | et laisse Mahmoud a son empire!*
    * Telephone: +1 (202) 994-6667     |                                *
    * Fax:       +1 (202) 994-6917     |                                *
    * http://home.gwu.edu/~hosam       |                                *
    *********************************************************************


On Fri, 16 Jan 2004, Marko Riedel wrote:

>
> Hi folks,
>
> I am so very grateful for your cooperation regarding the quickselect
> disorder paper! I would like to return the favor by sharing an idea
> that may well prove quite interesting, and, I believe, could perhaps
> generate enough material for a paper, so read the following
> closely. The diagrams will only work if your mail user agent uses a
> fixed-width font.
>
> Goal: exact analysis of quicksort on posets.
>
> Observation: classic quicksort produces the poset consisting of a
> single chain.
>
>     *
>     |
>     *
>     |
>     *
>     |     <- n items
>     *
>     |
>     *
>     |
>     *
>     |
>     *
>
> However, there's an infinite number of non-trivial posets that can be
> produced with a modified quicksort. I show two examples:
>
> I: fork.
>
>
>     *
>     |
>     *
>     |     <- n/2 items
>     *
>     |
>     *
>     |
>     *
>    / \
>   *   *            <- 2 x n/4 items
>  /     \
> *       *
>
> This poset is produced by recursing as long as the interval being
> sorted is partially or completely above the middle. The first interval
> to contain all of the upper half of the data set triggers a subsequent
> additional traditional quicksort on the first and the second quarter
> of the data set.
>
> II: ornament
>
>     *
>     |
>     *
>     |     <- n/3 items
>     *
>     |
>     *
>    /|\
>   * * *
>  /  |  \
> *   *   *              <- 3 x n/9 items
>  \  |  /
>   * * *
>    \|/
>     *
>     |
>     *
>     |     <- n/3 items
>     *
>     |
>     *
>
> This poset is obtained by recursing on all intervals containing some
> part of the upper and lower third; the first recursive step where
> these are completely sorted (the depth of the recursion where this
> occurs varies) triggers an additional recursion: it splits the central
> third into thirds and sorts them using traditional quicksort.
>
> This idea could generate a lot of interesting material since all
> connected posets are potential candidates for analysis. Keep in minde
> that we definitely require exact asymptotics.
>
> The algorithm is not very difficult since the internal recursive steps
> of quicksort already use subintervals of the whole interval and this
> is all that is needed for posets.
>
> There is a fine variation on this, namely when you use subintervals
> whose sizes are of different orders. E.g. in the above example all
> subintervals are theta(n), but you could just as well analyse a fork
> whose handle is theta(n) and whose tips are theta(sqrt(n)). Obviously
> the handle contributes the dominant term in this case, but the exact
> asymptotics are not as easy.
>
> There's an additional challenge for deep thinkers here: recall how
> there is a calculus for cover times of graphs. In principle these can
> be computed for any graph by using submatrices of the stochastic
> matrix obtained from the adjacency matrix of the graph. Can you
> provide a calculus for the quicksort asymptotics for any connected
> poset?
>
> I'd be thrilled to get some feedback on this. Have fun!
>
> Best regards,
>
> --
> +------------------------------------------------------------+
> | Marko Riedel, EDV Neue Arbeit gGmbH, mriedel@neuearbeit.de |
> | http://www.geocities.com/markoriedelde/index.html          |
> +------------------------------------------------------------+
>