PUC-Rio
Departamento de Informática
Prof. Marcus Vinicius S. Poggi de Aragão
Período: 2000.2
10 de outubro de 2000

PROJETO E ANÁLISE DE ALGORITMOS (INF 2128)

1o Trabalho de Implementação

Implemente os algoritmos dos itens onde aparece o último dígito do seu número de matrícula (não o DV).

Todos os algoritmos abaixo devem ser testados em um número de instâncias, de tamanhos diferentes, que permita estimar experimentalmente suas respectivas complexidades. Compare estas com a complexidade teórica do algoritmo.

Haverá um pool de instâncias na página: www.inf.puc-rio.br/~poggi

  1. (todos) Implemente o algoritmo de busca "binária" de um elemento em uma matriz ordenada nas linhas e nas colunas.

  2. (0,1,9) Implemente um algoritmo para encontrar um conjunto independente S em um grafo orientado G=(V,E) tal que " v Î V existe um caminho (orientado) de um vértice de S a v de tamanho inferior ou igual a 2 (dois arcos).

  3. (2,3,8) Implemente um algoritmo para encontrar um circuito Hamiltoniano em um grafo denso, i.e. G=(V,E) tal que " v,w Î V, d(v) + d(w) ³ n, onde d(v)= | { u | (u,v) Î E } | (o grau de v) e n=|V|.

  4. (4,5) Implemente um algoritmo para encontrar um ciclo Euleriano em um grafo G=(V,E) onde " v Î V, d(v) = 2.k para algum k.

  5. (6,7) Implemente um algoritmo para encontrar o código de Huffman para um string dado. Implemente também os algoritmos para codificar e decodificar este string.

  6. (todos) Algoritmos para encontrar a árvore geradora mínima (AGM) de um grafo G=(V,E):
    1. Implemente o algoritmo de Round Robin (com lazy leftist heaps, heapify, e Union and Find).
This document was translated from LATEX by HEVEA.