Fórmulas

• Soma dos N primeiros números naturais: N*(N+1)/2
• Soma dos N primeiros termos de uma P.A.: N*(a1+aN)/2 = N*a1 + N*(N+1)/2 *r
• Limite da soma dos termos de uma P.G. infinita: a1/(1-q)
• Dizemos que g(N) = O(f(N)) se c*f(N) >= g(N), N>=m; c e m são constantes

Questões

1. Considere o seguinte vetor: [25, 57, 48, 37, 12, 92, 86, 33]
   Mostre passo a passo como se ordena este vetor com o MergeSort.

2. Implemente o MergeSort na linguagem C. Faça para o vetor acima uma execução "na mão" do algoritmo para o MergeSort visto em sala de aula.

3. Vimos que o QuickSort, no melhor caso ordena um vetor de N elementos utilizando NlogN comparações. Por outro lado no pior caso o QuickSort é quadrático, o número de comparações é uma função de N^2. (Veja as duas próximas questões). O MergeSort, entretando, utiliza NlogN comparações sempre, em todos os casos. Entretanto, o QuickSort é muito mais usado que o MergeSort. Explique.

4. Qual a relação de recorrência que expressa o número de comparações utilizadas pelo QuickSort no melhor caso? Apresente e resolva a relação de recorrência.

5. Qual a relação de recorrência que expressa o número de comparações utilizadas pelo QuickSort no pior caso? Apresente e resolva a relação de recorrência.

6. De certa forma, o QuickSort adota uma abordagem top-down para ordenar o vetor, enquanto o MergeSort adota uma abordagem bottom-up. Explique.

7. A relação de recorrência que expressa o número de comparações usadas pelo QuickSort no melhor caso é T(N) = N + 2 T(N/2). Resolva esta relação de recorrência.

8. A relação de recorrência que expressa o número de movimentações de discos para resolver o problema das Torres de Hanoi é T(N) = 2 * T(N-1) +1. Resolva esta relação de recorrência.

9. Considere a função recursiva abaixo. Quantas inspeções de elementos são executadas no pior caso por esta função? Mostre claramente como se faz o cálculo.
   FuncRec(N) {
   se N == 1
   então inspecione elemento e termine
   senao inspecione os N elementos da entrada;
   FuncRec(N/7);
   }
   

10. Qual a relação de recorrência correspondente à função recursiva abaixo?
    FuncRec(N) {
    se N== 1
    então triture elemento e termine
    senao triture os N/2 menores elementos da entrada;
    FuncRec(N/2);
    }
    

11. Qual a definição de Tipo Abstrato de Dados?

12. Estudamos um Tipo Abstrato de Dados muito importante, a Fila de Prioridades ou Heap. Responda: qual a definição de Heap? Quais funções foram vistas para o Heap?

13. Proponha mais 5 funções para o Tipo Abstrato de Dados Heap, além daquelas vistas em aula. As funções não podem violar a definição básica de Heap.

14. Apesar de que só trabalhamos com uma implementação do Tipo Abstrato de Dados Heap, usando alocação estática de memória (vetor) discutimos que seria possível implementar o Heap utilizando alocação dinâmica de memória. Responda: qual a principal vantagem da alocação dinâmica de memória sobre a alocação estática de memória?

15. O Vetor [165 102 103 104 105 22 17 4 3] é um Heap? Em caso afirmativo: desenhe o Heap como uma árvore. Em caso negativo, transforme o vetor em Heap e depois desenhe como uma árvore.

16. Mostre como o HeapSort ordena o vetor: [25, 57, 48, 37, 12, 92, 86, 33]

17. Explique para que serve a função InicHeap, mostre o código para esta função que você usou no seu Trabalho Prático.

18. Explique como se implementa a função InsereHeap, mostre como inserir um novo elemento em um Heap.

19. Explique como se implementa a função RemoveHeap, mostre como remover um elemento de um Heap.

20. O que faz a função SacodeHeap? Quais funções do Heap usam a SacodeHeap?

21. Explique para que serve a função Heapfy, mostre o código para esta função que você usou no seu Trabalho Prático.

22. Explique para que serve a função ChecaHeap, mostre o código para esta função que você usou no seu Trabalho Prático.

23. Qual o custo de ordenar um vetor de N elementos com o HeapSort? Mostre com clareza como se chega ao resultado final.

24. O que é uma função de complexidade de um algoritmo?

25. O que é uma função de custo de um algoritmo em termos de tempo?

26. O que é uma função de custo de um algoritmo em termos de espaço?

27. Que tal medir o custo de um algoritmo usando um relógio? Por que estas medições são frágeis?

28. Insitimos muito em sala de aula para o fato do CountingSort ser um algoritmo de ordenação especial, que restringe o tipo de vetor no qual pode ser aplicado. Explique.

29. Mostre como o CountingSort ordena o seguinte vetor [2, 1, 4, 5, 5, 1, 3, 2], considere k=1..5

30. Descreva as 3 fases do CoutingSort, mostrando com clareza o número de atribuições executadas em cada fase.

31. (A) O que é um algoritmo de ordenção estável?i (B) Em que situação exatamente a estabilidade é importante? (C) Vimos 8 algoritmos de ordenação na disciplina: quais são estáveis? Quais não são estáveis?

32. O RadixSort não é um dos algoritmos de ordenação "genéricos", há restrições sobre os dados em que pode ser aplicado. Que restrições são estas?

33. Na ordenação de cada coluna de caracteres do RadixSort usamos o CountingSort. Justifique esta escolha.

34. Ordene com o RadixSort as seguintes placas de automóveis: AWK8080, AWL9081, BAX8268 e BBL8888.

35. Qual o custo de ordenar N strings de K caracteres cada com o RadixSort. Explique sua resposta.

36. Quando estudamos que o limite inferior para ordenar um vetor de N elementos é de NlogN comparações, fizemos uma árvore de decisão para N=3. Desenhe a árvore de decisão para N=4.

37. Mostre que o problema das N-Rainhas não tem solução nem para N=2 nem para N=3.

38. Para N=5 rainhas, qual o número total de possibilidades de colocá-las em um tabuleiro 5x5? (Não há qualquer restrição, são todas as possibilidades)

39. Na pergunta anterior, considere agora que cada rainha está em uma linha do tabuleiro direrente das demais. Quantas possibilidades temos agora?

40. Seguindo ainda as duas perguntas anteriores, considere uma restrição adicional: nenhuma rainha pode ser colocada na mesma coluna de outra rainha. Agora o número de possibilidades reduziu para quanto?

41. No exercício anterior: nem todas as possiblidades são válidas -- o que falta verificar?

42. O algoritmo de backtracking agiliza a busca justamente porque faz backtracking. Explique.

43. Execute o algoritmo de backtracking para encontrar 1 solução válida para o problema das 5-Rainhas. Mostre a execução passo-a-passo.