\documentclass[12pt]{article}

%% Escrevendo em português:
\usepackage[brazil]{babel}
\usepackage[latin1]{inputenc}

\pagestyle{empty}
\setlength{\textwidth}{17cm}
\setlength{\textheight}{23.5cm}
\setlength{\oddsidemargin}{-5mm}
\setlength{\topmargin}{-5mm}

\newcommand{\N}{\mbox{{\bf N}}}
\newcommand{\Z}{\mbox{{\bf Z}}}
\newcommand{\R}{\mbox{{\bf R}}}
\newcommand{\sse}{\Longleftrightarrow}
\newcommand{\floor}[1]{\lfloor{#1}\rfloor}
\newcommand{\ceil} [1]{\lceil{#1}\rceil}


\def\risonho{{$\bigcirc\!\!\!\!\!\lower.02cm\hbox{\vbox{\offinterlineskip\hbox{$\>\!..$}\vskip.07cm\hbox{$\scriptscriptstyle\smile$}}}$}}
\def\tristonho{{$\bigcirc\!\!\!\!\!\lower.02cm\hbox{\vbox{\offinterlineskip\hbox{$\>\!..$}\vskip.07cm\hbox{$\scriptscriptstyle\frown$}}}$}}

\begin{document}

\begin{center}
{\large
{\bf 
MAC 5711 - Análise de Algoritmos \\
}
}
{\em Departamento de Ciência da Computação} \\
Segundo semestre de 2002 \\

\vspace{3mm}
{\large
{\bf Lista 7} 
}
\end{center}

\begin{enumerate}

% Análise amortizada

\item {\bf (Exercícios 18.1-2 do CLR)} Mostre que se uma operação
  {\bf Decrementa}\ for incluída nas operações de manipulação de um contador
  binário com $k$ bits, $n$ operações poderiam custar até tempo $\Theta(nk)$. 
  
\item {\bf (Exercício 18.1-3 do CLR)} Uma seqüência de $n$ operações é
  executada em uma estrutura de dados. A $i$-ésima operação custa $i$ se $i$ é
  uma potência de 2, e 1 caso contrário. Determine o tempo amortizado por
  operação. 

\item Questão 8 do exame preliminar para o doutorado de agosto de
  e questão 3 do exame de agosto de 2000.  

% union-find

\item {\bf (Exercício 22.4-3 do CLR)} Usando o Lema 22.2 e o Corolário 22.5,
  dê um argumento simples para mostrar que as operações em conjuntos disjuntos
  usando florestas com a heurística da união por {\em rank}\ mas sem a
  heurística da compressão de caminhos executa em tempo $O(m \log n)$.
  
\item Seja $log^* n = \min\{i : \log^{(i)} n \leq 1\},$ onde $\log^{(0)} n = n$
  e, para $k>0$, $\log^{(k)} n = \log \log^{(k-1)} n$. Mostre que $\log(\log^*
  n) = O(\log^*(\log n)).$

\end{enumerate}

\end{document}
