PUC-Rio
Departamento de Informática
Prof. Marcus Vinicius S. Poggi de Aragão
Horário: 2as-feiras e 4as-feiras de 9 às 11 horas - Sala 422L
28 de setembro de 2006
Data da Entrega: 25 de outubro de 2006
Período: 2006.2

ANÁLISE DE ALGORITMOS (INF 1721)

1^o Trabalho de Implementação

Descrição

Este trabalho prático consiste em desenvolver códigos para diferentes algoritmos e estruturas de dados para resolver os problemas descritos abaixo e, principalmente, analisar o desempenho das implementações destes algoritmos com respeito ao tempo de CPU. O desenvolvimento destes códigos e a análise devem seguir os seguintes roteiros:

Descrever os algoritmos informalmente.
Demonstrar o entendimento do algoritmo explicando, em detalhe, o resultado que o algoritmo deve obter e justificá-lo.
Explicar a fundamentação do algoritmo e justificar a sua corretude. Apresentar e explicar a complexidade teórica esperada para cada algoritmo.
Documente o arquivo contendo o código fonte de modo que cada passo do algoritmo esteja devidamente identificado e deixe claro como este passo é executado.

A corretude código será testada sobre os conjuntos de instâncias distribuidos. O trabalho entregue deve conter:

Um documento contendo o roteiro de desenvolvimento dos algoritmos (e dos códigos), os itens pedidos acima, comentários e análises sobre a implementação e os testes realizados (papel). É parte importante do documento uma tabela contendo os tempos de CPU de cada um dos 7 algoritmos pedidos (descritos abaixo) para cada instância dada.
Um e-mail para poggi@inf.puc-rio.br deve ser enviado contendo os códigos fonte, os executáveis correspondentes e o documento final ( é obrigatório o uso do assunto (ou subject) AA062T1). (Lembrem que o gmail não aceita .exe, e portanto vc deve modificar a terminação de .zip para .txt).
O trabalho pode ser feito em grupo de até 3 alunos.

0. Estruturas de Dados

O grupo deve implementar (ou usar códigos prontos) códigos para efetuar as seguintes operações nas estruturas de dados abaixo:

d-Heap
Heap que permita a união de heaps (Leftist Heap do Knuth), com e sem operações preguiçosas (LAZY). (A documentação para isto estará disponível na página no curso).

1. Problema da Árvore Geradora Mínima (veja os links ``Instâncias para AGM'' para grafos de teste)

Implementar o Algoritmo de Kruskal utilizando uma ordenação de complexidade O(n log n) (Merge Sort ou Heap Sort, por exemplo) e com implementações de Union & Find:
1. sem a compactação dos ponteiros.
2. com a compactação dos ponteiros.
Implementar o Algoritmo de Prim utilizando as estruturas de dados, listadas a seguir, para selecionar o vértice mais próximo da árvore corrente. Nestas estruturas, cada vértice tem como valor-chave o peso da menor aresta que o conecta à árvore corrente.

Lista de estruturas de dados a utilizar:
1. d-Heap, para diferentes valores de d.
2. Leftist Heap sem lazy.
3. Leftist Heap com lazy.
Implementar o Algoritmo de Round-Robin (Tarjan) (equivalente ao algoritmo de Solin ou Borüvka) nesse algoritmo inicia-se com uma árvore associada a cada vértice (n árvores) armazenado-se numa min heap as arestas que liga