paa104_semana_4_adriano_andrade

Programação e Análise de Algoritmos - PAA104

        Divisão e Conquista

Todo o codigo fonte está disponivel no arquivo main.cpp, seguindo a ordem da lista de exercícios.

Cada função está separada por um bloco de comentários.

Para executar cada função, basta descomentar o trecho de codigo correspondente na função int main(int argc, char** argv) e exevutar.

Alguns exerciícios apresentam o teste de desempenho com o matplot

1. Implemente o algoritmo MergeSort

2. Mostre como o MergeSort ordena a lista E, X, A,M, P, L, E em ordem alfabética. ( word)

3. O MergeSort é um algoritmo estável? Explique. ( word)

4. Implemente um algoritmo de divisão e conquista para encontrar a posição do maior elemento de um arranjo de n elementos.
   Responda também: (a) Qual será a saída do método quando se vários elementos do arranjo tiverem o maior valor? (b) Defina e resolva a relação de recorrência para o método proposto. (c) Como este algoritmo se compara com uma solução força bruta? (word)

5. Implemente um algoritmo de divisão e conquista para encontrar a posição do maior e do menor elemento de um arranjo de n elementos. Responda também: (a) Defina e resolva a relação de recorrência para o método proposto. (b) Como este algoritmo se compra com uma solução força bruta? (word)

6. Implemente o algoritmo QuickSort.

7. Mostre como o QuickSort ordena a lista E, X, A,M, P, L, E , em ordem alfabética.
   Desenhe a árvore de chamadas feitas. (word).

8. Dê um exemplo que mostre que o QuickSort não é um algorítmo estável. (word)

9. Implemente a estrutura de dados ́Arvore Binária .

10. Implemente um algoritmo recursivo que encontre o tamanho de uma árvore binária.

11. Mostre o resultado dos caminhamentos preorder,postorder e inorderpara a seguinte
    árvore binária. (word).

12. Implemente os caminhamentos preorder,postorder e inorder para árvores binárias.

13. Implemente o algoritmo de Strassen para multiplicação de matrizes. Como este algoritmo se compara com o algoritmo de força bruta? (word)

14. Implemente o algoritmo QuickHull que usa o paradigma de divisão e conquista para encontrar o ConvexHull de um casca de pontos.
    Como o seu custo se compara com o algoritmo de força bruta?