\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}
\noindent
{\footnotesize {\sc MAC--IME--USP}}  \hfill {\footnotesize {\sc Carlos Eduardo Ferreira}}

\vspace{-1mm}
\hfill {\footnotesize {\sc Sala 297A Tel.: 3091 6140}}

\vspace{-1mm}
\hfill {\footnotesize {\sc e-mail} cef@ime.usp.br}

\vspace{0.5cm}

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

\vspace{0.7cm}

Segunda lista de exercícios -- entrega {\bf 8 de abril de 2003}
\end{center}


\begin{enumerate}

\item Mostre que para todo $a,b > 0$ vale que \[ (\log n)^a=O(n^b). \]

\item Onde pode estar o menor elemento de um vetor com a propriedade heap? E o
terceiro maior elemento? 

\item Considere um heap $d$-ário, em que cada elemento tem exatamente $d$
filhos. 
\begin{enumerate}
\item Como representar um heap $d$-ário em um vetor? 
\item Qual é a altura de um heap $d$-ário com $n$ elementos? 
\item Escreva um algoritmo para a operação Extrai-Máximo. Qual a complexidade
de tempo de seu algoritmo?
\item Escreva um algoritmo para a operação de Inserção, e analise a sua
complexidade de tempo. 
\end{enumerate}

\item Faça uma função que recebe um vetor $v$ com $n$ inteiros e \textbf{
utilizando espaço adicional constante} coloca os números pares no 
começo do vetor e os
números ímpares no fim, devolvendo o índice do primeiro número ímpar, ou $n+1$
se todos os números do vetor forem pares. Diga qual é a complexidade de sua
função, e justifique.

\item Qual a profundidade mínima de uma folha na árvore de decisão de um
algoritmo de ordenação baseado em comparações? 

\item Mostre que são necessárias no mínimo $2n - 1$ comparações para
concatenar duas listas ordenadas com $n$ elementos cada. 

\item Considere $n$ inteiros no intervalo $[1,n^2]$. É possível escrever uma
função para ordená-los em tempo $O(n)$? Justifique. 

\end{enumerate}
\end{document}