Construcao e Analise de Algoritmos - Prova 3
--------------------------------------------

1) Considere o algoritmo a seguir:

   Algoritmo X (L: <x1,...,xn> )  {

      1. Se (n = 2)  Retorna ( <min{x1,x2}, max{x1,x2}> );

      2. Dividir entradas em n/2 pares e ordenar cada par
 
           L = < (y1,z1), (y2,z2), ..., (y_n/2,z_n/2) >

        onde yi < zi, para todo i.

      3. (a1, ..., a_n/2) := X (y1, ..., y_n/2)

      4. (b1, ..., b_n/2) := X (z1, ..., z_n/2)

      5. k := n/4

         Enquanto (k >= 1) Faca {
 
            Para i := 1 Ate k Faca {

                Se ( b_{n/4 - k + i} > a_{n/4 + i} )

                   Troca ( b_{n/4 - k + i} > a_{n/4 + i} )
            }
            k := k / 2
         }

      6. Retorna ( <a1, b1, a2, b2, ..., a_n/2, b_n/2 > )
   }


   a) Simule a execucao do algoritmo X sobre uma entrada com 8 ou 16
     elementos.
     Sugestao: 
        < 10, 4, 17, 20, 3, 5, 14, 11, 8, 13, 2, 6, 15, 9, 18, 12 > 

      Nota: Indique o valor de retorno de cada chamada recursiva.

   b) Descreva sucintamente a funcionalidade do algoritmo X.

   c) [Problema Extra (1 ponto): entrega no dia 13/12]
      Prove que o algoritmo X realiza a funcionalidade descrita no item (b) 
     corretamente.

   d) Analise o tempo de execucao do algoritmo X sobre uma lista com 
     n elementos.

      Nota: Assuma que n e' uma potencia de 2.

   e) Descreva um algoritmo para ordenar uma lista com n numeros inteiros
     baseado no algoritmo X (i.e., o seu algoritmo deve usar o algoritmo X 
     como uma sub-rotina).

   f) Analise o tempo de execucao do seu algoritmo de ordenacao.