Algoritimo

Trabalho 1 – ordenação (para 13/9)
O objetivo do trabalho é comparar alguns algoritmos de ordenação.

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.

Compare o desempenho dos algoritmos em sequências de números inteiros gerados 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.

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

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?

Trabalho 2 – grafos (para 23/10) map O grafo ao lado mostra 128 cidades da América do Norte. Ele foi extraído do arquivo miles.dat do livro The Stanford GraphBase. O arquivo map.txt representa esse grafo: os vértices estão numerados de 1 a 128 e cada linha lista uma aresta do grafo e o seu comprimento, isto é, a distância entre as cidades dadas.

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

Para cada um desses subgrafos, calcule o comprimento total.

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