IF672 -  Algoritmos e Estruturas de Dados
1o. Exercício Escolar

18/junho/2003

1.	Desenhe a seqüência de árvores obtidas pela inserção de cada uma das chaves abaixo nesta ordem numa árvore AVL originalmente vazia.   Caso uma inserção venha a quebrar a propriedade AVL da árvore,  indique claramente qual a rotação apropriada para a situação, e mostre a árvore resultante após a rotação.   CHAVES:   235,  340, 250, 60, 180, 20, 10, 55, 40, 25, 30.   

  
2.	Desenhe a seqüência de configurações das árvores obtidas após cada execução de Heapify, durante a construção  bottom-up de um heap onde o maior elemento está na raiz, a partir de um array original com as chaves na seguinte ordem:       60, 70, 80, 90, 100, 110,  120, 130, 140, 150, 160, 170, 180.  

3.	 a)   Explique de forma clara e sucinta  (6 linhas no máximo cada): 
              	-  O que é uma Tabela Hash,  
-  O que é uma colisão, e 
-  As maneiras de tratar a ocorrência de uma colisão.
  
 b)  Desenhe a seqüência de configurações da tabela Hash obtida numa tabela de tamanho 7, cuja  função hash é dada por H(x) =  x mod 7, e colisões são resolvidas por double hashing,  com a segunda função  D(y) = (y mod 3) + 1,  quando as seguintes chaves são inseridas nesta ordem a partir da tabela vazia:    42,  56,  63, 70.   Mostre a configuração após cada inclusão, indicando claramente onde ocorreu colisão.

4.	Mostre as configurações do array após cada retorno de uma chamada recursiva durante a execução do algoritmo Quicksort  apresentado em sala, com a entrada:    50, 70,  90,  140,  60,  20,  120,  10,  130,  80,  40,  30,  100.

PONTUAÇÃO: 	Problema 1  à   2,0
								Problema 2  à   2,0
								Problema 3  à   3,0
								Problema 4  à   3,0

1o. Exercício Escolar de Algoritmos  (Turma I2)
27/fevereiro/2002

  
1.	Desenhe a  seqüência de árvores AVL  pela inserção das seguintes chaves nesta ordem numa árvore originalmente vazia:  134, 296, 175, 151, 168, 156,  170, 169, 154, 164, 160.

2.	Desenhe a seqüência de configurações do array  obtidas após a execução de HEAPIFY, durante a construção bottom-up de um heap onde o maior elemento está na raiz,  a partir de um array original  com as chaves na seguinte ordem: 120, 180, 40, 150, 22, 90, 64, 295, 450, 329, 250, 360, 350, 410, 550, 490, 533.

3.	 Explique como funciona uma tabela Hash e dê um exemplo desenhando a seqüência de tabelas Hash obtidas numa tabela de tamanho 13, cuja função hash é dada por H(chave) = chave mod 13, e colisões são resolvidas por linear probing crescente, pela inserção das chaves: 52, 78, 48, 61, 81, 120, 79, 121, 92.

4.	a) Explique como implementar  de maneira eficiente  a operação de união de conjuntos distintos

b)  Ilustre a sua explicação com dois exemplos:
               i)         Um que uma dois conjuntos de tamanhos 5 e 9,  e 
ii)	Outro que uma dois conjuntos de tamanhos 14 e 7.  

ALGORITMOS  E ESTRUTURAS  DE  DADOS
Período 2003/2  -   27 / janeiro / 2004

1o. Exercício Escolar

1.	Desenhe a seqüência de árvores obtidas pela inserção de cada uma das chaves abaixo nesta ordem numa árvore AVL originalmente vazia.   Caso uma inserção venha a quebrar a propriedade AVL da árvore, indique claramente qual a rotação apropriada para a situação, e mostre a árvore resultante após a rotação.   CHAVES:   10, 80, 20,  95,  40,  60,  70, 55,  65, 50.  

2.	Desenhe a árvore original e a árvore obtida após cada execução do procedimento Heapify no processo de transformação de um array desordenado contendo originalmente as chaves a seguir (nesta ordem) em um heap onde cada nó contém um valor maior ou igual ao dos descendentes:  170, 289, 110, 553, 328, 140,  403,  580, 764,  625, 800.  

3.	Definição:    Um nó v de uma árvore binária é dito pesoBalanceado (pBal) se a diferença entre o número de descendentes na sua sub-árvore esquerda e o  número de descendentes na sua sub-árvore direita for menor ou igual a 3h,  onde h é altura da árvore com raiz v.  (Altura de uma árvore é o número de arestas no maior caminho da raiz até uma folha qualquer desta árvore.)
 
Escreva em linguagem estruturada um algoritmo recursivo para identificar,  para cada nó v de uma  árvore dada: 
  1. Se este nó é pBal, e 
  2. Quantos nós existem na sub-árvore de raiz v  que são pBal,   incluindo o 
      próprio v,  se for o caso. 

Esta informação deve ser colocada em dois campos chamados:   pBal   (V/F)  e
qtd-desc-pBal  (inteiro),  dentro da estrutura do nó. 

ENTRADA: Apontador para a raiz r de uma árvore binária. 
SAÍDA:  A informação deixada no nós após cada visita.

IMPORTANTE:
Cada aresta só pode ser percorrida de cima para baixo uma única vez.
Note que esta informação usa a altura da árvore, deve fluir no sentido bottom-up.  Cada nó v  no retorno da chamada deve devolver a seu pai duas informações:
       a)  Quantos nós são pBal na árvore de raiz v,   e
       b)  O número de nós (quaisquer) que existem na árvore de raiz v. 

2o. Exercício Escolar de Algoritmos  (Turma I2)
22/abril/2002

  
1.	Desenhe a  seqüência de árvores geradas  na construção da Árvore de Busca-em-Profundidade seguindo o algoritmo apresentado em sala de aula,  quando a entrada é dada pela seguinte lista de incidências, onde cada par representa o outro extremo e o peso da aresta correspondente, nesta ordem:
      1 ® (3,9),  (5,5),  (4,1)
      2 ® (3,2),  (4,2),  (5,2)
      3 ® (1,9),  (2,2),  (5,3)
      4 ® (1,1),  (2,2),  (5,2)
      5 ® (1,5),  (3,3),  (4,2), (2,2)

2.	Dê a seqüência de valores dos dados de controle ao final de cada iteração durante a execução do algoritmo para encontrar a Árvore Geradora de Peso Mínimo, apresentado em sala de aula,  quando a entrada é dada pela mesma lista de incidências acima.

3.	a) Explique de forma concisa e objetiva as três etapas associadas à técnica Dividir-para-conquistar.  (Máximo de três linhas para cada etapa.)
b) Exemplifique cada uma das três etapas, usando os passos dos algoritmos Mergesort e Quicksort.  (Máximo de três linhas para cada etapa.)

4.	a) Explique de forma concisa e objetiva a técnica Programação Dinâmica. (Máximo de três linhas.)
b) Exemplifique o uso da técnica, apresentando uma solução ótima para o problema Distância-deEdição (abbab,  babaa), quando I=2, R=2,  M=4, S=3. 

2o. Exercício Escolar de Algoritmos  (TURMA B)
22/abril/2002

  
1.	Desenhe a  seqüência de árvores geradas  na construção da Árvore de Busca-em-Largura seguindo o algoritmo apresentado em sala de aula,  quando a entrada é dada pela seguinte lista de incidências, onde cada par representa o outro extremo e o peso da aresta correspondente, nesta ordem:
      1 ® (2,8),  (3,5),  (4,3), (5,2)
      2 ® (1,8),  (3,2),  (4,3)
      3 ® (1,5),  (2,2),  (5,2)
      4 ® (1,3),  (2,3),  (5,1)
      5 ® (1,2),  (3,2),  (4,1)

2.	Dê a seqüência de valores dos dados de controle ao final de cada iteração durante a execução do algoritmo para encontrar a Árvore de Distâncias(1), apresentado em sala de aula,  quando a entrada é dada pela mesma lista de incidências acima.

3.	a) Explique de forma concisa e objetiva as três etapas associadas à técnica Dividir-para-conquistar.  (Máximo de três linhas para cada etapa.)
b) Exemplifique cada uma das três etapas, usando os passos dos algoritmos Mergesort e Quicksort.  (Máximo de três linhas para cada etapa.)

4.	a) Explique de forma concisa e objetiva a técnica Programação Dinâmica. (Máximo de três linhas.)
b) Exemplifique o uso da técnica, apresentando uma solução ótima para o problema Distância-deEdição (abbab,  bbbaa), quando I=2, R=2,  M=4, S=3. 

Prova Final de Algoritmos
período 2002 / 2   -  18 / março / 2003

1.	(vale 2,0)   Explique em oito linhas para que serve e como funciona uma tabela Hash.   Desenhe a seqüência de tabelas Hash obtidas num array de tamanho 13, cuja função hash é dada por H(chave) = chave mod 13, e colisões são resolvidas por double hashing, com função  D(x) = x mod 7 + 1.  Mostre a configuração da tabela após a inserção de cada chave da seqüência:  42,  55,  110,  136,  19,  45.    Aponte claramente onde ocorreu colisão, e o que foi feito após isso. 

2.	(vale 2,0)    Definição:    Um nó v  de uma árvore binária é dito estável  se a diferença entre o número de nós com um só filho na sua sub-árvore esquerda e o  número de nós com um só filho na sua sub-árvore direita for menor que dois. 
 
Escreva um algoritmo recursivo para identificar,  para cada nó v de uma  árvore dada:   (1)  Se este nó é estável,  e  (2)  Quantos nós existem na sub-árvore de raiz v  que são estáveis,   incluindo o próprio v, se for o caso. 
Esta informação deve ser colocada em dois campos chamados:  estável (V/F),  e qtd-descend-estáveis, (inteiro) dentro da estrutura do nó. 

ENTRADA: Apontador para a raiz r de uma árvore binária. 
SAÍDA:  A informação deixada no nós após cada visita.

IMPORTANTE:  A informação deve fluir no sentido bottom-up.  Cada nó v  no retorno da chamada deve devolver a seu pai duas informações:
       a)  Quantos nós são estáveis na árvore de raiz v,   e
       b)  O número de nós com um só filho na árvore de raiz v. 

 3. (vale 2,0)  Dê a seqência  de  valores do array Dist a cada iteração do algoritmo apresentado em sala de aula para calcular a  árvore geradora de peso mínimo para o grafo  dado pela seguinte lista de incidências, onde cada par representa o outro extremo e o peso da aresta correspondente, nesta ordem:
      1 ® (2, 14),  (3, 6),  (4, 12),  (5, 15)                 2 ® (1, 14),  (3, 7),  (4,  4),  (5, 1)
      3 ® (1, 6),  (2, 7),  (4, 2)                                   4 ® (1, 12),  (2, 4),   (3, 2),  (5,2)
      5 ® (1, 15),  (2, 1),  (4,2)
 
 4.  (vale 2,0)  Escreva a seqüência de arrays obtida pela execução do Algoritmo Heapsort apresentado em sala de aula quando a entrada contém as seguintes chaves nesta ordem:  45,  28,  50,  90,  60,  14,   49,  33,  80,  07, 70,  23.  

5.  (vale 2,0)  Mostre a(s) tabela(s) de programação dinâmica  para calcular o alinhamento semi-global entre as cadeias  s: CGTAG  e t: GCGATG,  quando os custos das operações  são:  M = 3, S = -1,  I = -4,  R = -4,  e as prioridades  M > S > R > I.   Após todos os cálculos da programação dinâmica,  explique como o melhor alinhamento local  é obtido,  e  apresente este alinhamento.