Lista1_AnaliseAlgoritmos

Prévia do material em texto

Universidade Federal de Campina Grande 
Centro de Engenharia Eletrica e Informática 
Departamento de Sistemas e Computação 
Graduação em Ciência da Computação 
Lista de Exercícios sobre Análise de Algoritmos 
(Consulte a monitoria para saber das respostas e tirar suas dúvidas) 
 
1. Resolva as seguintes relações de recorrência: 
 
���� = 7��� 7� 	 + � 
���� = 9��� 3� 	 + �
 
���� = 8��� 2� 	 + �� 
���� = 49��� 25� � + �
�
� 	 log � 
���� = ��� − 1� + 	2 
���� = ��� − 1� + ��, onde c ≥ 1 é uma constante 
���� = ��� − 1� + ��, where c > 1 é uma constante 
���� = 2��� − 1� + 1 
���� = ��√�	 + 1 
 
2. Faça um algoritmo iterativo e outro resursivo para calcular o fatorial de um número dado. Em 
seguinda encontre o tempo de execução desses algoritmos. 
 
3. Faça um algoritmo iterativo que diz se um numero está ou nao num vetor de dados V e depois 
encontre sua expressão do tempo de execução. 
 
4. Sejam !��� e "��� funções de inteiros nos inteiros positivos. O que significa dizer que !��� =
#�"����? 
 
5. Considere as funções !��� = 3�
 − � + 4 e "��� = �$%"	� + 5. Usando a definicao de O, mostre 
que !��� + "��� = #��
�. 
 
6. Usando a definição da notação assintótica, determine se os seguintes itens sao verdadeiros ou 
falsos. 
a. 2�&' = #�2�� 
 
b. 2
� = #�2�� 
 
7. Mostre que ∑ )
�*+' = Θ����. Caso ache necessário, use a fórmula do somatório dada abaixo. 
 
 
8. Seja T a funcao definida pela seguinte recorrência: ��1� = 1 e ���� = ��√�	 + 2. Mostre que a 
complexidade dessa função é Θ�log log ��. Dica: escreva a raiz quadrada como potencia de 
expoente fracionario no método iterativo. Voce vai precisar de regras de manipulação de 
logaritmos para simplificar termos.(Consulte a monitoria para saber da resposta). 
 
∑
=
++
=+++=
n
i
nnn
ni
1
2222
6
)12)(1(21 L
9. Suponha que, para entradas de tamanho n, voce tenha de escolher um entre dois algoritmos. 
a) O algoritmo A resolve problemas dividindo-os em dois subproblemas de tamanho n-1, 
recursivamente resolve cada subproblema e então combina as soluções em tempo O(1). 
b) Algoritmo B resolve problemas dividindo-os em nove subproblemas de tamanho n/3, 
recursivamente resolve cada subproblema e então combina as soluções em tempo O(n
2
). 
Qual o consumo de tempo desses algoritmos? Qual algoritmo é assintoticamente mais eficiente? 
(Consulte a monitoria para saber da resposta). 
 
10. Dada uma função "��� com determinada complexidade. Seja !��� = "��� + 1. Mostre que 
! = #�"����.(Use a definição mostrada nso slides). 
 
11. Suponha que um certo problema X depende de um parametro inteiro positivo �. Meu algoritmo 
para o problema consome tempo %��
�. Meu amigo diz ter um algoritmo melhor, que consome 
tempo -���. Devo ficar impressionado?