Lista de Exercícios 1 FPAA

Prévia do material em texto

Pontifícia Universidade Católica de Minas Gerais 
Projeto e Análise de Algoritmos 
Prof. Walisson Ferreira de Carvalho 
 
Lista de Exercícios #1 
1) Qual a notação sigma equivalente à seguinte progressão? 
5 + (−5) + (−15) +⋯ .+(−745) + (−755) 
 
2) Avalie o somatório ∑ 1𝑖𝑛𝑖=1 
3) Resolva a seguinte equação de recorrência 
T(n) = T(n - 1) + 2; n > 0 
T(0) = 1 
4) São dados 2n números distintos distribuídos em dois arranjos com n elementos A e B 
ordenados de maneira tal que: 
 
A[1] > A[2] > A[3] > · · · > A[n] e B[1] > B[2] > B[3] > · · · > B[n]. 
 
O problema é achar o n-ésimo maior número dentre estes 2n elementos. Escreva um 
algoritmo para resolver esse problema e faça a análise do algoritmo apresentado. 
 
5) Indique se as afirmativas a seguir são verdadeiras ou falsas e justifique a sua resposta: 
a. 2𝑛+1 = 𝑂(2𝑛) 
b. 22𝑛 = 𝑂(2𝑛) 
 
6) Prove que 2n² − 20n − 50 = Ω(2n). 
 
7) Sobre recursividade responda: 
a. Quando se deve e quando não se deve usar recursividade? 
b. Explique os tipos de recursão. 
8) Faça a análise do seguinte algoritmo 
 
9) Resolva as recorrências a seguir aplicando o Teorema Mestre: 
a. T(n)=9T(n/3)+n 
b. T(n) = 4T(n/2) + n^3;