Universidade Federal de Minas Gerais
Departamento de Ciência da Computação

CURSO DE PÓS-GRADUAÇÃO EM CIÊNCIA DA COMPUTAÇÃO
PROJETO E ANÁLISE DE ALGORITMOS

Última alteração: Junho 13, 2002

Horario : Terça: 14:55 - 16:35, Quinta: 14:55 - 16:35, Sala: 2029
Professor: Nivio Ziviani
Monitora: Claudine Santos Badue
1$^{\underline{o}}$ Trabalho Prático - 06/06/02 - 10 pontos
Data de Entrega: 28/06/02
Penalização por Atrazo: 1 ponto até 02/06/02 mais 1 ponto por dia a seguir

1.

Avaliar as somas (0,5 + 0,5 + 0,5 + 0,5 pontos):

(a)

(b)

(c)

(d)

2.

Apresente a complexidade de tempo para os procedimentos abaixo: 0.5 + 0.5 + 0.5 + 0.5 pontos)

(a)

      PROCEDURE FazAlgo ( n : integer);
      VAR i, j, k, x : integer;
      BEGIN
        x := 0;
        FOR i := 1 TO n - 1 DO
          FOR j := i + 1 TO n DO
            FOR k := 1 TO j DO x := x + 1;
      END;

(b)

      PROCEDURE Pesquisa ( n : integer);
      BEGIN
        IF n > 1
        THEN BEGIN
             Inspecione n*n*n elementos;
             Pesquisa (n/3);
             END;
      END;

(c)

      PROCEDURE Sort ( VAR A: ARRAY[1..n] OF integer;
                       i, j: integer );
      { n uma potencia de 2 }
      BEGIN
        IF i < j
        THEN BEGIN
             m := (i + j - 1)/2;
             Sort(A,i,m);
             Sort(A,m+1,j);
             Merge(A,i,m,j);
             { Merge intercala A[i..m] e A[m+1..j] em A[i..j] }
             END;
      END;

(d)

      PROCEDURE Proc( n : integer );
      BEGIN
        IF n = 0 THEN RETURN 1
                 ELSE RETURN Proc(n-1) + Proc(n-1)
      ENDE;

3.

Limite inferior: 1,5 + 1,5 pontos)

São dados 2n números distintos distribuídos em dois arranjos A e B, cada um com n elementos ordenados, tal que: $A[1] \gt A[2] \gt \ldots \gt A[n]$ e $B[1] \gt B[2] \gt \ldots \gt B[n]$.O problema é achar o n-ésimo maior número dentre estes 2n elementos.

(a)

Apresente um algoritmo ótimo para resolver esse problema. Implemente o seu algoritmo. A listagem da implementação deve ser entregue e o programa submetido (veja aqui maiores detalhes sobre instruções para a entrega de trabalhos praticos).

(b)

Prove que o seu algoritmo é ótimo, isto é, obtenha um limite inferior para o número de comparações para resolver esta classe de problemas.

4.

Árvore Binária de Pesquisa Sem Balanceamento 1 + 0,5 + 0,5 + 1 pontos)

Considere o algoritmo para pesquisar e inserir registros em uma árvore binária de pesquisa sem balanceamento. Devido à sua simplicidade e eficiência a árvore binária de pesquisa é considerada uma estrutura de dados muito útil. Considerando-se que a altura da árvore corresponde ao tamanho da pilha necessária para pesquisar na árvore é importante conhecer o seu valor. Assim sendo,

(a)

determine empiricamente a altura esperada da árvore;

(b)

mostre analiticamente o melhor caso e o pior caso para a altura da árvore;

(c)

compare os resultados obtidos no item (a) com resultados analíticos publicados na literatura.

(d)

Mostre analiticamente o número esperado de comparações para encontrar um registro existente na árvore (busca com sucesso).

Utilize o procedimento Permut abaixo para obter uma permutacao randômica das chaves.

#include <stdio.h>
#include <stdlib.h>
#include <sys/types.h>
#include <sys/timeb.h>

void IniciaRand() { /* Substituir por uma funcao que tome tempo em ms */
  time_t ltime;
  time(&ltime);
  ltime%=10000;
  srand(ltime);
}

double rand0a1() {
  double resultado=  (double) rand()/ 0x7FFF; /* Dividir pelo maior inteiro */
  if(resultado>1.0) resultado= 1.0;
  return resultado;
}

void Permut( int A[], int n) {
 int i,j,b;

 IniciaRand(); /* Funcao que Inicia a geracao de numeros randomicos */
 for(i = n-1; i>0; i --) {
   j = (i * rand0a1()) +1 ;
   b = A[i];
   A[i] = A[j];
   A[j] = b;
 }
}

int main() {
  unsigned int x;
  int v[20];

  for(x=0;x<20;x++)    v[x]=x;
  Permut(v,20);
  for(x=0;x<20;x++)  printf("%d ",v[x]);
  printf("\n");
  return 0; 
}