IF672 - Algoritmos e Estruturas de Dados
novembro 2002 a março 2003

Lista 3

Essa lista naturalmente NÃO é opcional

Antes de fazer estes exercícios, leia com atenção textos sobre
Hashing, Double Hashing, Função de Hashing

1. Implementar um hashing que mapeia sequências de letras ('a','c','t','g').

2. Implementar rotinas de busca e inserção para uma hashing table com OPEN ADDRESSING, ou seja, cujo conteúdo da tabela são as próprias chaves, como foi discutido em sala. Colisões devem ser resolvidas usando double-hashing. Use a função e os detalhes definidos na página 282 do livro da Sara Baase, implementando a função de double-hashing sugerida no item 8.

3. Implementar rotinas para:

Criação de um heap (Constrói-heap) a partir de um array com n elementos, usando a abordagem bottom-up,
Remoção de um elemento de um heap. A remoção é feita em três etapas:
1. Salvar (para devolver) o conteúdo da raiz (posição 1);
2. Copiar o elemento da última posição do array para a posição 1, diminuindo o valor de n de 1;
3. Executar Heapify (1), ou seja, encontrar o lugar adequado para o elemento que foi colocado artificialmente na raiz da árvore.