• 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) AA092T1 deve ser enviado contendo os arquivos correspondentes ao trabalho. O NÃO ENVIO DESTE E-MAIL IMPLICA QUE O TRABALHO NÃO SERÁ CONSIDERADO.
  
  
• O trabalho pode ser feito em grupo de até 3 alunos.

1. Implemente o algoritmo da mediana da medianas;
2. Argumente que sua complexidade é linear, i.e. O(n);
3. Verifique sua complexidade experimentalmente nas instâncias disponibilizadas.
4. Analise cuidadosamente, seguindo os passos descritos no início do trabalho, os resultados obtidos.

1. Implemente o algoritmo da QuickSort com as seguintes escolhas de pivot:
   1. Um elemento aleatório do conjunto considerado na iteração;
   2. A média do elementos no conjunto considerado na iteração;
   3. A mediana do conjunto considerado na iteração;
2. Implemente o algoritmo Shell Sort. 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.
3. Verifique as complexidades experimentais destes 5 algoritmos nas instâncias disponibilizadas.
4. Analise cuidadosamente, seguindo os passos descritos no início do trabalho, os resultados obtidos.

1. Implementar algoritmos para o problema da mochila fracionária 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)
   3. Considere que o seu algoritmo do item (b) utiliza particionamentos em sequencia com pivot calculado apropriadamente para garantir a complexidade O(n). Utilize agora como pivot o valor calculado pela expressão:

      pivot =

      1 |K|

      å j Î K

      vj wj

      onde K é o conjunto de itens considerados.
      1. Prove que a complexidade (pior caso) do algoritmo resultante é O(n²).
      2. Estime sua complexidade sobre as intâncias testadas.
      3. Assim como para os itens (a) e (b) apresente experiências computacionais comparativas.
      4. Analise cuidadosamente, seguindo os passos descritos no início do trabalho, os resultados obtidos.

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