1. Sejam S₁ e S₂ conjuntos cujos elementos são números inteiros e onde |S₁|+|S₂|=n. Dado um inteiro x, propor um algoritmo para determinar se existem e₁ Î S₁ e e₂ Î S₂ tais que e₁ + e₂ = x.
   1. Proponha e implemente um algoritmo de complexidade Q (n²) e apresente a análise que permite concluir esta complexidade.
   2. Proponha e implemente um algoritmo de complexidade O(n log n) e apresente a análise que permite concluir esta complexidade.
   3. Suponha agora que S₁ e S₂ estejam ordenados. Proponha e implemente um algoritmo de complexidade O(n) e apresente a análise que permite concluir esta complexidade.
      
      
   4. Execute os algoritmos implementados sobre conjuntos S₁ e S₂ de tamanho total 1000, 2000, 5000, 10000, 20000, 50000 e 10000. Apresente os tempos de CPU para cada execução de cada algoritmo, organize numa tabela.
      
      
   5. Analise os resultados experimentais obtidos e compare com as complexidades teóricas.
   
   
2. Sejam S₁ e S₂ conjuntos cujos elementos são números inteiros e onde |S₁|=|S₂|=n.
   1. Apresente e implemente um algoritmo de complexidade Q (n²) para determinar a união de S₁ e S₂. Nenhum elemento deve aparecer mais de uma vez.
      
      
   2. Apresente e implemente um algoritmo que execute em O(n log n).
      
      
   3. Execute os algoritmos implementados sobre conjuntos S₁ e S₂ de tamanho 1000, 2000, 5000, 10000, 20000, 50000 e 10000. Apresente os tempos de CPU para cada execução.
      
      
   4. Analise os resultados experimentais obtidos e compare com as complexidades teóricas.
   
   
3. Busca em Vetores Ordenados
   
   
   1. Escreva um algoritmo de "busca ternária" que primeiro testa se o elemento da posição n/3 é igual ao elemento procurado x e então, se necessário, testa o elemento da posição 2n/3 para verificar a igualdade com o elemento x e, possivelmente, reduzir o tamanho do conjunto para um terço do original.
      
      
   2. Implemente um algoritmo de Busca Binária.
      
      
   3. Execute os algoritmos implementados sobre vetores de tamanho 1000, 2000, 5000, 10000, 20000, 50000 e 10000. Apresente os tempos de CPU para cada execução. Apresente também o número de comparações e recursões realizadas em cada execução.
   4. Analise os resultados experimentais obtidos e compare com as complexidades teóricas.
   
   

• 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 gráficos com os tempos de CPU para a execução de cada um dos casos teste (observe que tempos de CPU inferiores à 5s não são confiáveis, nesse caso repita a execução do teste até que o tempo ultrapasse 5s, divida então o tempo de CPU obtido pelo número de execuções que foram necessárias);
• 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.

• 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 códigos fonte (papel).
• Um e-mail contendo os códigos fonte, os executáveis e o documento em versão eletrônica, correspondentes (o e-mail deve ser enviado para marcus.poggi@gmail.com e é obrigatório o uso do assunto (ou subject) AA061T1).
• O trabalho pode ser feito em grupos de até 2 alunos.

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