• 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.
• Apresentar as tabelas dos tempos de execução obtidos pelos algoritmos sobre as instâncias testadas, comparando sua evolução com a evolução dos tempos seguindo a complexidade teórica correspondente.
• 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.
• Para a medida de tempo de CPU das execuções utilize as funções disponíveis no link correspondente na página do curso, um exemplo de utilização é apresentado. Quando o tempo de CPU for inferior à 5 segundos, faça uma repetição da execução tantas vezes quantas forem necessárias para que o tempo ultrapasse 5 s (faça um while), conte quantas foram as execuções e reporte a média.

• 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).
  
  
• A impressão dos trechos relevantes dos códigos fonte (papel).
  
  
• Um e-mail para poggi@inf.puc-rio.br (é obrigatório o uso do assunto (ou subject) PAA071T1) deve ser enviado contendo os arquivos correspondentes ao trabalho.
  
  
• O trabalho pode ser feito em grupo de até 5 alunos.

1. Árvore Balanceada (Árvore AVL, Árvore Vermelha-Preta, etc.)
2. Heap que permita a união de heaps (Leftist Heap do Knuth), com e sem operações preguiçosas (LAZY).

1. 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. (ver links na página do curso para textos sobre algoritmos para a MST, em especial para o algoritm de Round-Robin, ver também links para instâncias do problema).
   
   Lista de estruturas de dados a utilizar:
   1. Árvore Balanceada de Busca
   2. Heap sem lazy.
   3. Heap com lazy.
   
   A Heap sugerida para ser implementada é a Leftist Heap ver texto no link heap na página do curso.
   
   
2. 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 ligam cada árvore ao restante do grafo. A cada iteração uma árvore é conectada a uma outra e suas min heaps combinadas. A ordem em que as árvore são combinadas segue o critério FIFO onde a ordem inicial é arbitrária (1,2,...,n por exemplo). Utilize as seguintes heaps com operação de união:
   1. Heap sem lazy.
   2. Heap com lazy.

1. Implementar os algoritmos colocam na mochila os itens de maior razão valor/peso com as seguintes complexidades teóricas em função do número n de itens candidatos a serem colocados na mochila:
   1. O(n log n)
   2. O(n)

1. Implementar algoritmos com a seguinte complexidade::
   1. O(n² + nm)
   2. O(|C|.(n + m)) onde C é o conjunto de componentes fortemente conexos.
   3. O(n + m)
2. Utilize esse algoritmo para determinar se uma instância do problema 2-SAT pode ser satisfeita ou não.

This document was translated from L^AT_EX by H^EV^EA.