Instituto de Matemática Pura e Aplicada

Geometria Computacional - 2001

1a Lista de Exercícios

Para 05/04/2001

 

1. Implemente os algoritmos mergesort e quicksort contidos no Capítulo 1 do livro. Verifique se eles estão corretos (isto é, se funcionam corretamente para qualquer instância do problema de ordenação; em particular, veja se eles funcionam quando há dados repetidos). Faça as correções que forem necessárias. Compare os dois algoritmos. Veja como eles se comportam para dados aleatórios e para conjuntos já ordenados. Qual dos dois é mais rápido?

 

2. Considere o problema:

Polígono Simples: Dados pontos p1, p2, ..., pn, obter um polígono simples cujos vértices são os pontos dados.

a) Descreva um algoritmo para Polígono Simples. Qual é a complexidade de seu algoritmo?

b) Mostre que Ordenação a Polígono Simples e deduza que Polígono Simples requer W(n log n) passos no pior caso.

 

3. Considere um algoritmo do tipo "Dividir para Conquistar". Mostre que se as etapas de separação e combinação são realizadas em tempo q (n) e existe uma constante a (0<a <1) tal que os tamanhos das instâncias S1 e S2 produzidas pelo processo de separação sejam tais que | S1 | = a n e | S2 | = (1–a )n, então o algoritmo ainda é q (n log n). Porque esse resultado não implica em que o algoritmo quicksort tenha complexidade (de pior caso) q (n log n)?