Carlos E. Ferreira cef@ime.usp.br

MAC 5711 - Análise de Algoritmos

Primeira lista de exercícios - entrega 13 de março de 2003

1. Considere o seguinte algoritmo (chamado de ordenação por seleção) para ordenar um vetor. Ache o menor elemento do vetor e troque com o primeiro. Ache o segundo menor, e troque com o segundo. Repita o processo até o vetor estar totalmente ordenado.

   Escreva o algoritmo descrito acima (em pseudo-código) e faça uma análise de tempo de processamento no melhor e pior caso.

2. Sejam $f,g : {\mbox{{\rm I\kern-0.22emN}}}\longrightarrow \mbox{{\rm I\kern-0.22emR}}_+$. Prove que $\max(f(n),g(n))=\Theta(f(n)+g(n))$.

3. Mostre que para quaisquer $a,b \in \mbox{{\rm I\kern-0.22emR}}$, $b > 0$, $(n+a)^b = \Theta(n^b)$.

4. Mostre que $\log_{k_1}n = \Theta(\log_{k_2}n)$ para quaisquer constantes $k_1, k_2 > 1$.

5. É verdade que $2^{n+1}=O(2^n)$? E $2^{2n}=O(2^n)$?

6. Mostre que $T(n)=n^{O(1)}$ se e somente se existe $k>0$ tal que $T(n)=O(n^k)$.

7. Mostre que $\log(n!)=\Theta(n\log n)$.

8. Mostre que se $f(n)=O(g(n))$ e $g(n)=O(h(n))$, então $f(n)=O(h(n))$.

9. Mostre que $f(n)=O(g(n))$ se e somente se $g(n)=\Omega(f(n))$.

10. Mostre que para $i \ge 2$, o $i$-ésimo elemento da seqüência de Fibonacci ($F_0=F_1=1$, $F_i=F_{i-1}+F_{i-2}$ para $i \ge 2$) satisfaz
    
    $$F_i \ge \phi^{i-2}$$
    
    
    onde, $${\phi = \frac{1 + \sqrt 5}{2}}$$.

11. Escreva o algoritmo Merge do Mergesort e analise sua complexidade computacional. Tente escrever o algoritmo sem utilizar um outro vetor para armazenar os elementos. Seu algoritmo tempo complexidade linear com o tamanho da seqüência a ser ordenada?