\documentclass[12pt]{article}
\usepackage[latin1]{inputenc}
\usepackage[brazil]{babel}

\def\R{\mbox{{\rm I\kern-0.22emR}}} % Set of  the  real numbers
\def\N{{\mbox{{\rm I\kern-0.22emN}}}}
\def\Z{{\rm Z}\!\!{\rm Z}}

\begin{document}
\hfill
{\footnotesize Carlos E. Ferreira {\it cef@ime.usp.br}}

\vspace{0.5cm}

\begin{center}
{\large
MAC 5711 -- Análise de Algoritmos
}

\vspace{0.7cm}

Primeira lista de exercícios -- entrega {\bf 13 de março de 2003}
\end{center}

\begin{enumerate}
\item 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. 

\item Sejam $f,g : \N \longrightarrow \R_+$. Prove que
$\max(f(n),g(n))=\Theta(f(n)+g(n))$. 

\item Mostre que para quaisquer $a,b \in \R$, $b > 0$, $(n+a)^b =
\Theta(n^b)$.

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

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

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

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

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

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

\item 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, $\displaystyle{\phi = \frac{1 + \sqrt 5}{2}}$. 

\item Escreva o algoritmo {\tt Merge} do {\tt 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? 
\end{enumerate}
\end{document}