Revisão 1 (Exercícios) - Algoritmos e Estruturas de Dados

Prévia do material em texto

Universidade Federal de Pernambuco – UFPE
Centro de Informa´tica
Sistemas de Informac¸a˜o
IF969 – Algoritmos e Estruturas de Dados
Professor: Renato Vimieiro
1a Lista de exerc´ıcios de fixac¸a˜o
1. Seja A um algoritmo com complexidade de tempo a(n) = n2 − n + 549 e B um algoritmo com complexidade
de tempo b(n) = 49n+ 49. Qual algoritmo e´ melhor?
2. Demonstre que n(n+1)2 ∈ O(n3) e n(n+1)2 ∈ O(n2)
3. (Kleinberg e Tardos ex. 2.2) Suponha que voceˆ tenha dispon´ıvel seis algoritmos diferentes para resolver um certo
problema. Suponha tambe´m que o nu´mero de operac¸o˜es executadas por estes algoritmos sejam exatamente
as listadas a seguir. Se o computador dispon´ıvel para resolver o problema executa 25 × 1010 instruc¸o˜es por
segundo e fossemos alocados somente uma hora nessa ma´quina, qual seria o tamanho ma´ximo do conjunto de
dados (n) que poder´ıamos usar com cada algoritmo?
(a) n2
(b) n3
(c) 100n2
(d) n log n
(e) 2n
(f) n!
4. (Adaptado de Livitin ex 2.2.10) Seja S um conjunto com n nu´meros reais. Supondo que este conjunto esteja
armazenado nas estruturas de dados listadas a seguir, descreva um algoritmo para calcular o tamanho do menor
intervalo que contenha os elementos de S. Em seguida, mostre qual o seu tempo de execuc¸a˜o.
(a) vetor na˜o ordenado (b) vetor ordenado (c) a´rvore bina´ria
5. Considere um algoritmo forc¸a bruta para calcular an, onde n ∈ Z. Pergunta-se:
(a) Qual a complexidade desse algoritmo?
(b) Desenhe um algoritmo iterativo que calcule o valor em tempo O(lg n).
6. Mostre a implementac¸a˜o de uma func¸a˜o Lista unirLista(Lista l1, Lista l2) que recebe duas listas ordenadas
como paraˆmetros e retorna uma terceira lista ordenada com os elementos das outras duas. Use pseudoco´digo
ou C++.
7. Implemente um me´todo void Lista::inverteOrdem() que reverta a ordem dos elementos de uma lista simples-
mente encadeada. Para implementar essa func¸a˜o, voceˆ na˜o pode usar estruturas de dados auxiliares ou trocar
os valores dos no´s, isto e´, so´ pode manipular os ponteiros de cada no´.
8. (Ziviani ex. 5.4) A´rvore bina´ria:
(a) Desenhe a a´rvore bina´ria resultante da inserc¸a˜o sucessiva das chaves QUESTAOFACIL com valores repre-
sentando a posic¸a˜o da letra na string.
(b) Desenhe as a´rvores resultantes das remoc¸o˜es de E e depois U da a´rvore obtida no exerc´ıcio anterior.
9. Desenhe a a´rvore rubro-negra resultante da inserc¸a˜o sucessiva das chaves QUESTAOFACIL.
10. (CLRS ex. 11.2-3) O professor Marley apresenta a hipo´tese de que e´ poss´ıvel obter ganhos substanciais de
desempenho se modificarmos o algoritmo de hash com encadeamento para usar listas ordenadas. Como a
modificac¸a˜o do professor afeta o tempo de execuc¸a˜o para pesquisas bem-sucedidas, sem sucesso e inserc¸o˜es?
11. Determine uma func¸a˜o hash usando te´cnica MAD e demonstre a inserc¸a˜o das seguintes chaves 5, 28, 19, 15,
20, 33, 12, 17, 10 numa tabela de tamanho 9 com hash duplo a` sua escolha.
12. Mostre como seria a inserc¸a˜o do valor 10 no heap [15, 13, 9, 5, 12, 8, 7, 4, 0, 6, 2, 1].
13. (Livitin ex. 3.1-12a)
(a) Prove que se o algoritmo da bolha na˜o troca nenhum elemento em uma iterac¸a˜o, enta˜o o vetor esta´
ordenado e o algoritmo pode ser interrompido.
(b) Mostre como seria a implementac¸a˜o dessa versa˜o otimizada do algoritmo da bolha.
(c) A versa˜o otimizada e´ mais eficiente que a versa˜o tradicional no pior caso? E no melhor?
14. Mostre como se daria a ordenac¸a˜o da palavra ALGORITMO usando o me´todo da bolha e de selec¸a˜o.
1
15. (Ziviani ex.4-2) Encontre um vetor exemplo para provar que o algoritmo de selec¸a˜o na˜o e´ esta´vel.
16. (Ziviani ex.4-3) Modifique o me´todo de ordenac¸a˜o por inserc¸a˜o de forma que a busca pela posic¸a˜o de inserc¸a˜o
seja feita usando uma busca bina´ria. Determine a complexidade dessa versa˜o otimizada.
17. (SW ex.2.1.10) Um estudante propoˆs modificar o algoritmo shellsort para usar o me´todo de ordenac¸a˜o por
selec¸a˜o como forma de obter uma sequeˆncia h-ordenada. Essa modificac¸a˜o representaria uma melhoria do
algoritmo original? Explique sua resposta.
18. (SW ex.2.2.8) Um estudante propoˆs uma modificac¸a˜o na versa˜o top-down do mergesort para evitar a intercalac¸a˜o
dos elementos fosse evitada caso os elementos ja´ estivessem ordenados, ou seja v[meio] ¡= v[meio+1]. Ocorre
alguma melhoria no nu´mero de comparac¸o˜es? Justifique.
19. Mostre a implementac¸a˜o da func¸a˜o partic¸a˜o em Python que utiliza um pivoˆ aleato´rio para evitar o pior caso
do quicksort.
20. A func¸a˜o partic¸a˜o troca elementos ainda que eles sejam iguais ao pivoˆ. Por que essa caracter´ıstica e´ bene´fica
ao quicksort?
21. Uma das otimizac¸o˜es propostas para o quicksort consiste em interromper o processo recursivo para vetores de
tamanho menor que M e usar outro algoritmo de ordenac¸a˜o. Qual seria o melhor algoritmo para ser combinado
com o quicksort? Justifique.
22. Mostre a implementac¸a˜o da otimizac¸a˜o proposta no exerc´ıcio anterior.
23. O algoritmo Quickselect baseia-se no Quicksort para encontrar o k-e´simo menor elemento de um vetor. A ideia
e´: se a partic¸a˜o for em k-1, enta˜o retornar o pivoˆ, caso contra´rio buscar na partic¸a˜o a` esquerda ou a` direita
dependendo se p > k− 1 ou p < k− 1. Mostre a implementac¸a˜o do Quickselect sem que a ordem dos elementos
do vetor original seja alterada.
2