Algoritmos
2015 – trabalhos

Trabalho 0 – aquecimento (para 13/8)

O objetivo do trabalho é fazer uma análise experimental do desempenho do algoritmo de Euclides para encontrar o máximo divisor comum de dois números naturais.

Pesquise sobre o algoritmo de Euclides.
Implemente o algoritmo de Euclides.
Meça o número de passos feitos pelo algoritmo de Euclides para calcular o o máximo divisor comum de dois números naturais a e b, para 1 ≤ a,b ≤ N. Como o número máximo varia em função de N? Como o número médio varia em função de N?
Pesquise sobre o desempenho do algoritmo de Euclides.
Compare as previsões teóricas com os seus resultados experimentais.

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

O objetivo do trabalho é fazer uma análise experimental para 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 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.
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?
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 15/10)

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 é, duas cidades e a distância entre elas.

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 seu 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 uma imagem do grafo e o programa ps.

Trabalho 3 – fecho convexo (para 3/11)

O objetivo do trabalho é comparar algoritmos que calculam o fecho convexo de um conjunto de pontos no plano.

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.
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?
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.
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?
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 – interseção de segmentos de retas (para 8/12)

Neste trabalho estudaremos o problema de detectar se em uma coleção de segmentos no plano, algum par se intersecta. Para isso utilizaremos o algoritmo de "varredura por retas verticais". Esse algoritmo faz uso de uma estrutura de dados X, capaz de implementar as operações de: Inserção, Remoção, Sucessor/Antecessor. Nos itens que seguem, o aluno deve escolher apenas um item especial (marcado com *) para implementar.

Implemente o algoritmo de varredura (utilizando uma estrutura X arbitrária) para detectar:
1. Se dois segmentos de uma coleção se intersectam.
2. *Se uma sequência de segmentos constitui um polígono.
Implemente as estruturas:
1. lista duplamente encadeada
2. árvore binária de busca
3. * red-black trees

Compare o desempenho do algoritmo (utilizando todas as estruturas implementadas no item anterior) para detectar interseções dos segmentos gerados pelos seguintes códigos python (para N = 10, 100, 1000... até onde der):

import random
N = 10
print "x1    y1    x2    y2"
for i in range(N/2):
    x = random.random()*N
    y = random.random()*N
    print x, y, x + 1.2, y - .2
    print x, y + .5, x + .5, y + 2.5

import random
N = 10
print "x1    y1    x2    y2"
for i in range(N):
    a = random.random() * N
    print i, a, i + N, a

N = 10
print "x1    y1    x2    y2"
for i in range(N):
    print i, i, i + N, i

Caso tenha implementado o item 1b, rode também o algoritmo em um polígono regular com N lados.
Avalie o desempenho de cada uma das estruturas de dados implementadas.