Algoritmos
 2014 - trabalhos

Trabalho 1 – ordenação (para 25/9)

1. Implemente os algoritmos estudados em aula (seleção, inserção, mergesort, quicksort, heapsort). Escreva o programa mais simples possível para testar cada algoritmo. Compare o esforço necessário para a implementação correta de cada algortimo.

2. Compare o desempenho dos algoritmos em sequências de números inteiros geradas aleatoriamente. Use sequências de 100 até 100000 números. (E mais se for possível.) Meça e compare os tempos de cada algoritmo.

3. Repita os testes com sequências especiais: ordenadas em ordem crescente, ordenadas em ordem descrescente, com muitas repetições, com poucas repetições.

4. No caso de mergesort e quicksort, interrompa a recursão quando o subproblema for pequeno e execute ordenação por inserção em cada subproblema. No caso de quicksort, faça o mesmo executando ordenação por inserção uma única vez, ao final do processo. Vale a pena fazer essas modificações? A partir de quando? Para qual definição de pequeno?
5. Adapte os seus programas para ordenar palavras. Teste o desempenho de cada algoritmo no arquivo BR4.txt contendo 10000 palavras e no arquivo BR5.txt contendo 100000 palavras. Houve mudança do desempenho relativo dos algoritmos agora que comparar valores é mais complicado?

Trabalho 2 – grafos (para 23/10)

1. Encontre uma árvore geradora mínima para esse grafo.
2. Encontre o menor caminho entre a cidade 93 e a cidade 112.
3. Encontre a árvore de menores caminhos a partir da cidade 104.

Se quiser gerar uma figura, edite o arquivo map.eps para incluir o subgrafo após a linha marcada subgraph no formato indicado.

Faça o mesmo para o grafo das 5565 sedes dos municípios do Brasil, encontrando o menor caminho entre a cidade 1 e cidade 2646, e a árvore de menores caminhos a partir da cidade 2646. Veja uma imagem do grafo e o programa ps.

Trabalho 3 – fecho convexo (para 13/11)

1. Implemente o algoritmo de Jarvis e o algoritmo de Graham, nas suas duas variantes. (Implemente também outros algoritmos se quiser.) Escreva o programa mais simples possível para cada algoritmo. Não se preocupe com interfaces gráficas.

2. Teste os seus programas no seguinte conjunto de pontos:

      A   B   C   D   E   F   G   H   I   J   K   L   M   N   O   P   Q
   x  3  11   6   4   5   8   1   7   9  14  10  17  15  13   3  12  16
   y  9   1   8   3  15  11   6   4   7   5  13  14   2  16  12  10   8
   

   A solução é B M L N E O G D. Note que Q não faz parte da solução. A figura ao lado mostra a solução e foi gerada por um programa em PostScript.

   Teste também para as 128 cidades da América do Norte e para as 5565 sedes dos municípios do Brasil, e compare a sua solução com as figuras acima. Quantos vértices tem o fecho convexo em cada caso?

3. Compare o desempenho dos algoritmos implementados em conjuntos de pontos gerados aleatoriamente dentro de um retângulo, dentro de um triângulo, dentro de um círculo, e sobre o círculo. Use conjuntos de 100 até 100000 pontos. (E mais se for possível.) Compare os tempos de cada algoritmo e também o esforço necessário para sua implementação.

4. Refaça os testes do item anterior incorporando eliminação de pontos interiores. Vale a pena eliminar pontos interiores? Qual as frações do tempo total que levam a eliminação de pontos interiores e o cálculo do fecho convexo após essa eliminação?

5. Avalie o papel do passo de ordenação no desempenho global dos seus programas. Qual a diferença entre usar um algoritmo quadrático ou um algoritmo O(n log n)?

Trabalho 4 – triangulação (para 27/11)

1. Calcule o o fecho convexo das 128 cidades da América do Norte.
2. Triangule esse polígono convexo a partir da cidade 7.
3. Adicione as cidades restantes, uma de cada vez, na ordem dada, atualizando a triangulação a cada passo.
4. Na triangulação final, qual são as três cidades que aparecem em mais triângulos?