Trabalho Final

Pesquisa e Ordena¸c˜ao
Professor: Ricardo Moura Sekeff Budaruiche
Trabalho final de disciplina
Entrega 15 de junho de 2015
Descri¸
c˜ ao: Este trabalho ir´ a consistir na composi¸c˜ao da 3a nota da disciplina de Pesquisa e Ordena¸c˜ao (2a parte) e dever´ a ser desenvolvido em duplas a fim de otimizar o aprendizado e proporcionar o desenvolvimento de solu¸c˜ oes ´ otimas para problemas computacionais. Todos os problemas que envolvem desenvolvimento de c´ odigo dever˜ ao possuir os c´odigos-fonte e o execut´avel funcionando. Se um programa n˜ao funcionar corretamente no dia da apresenta¸c˜ao, ent˜ao a pontua¸c˜ao dessa quest˜ ao n˜ ao ser´a levada em conta para o somat´ orio final dos pontos. Cada equipe, no dia da entrega, dever´ a entregar um arquivo com os c´ odigos-fonte, os execut´ aveis e um arquivo em pdf contendo as discuss˜ oes geradas pela equipe em cada uma das quest˜oes. N˜ao ser˜ao aceitos trabalhos copiados da internet nem de outros colegas, configurando para isso fraude acadˆ emica. Os trabalhos enquadrados como fraude acadˆ emica ter˜ ao notas 0 (zero) atribu´ıdas aos seus trabalhos.
Quest˜
ao 1 Gere aleatoriamente arranjos de 1.000, 10.000, 100.000, 1.000.000 e 1.000.000.000 de inteiros. Implemente 4 algoritmos de busca:
1. Busca bin´ aria 2. Busca usando ´ arvores B
3. Busca usando ´ arvores B+
4. Busca usando ´ arvores AVL
Utilize os vetores que criou aleatoriamente como entrada para cada um dos algoritmos e contabilize o tempo para encontrar um elemento qualquer (inclusive algum que n˜ ao exista nos vetores) nesse vetor.
Tabule os resultados e plote gr´ aficos para essa execu¸c˜ ao. Comente sobre os resultados finais. Contabilize n´ umero de chamadas recursivas, tempo em milissegundos, tamanho do arranjo testado e quantidade de mem´ oria consumida. Escreva um relat´ orio explicando seus experimentos, as instˆ ancias utilizadas, as dificuldades encontradas e os resultados alcan¸cados. Fundamente seu relat´ orio com o referencial te´ orico do