PUC-Rio
Departamento de Informática
Prof. Marcus Vinicius S. Poggi de Aragão
Período: 2003.1
Horário: 2as-feiras e 4as-feiras de 17 às 19 horas
Local: 134L
14 de maio de 2003
ANÁLISE DE ALGORITMOS (INF 1721)

1o Trabalho de Implementação

Implemente os algoritmos listados a seguir. Todos os algoritmos devem ser testados em vários grupos de instâncias de tamanhos diferentes, de modo a permitir estimar experimentalmente suas respectivas complexidades (para cada problema esta disponível uma massa de dados na página). Compare estas com a complexidade teórica do algoritmo. Isto é prepare tabelas contendo os tempos de CPU de cada execução, as funções candidatas para ser a complexidade teórica do algoritmo, e a razão entre estes valores (utilize pelo menos duas funções). Recomendação: para os casos onde o tempo de cpu é muito pequeno, execute um certo número de vezes (100 ou 1000 por exemplo) e utilize a média como tempo de CPU.

  1. Algoritmo Shell Sort para o problema de ordenação de uma seqüência de itens. Devem ser implementadas duas versões deste algoritmo. Uma que utilize potência de dois para o cálculo dos intervalos e uma segunda versão que use alguma outra sequência (por exemplo, os números da sequência de Fibonacci (1, 2, 3, 5, 8, 13, ...)). Obtenha as suas respectivas comlexidades experimentais. Veja o capítulo 8 do livro Algorithms, R. Sedgewick, 1992.

    Dados em http://www.inf.puc-rio.br/ poggi//aalg031.html no link SORTdata.

  2. Algoritmo de Kruskal para o problema da árvore geradora de peso mínimo mínimo. A sua implementação deve utilizar uma estrutura de dados com Union and Find. Essa estrutura, usada no armazenamento dos componentes das florestas geradoras intermediárias, deve permitir uma resposta eficiente à principal questão presente neste algoritmo: Ao se adicionar uma aresta à arvore em construção é criado um ciclo?. Utilize o código do Union and Find apresentado em aula.

    Dados em http://www.inf.puc-rio.br/ poggi//aalg031.html no link AVGdata.

  3. Implemente o algoritmo para multiplicar duas matrizes apresentado em TWO NEW ALGORITHMS FOR MATRIX MULTIPLICATION AND VECTOR CONVOLUTION. Obtenha a sua complexidade experimental.

    Dados em http://www.inf.puc-rio.br/ poggi//aalg031.html no link MATRIXdata.

  4. Implemente o algoritmo de Edmonds e Karp para obter o Fluxo Máximo de uma rede. Determine a sua complexidade experimental.

    Dados em http://www.inf.puc-rio.br/ poggi//aalg031.html no link MAXFLOWdata.