Universidade Federal do Paraná
Departamento de Informática
Bacharelado em Ciência da Computação
Prof. Elias P. Duarte Jr.
Lista 2 de Algoritmos II
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
- Considere o seguinte vetor: [25, 57, 48, 37, 12, 92, 86, 33]
Mostre passo a passo como se ordena este vetor com o MergeSort.
- 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.
- 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.
- 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.
- 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.
- De certa forma, o QuickSort adota uma abordagem top-down para ordenar o vetor, enquanto
o MergeSort adota uma abordagem bottom-up. Explique.
- 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.
- 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.
- 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);
}
- 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);
}
- Qual a definição de Tipo Abstrato de Dados?
- 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?
- 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.
- 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?
- 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.
- Mostre como o HeapSort ordena o vetor: [25, 57, 48, 37, 12, 92, 86, 33]
- Explique para que serve a função InicHeap, mostre o código para esta função que você usou
no seu Trabalho Prático.
- Explique como se implementa a função InsereHeap, mostre como inserir um novo elemento em um Heap.
- Explique como se implementa a função RemoveHeap, mostre como remover um elemento de um Heap.
- O que faz a função SacodeHeap? Quais funções do Heap usam a SacodeHeap?
- Explique para que serve a função Heapfy, mostre o código para esta função que você usou
no seu Trabalho Prático.
- Explique para que serve a função ChecaHeap, mostre o código para esta função que você usou
no seu Trabalho Prático.
- Qual o custo de ordenar um vetor de N elementos com o HeapSort? Mostre com clareza como se
chega ao resultado final.
- O que é uma função de complexidade de um algoritmo?
- O que é uma função de custo de um algoritmo em termos de tempo?
- O que é uma função de custo de um algoritmo em termos de espaço?
- Que tal medir o custo de um algoritmo usando um relógio? Por que estas medições são frágeis?
- 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.
- Mostre como o CountingSort ordena o seguinte vetor [2, 1, 4, 5, 5, 1, 3, 2], considere k=1..5
- Descreva as 3 fases do CoutingSort, mostrando com clareza o número de atribuições executadas em cada fase.
- (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?
- 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?
- Na ordenação de cada coluna de caracteres do RadixSort usamos o CountingSort. Justifique esta escolha.
- Ordene com o RadixSort as seguintes placas de automóveis: AWK8080, AWL9081, BAX8268 e BBL8888.
- Qual o custo de ordenar N strings de K caracteres cada com o RadixSort. Explique sua resposta.
- 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.
- Mostre que o problema das N-Rainhas não tem solução nem para N=2 nem para N=3.
- 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)
- Na pergunta anterior, considere agora que cada rainha está em uma linha do tabuleiro direrente das demais. Quantas possibilidades temos agora?
- 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?
- No exercício anterior: nem todas as possiblidades são válidas -- o que falta verificar?
- O algoritmo de backtracking agiliza a busca justamente porque faz backtracking. Explique.
- 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.