\documentclass[12pt,a4paper]{article}

%% Escrevendo em português:
\usepackage[brazil]{babel}
\usepackage[latin1]{inputenc} % isso é quase redundante
\usepackage{textcomp}
\usepackage[T1]{fontenc}
%----------------------------
\usepackage[latin1]{inputenc}
\usepackage[brazil]{babel}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{enumerate}
\usepackage{latexsym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{layout}

\addtolength{\parskip}{\baselineskip}

\title{MAC338 - Lista de Exercícios}
\date{02/06/2006}

\begin{document}

\maketitle

Para fazer estes exercícios, você deve ler o capítulo correspondente do CLRS. 

\section{Programação Dinâmica (CLRS, Capítulo~15)}

\begin{enumerate}

\item (CLRS 15.2-1) Encontre a maneira ótima de fazer a
multiplicação das matrizes cujas dimensões são (5, 10, 3, 12, 5,
50, 6).

\item (CLRS 15.2-5) Mostre que são necessários exatamente $n-1$
pares de parênteses para especificar exatamente a ordem de
multiplicação de um produto com $n$ fatores.

\item (CLRS 15.3-2) Desenhe a árvore de recursão para o algoritmo
\textsc{MergeSort} aplicado a um vetor de 16 elementos. Por que a
técnica de programação dinâmica não é capaz de acelerar o
algoritmo?

\item (CLRS 15.4-1) Determine a subseqüência comum máxima de 
$$(1,0, 0, 1, 0, 1, 0, 1)$$ 
e 
$$(0, 1, 0, 1, 1, 0, 1, 1, 0).$$

\item (CLRS 15.4-5) Mostre como o algoritmo da subseqüência comum
máxima pode ser usado para resolver o problema da subseqüência
crescente máxima de uma seqüencia numérica. Dê uma delimitação
justa, em notação $\Theta$ do consumo de tempo de sua solução.

\end{enumerate}

\section{Algoritmos Gulosos (CLRS, Capítulo~16)}

\textbf{Problema dos Intervalos disjuntos:} Dado um conjunto de intervalos
${[s_1, f_1),...,[s_n, f_n)}$ encontrar uma coleção máxima de intervalos
disjuntos dois a dois.  (Obs: Uma definição mais detalhada do problema se
encontra no CLRS sob o nome de \emph{Activity-selection problem}).

\begin{enumerate}

\item (CLRS 16.1-1) Escreva e explique um algoritmo guloso para resolver o
  problema dos intervalos disjuntos.

\item (CLRS 16.1-1) Escreva e explique um algoritmo de programação dinâmica
  para resolver o problema dos intervalos disjuntos.

\item (CLRS 16.1-1) Compare o tempo de execução dos algoritmos dos
exercícios anteriores.

\end{enumerate}

\section{Estruturas de Dados para Famílias de Conjuntos Disjuntos (CLRS,
  Capítulo~21)}  

\begin{enumerate}
  
\item (CLRS 21.3-3) Dê uma seqüência de operações \textsc{MakeSet},
  \textsc{Union}, e \textsc{FindSet} com~$m$ operações no total, $n$~das quais
  \textsc{MakeSet}, que consome tempo~$\Omega(m\log n)$.  Aqui, supomos que
  usamos a estrutura \textit{disjoint-set forest}, com \textit{union by rank}.
  
\item (CLRS 21.4-2) Suponha que usamos a estrutura \textit{disjoint-set
    forest}, com \textit{union by rank} mas sem compressão de caminhos, para
  implementar \textsc{MakeSet}, \textsc{Union}, e \textsc{FindSet}.  Prove que
  para todo elemento~$x$, sempre temos~$\mathit{rank}[x]\leq\log_2n$, onde~$n$
  é o número de \textsc{MakeSet} executados.

\end{enumerate}

\section{Análise Amortizada (CLRS, Capítulo~17)}  

\begin{enumerate}
  
\item CLRS 17.1-3

\item CLRS 17.2-2

\item Faça o Problema CLRS 17-2.
  
\end{enumerate}

\section{Hashing (CLRS, Capítulo~11)}  

\begin{enumerate}
  
\item CLRS 11.2-1

\item CLRS 11.2-2

\item CLRS 11.3-1

\item CLRS 11.3-5

\item CLRS 11.3-6
  
\end{enumerate}

\section{Complexidade (CLRS, Capítulo~34)}  

\begin{enumerate}
  
\item CLRS 34.1-4

\item CLRS 34.2-7

\item CLRS 34.2-8

\item CLRS 34.2-10
  
\end{enumerate}

\end{document}

% Local Variables: 
% mode: latex
% eval: (Portug-mode)
% TeX-master: t
% End: 
