Universidade Federal do Paraná
Departamento de Informática
Disciplina CI056 - Algoritmos e Estruturas de Dados II
2o Período do BCC, IBM, MI
Prof. Elias P. Duarte Jr.

Trabalho Prático 2 (2015/2, Turma A): A Mega Quadra

Data de Entrega: 13 de dezembro de 2014, domingo -> são 18 dias de prazo, organize-se!

Os alunos devem informar por e-mail a URL do trabalho, usando o subject "TP2 ALGORITMOS II 2015-2" -- máximo cuidado para enviar exatamente este subject, OK?

OBS.: O trabalho deve ser feito em dupla; os dois membros da equipe devem se reunir para fazer todo o código!

Participe do sorteio da Mega Quadra! Ganha o jogo quem acerta se 4 números estão em um vetor de números aleatórios. Se não acertar 4, quem sabe 3? Ou 2? Ou 1? Se não acertar nenhum, jogue de novo!

O programa da Mega Quadra deve inicialmente receber como parâmetro de entrada o tamanho de um vetor de inteiros, que deve ser preenchido com números aleatórios de 1 até um valor máximo também fornecido como parâmetro. ATENÇÃO: deve ser possível imprimir na tela este vetor, de forma limpa e compacta.

Em seguida este programa permite que o usuário entre com quatro números inteiros (na faixa permitida -- faça a consistência dos dados!). Informe ao usuário se ganhou o jogo, ou seja os 4 dos números fornecidos estão no vetor; informe também se 3, 2, 1 ou nenhum número está no vetor. Permita ao jogador jogar quantas vezes quiser. Se preferir faça a interface simples, na própria linha de comando.

Para cada número informado pelo jogador, utilize tanto a Pesquisa Sequencial como a Pesquisa Binária. Você deve salvar o vetor não ordenado e ordená-lo usando um de 4 algoritmos diferentes: SelectSort, BubbleSort, QuickSort recursivo e QuickSort iterativo. Para o QuickSort utilize como pivô o elemento que corresponde à mediana do primeiro, meio e último elementos do vetor.

Uma opção do programa deve permitir contar o tempo de execução de 10.000 (dez mil) ordenações do vetor para cada algoritmo. Assim, para cada um dos quatro algoritmos de ordenação gere 10.000 vetores de números aleatórios e faça a ordenação dez mil vezes. Portanto serão gerados e ordenados 40.000 vetores nesta opção. Meça e mostre o tempo de máquina necessário para cada algoritmo ordenar seus dez mil vetores.

Deve ser construída uma página Web, que contém em documentos HTML, os seguintes itens:

  • Relatório de como foi feito o trabalho e quais foram os resultados obtidos. Use desenhos, diagramas, figuras, todos os recursos que permitam ao professor compreender como a dupla estruturou o trabalho e quais resultados obteve.
  • Listagem do programa em C;
  • Log dos testes executados: mostre explicitamente diversos casos testados, lembre-se à a partir desta listagem de testes que o professor vai medir até que ponto o trabalho está funcionando.

    Observações:

  • Não serão aceitos trabalhos impressos, nem em meio ótico/magnético.
  • Todos os trabalhos serão defendidos no laboratório, portanto certifique-se que seu trabalho funciona aqui!

    Importante: capriche na legibilidade e organização.

    Prof. Elias P. Duarte Jr.     Departamento de Informática     UFPR