Construcao e Analise de Algoritmos - Prova 1
--------------------------------------------

1) Considere o algoritmo abaixo que manipula os elementos de um vetor
  arbitrario A[1..n] de numeros inteiros.

  Algoritmo X (i,f) {
  
     Se (f <= i) Retorna;
    
     Se (A[i] > A[f])
        Troca (i,f);

     X (i+1, f-1);

     Se (A[i] > A[i+1])
        Troca (i, i+1);

     X (i+1, f);

  }


a) Simule a execucao do algoritmo no vetor < 17, 5, 29, 3, 14>,
  e indique as trocas de elementos que sao realizadas durante
  a execucao.

b) Descreva sucintamente a funcionalidade do algoritmo X.

c) Prove que o algoritmo X funciona corretamente (Dica: inducao).

d) Determine o numero exato de trocas realizadas pelo algoritmo X
  nos seguintes casos:

    d1) O vetor A esta' organizado em ordem crescente.
    d2) O vetor A esta' organizado em ordem decrescente.
   *d3) A = < n, n-1, n-2, (n/2)+1, 1, 2, 3, ..., (n/2) >

    (Dica para (d3): Obtenha uma equacao de recorrencia para o 
                    numero de trocas Tr(n) realizadas em vetores
                    com este tipo de organizacao.)

e) Apresente uma equacao de recorrencia que descreva o tempo de
  execucao T(n) do algoritmo X.

f) Faca uma estimativa do comportamento assintotico de T(n).
  Ou seja, apresente funcoes f(n) e g(n) tais que

        T(n) = O (f(n))
        T(n) = Omega (g(n)) 



2) A) Considere um vetor nao-ordenado A[1..n] de numeros inteiros.
  
     a1) Faca um algoritmo que execute em tempo O(n) para encontrar
        algum numero x que NAO esteja no vetor A.

     a2) Prove que qualquer algoritmo correto para este problema
        executa em tempo Omega(n).


   B) Suponha que voce possui um procedimento Ax() que ordena k elementos
     de um conjunto X em tempo Tx(k). Suponha tambem que voce possui um 
     procedimento Ay() que ordena k elementos de um conjunto Y em tempo 
     Ty(k).

     b1) Descreva um algoritmo para ordenar n elementos da forma
        (x,y), onde x pertence a X e y pertence a Y, utilizando
        os procedimentos Ax() e Ay().
  
     b2) Determine a complexidade do seu algoritmo em termos de Tx(n) e Ty(n).
 
     Nota: Para o item (b1) voce deve indicar as propriedades que devem
          ser satisfeitas pelos procedimentos Ax() e/ou Ay() para que o
          seu algoritmo funcione corretamente.


   C) Considere um vetor nao-ordenado A[1..n] de numeros inteiros, e um 
     inteiro z. O problema consiste em determinar se existem dois elementos 
     A[i] e A[j] tais que A[i] + A[j] = z. Faca apenas um dos itens a seguir:

     c1) Apresente um algoritmo para este problema que execute em O(n**2).

     c2) Apresente um algoritmo para este problema que execute em O(n logn).

     c3) Apresente um algoritmo para este problema que execute em O(n), 
        supondo que o vetor A se encontra ordenado.



3) Suponha que voce possui um procedimento Terc() que encontra o [n/3]-esimo
  elemento de um vetor A[1..n] (onde [x] denota Teto(x)). Formalmente, o
  procedimento Terc encontra um elemento x de A tal que
   
                      | {i : A[i] < x } | = [n/3]


  a) Descreva um algoritmo que utiliza o procedimento Terc() para encontrar
    a mediana do vetor A[1..n].


  b) Determine a complexidade do seu algoritmo.


  Nota: A mediana do vetor A e' o elemento y de A tal que

                      | {i : A[i] < y } | = [n/2]








4) Considere um vetor A[1..n] de numeros positivos. O problema consiste em 
  encontrar um subconjunto S de elementos de A tal que:

   i) A soma dos elementos em S seja a maior possivel.

  ii) S nao contenha dois elementos consecutivos de A.

  Exemplo: A solucao deste problema para o vetor A = < 12, 15, 10, 4, 9, 11> 
          e' o conjunto S = { 12, 10, 11 }. Note que o maior elemento de A
          nao aparece na solucao.


  a) Apresente um algoritmo de divisao e conquista para este problema.

  b) Descreva o tempo de execucao T(n) do seu algoritmo atraves de uma
    equacao de recorrencia.

  c) Resolva a equacao de recorrencia do item (b) e determine a complexidade
    do seu algoritmo.



5) Considere um vetor nao-ordenado A[1..n] de numeros inteiros distintos, onde
  n e' divisivel por 6. O problema consiste em encontrar um elemento x de A que 
  satisfaca as seguintes condicoes:

   i) x = A[i] para algum  n/6 < i <= 5n/6.

  ii) | {i : A[i] < x } | >= n/6  e  | {i : A[i] > x } | >= n/6.   

     Ou seja, existem pelo menos n/6 elementos em A menores do que x, e 
     pelo menos n/6 elementos em A maiores do que x.


  a) Prove que existe pelo menos um elemento em A que satisfaca (i) e (ii).

  b) Faca um algoritmo para resolver este problema

  c) Considere o seguinte algoritmo para este problema:


     Algoritmo X {

         Repetir {

             i := indice aleatorio entre n/6 (exclusive) e 5n/6 (inclusive);

         } Ate ( A[i] e' solucao );

         Retorna (A[i]);

     }


     c1) Determine o numero minimo de elementos em A que sao solucao para o
        problema, ou seja, satisfazem as condicoes (i) e (ii).
    

        Para os itens (c2) e (c3) assuma que o numero de solucoes do problema
     e' exatamente aquele que voce calculou em (c1).
 
     c2) Calcule a probabilidade de que o algoritmo verifique exatamente k
        elementos para encontrar a solucao. 

        (Dica: Analise separadamente os casos k=1,2,3, e entao obtenha uma
              formula geral.)

     c3) Suponha que a verificacao de que um elemento A[j] e' solucao e' feita
        em tempo O(n). Determine o tempo medio de execucao do algoritmo.

     c4) Qual a complexidade do algoritmo X no pior caso.