\documentclass[12pt]{article}
\usepackage[brazil]{babel}
\usepackage[latin1]{inputenc}
\usepackage{color}
\usepackage{alltt}
\usepackage{graphicx}
\usepackage{latexsym}
\usepackage{amssymb}
\usepackage{amscd}
\usepackage{psfrag}
\usepackage{latexsym}
\definecolor{Pink}{cmyk}{0,1,0,0}
\definecolor{DarkGreen}{rgb}{0,0.5,0}

\title{Lista 10 de An\'{a}lise de Algoritmos}
\author{Nome do Aluno}
\date{12 de novembro de 2007}
\begin{document}
\maketitle

\section*{{\color{blue} Exerc\'{i}cio 25.H}}

O \textsl{problema do mínimo off-line} consiste em manter um conjunto
dinâmico ${\color{red} T}$ de elementos de
${1,2,\ldots,{\color{blue}n}}$ sob as operações de
\textsc{{\color{blue}Insert}} e \textsc{{\color{blue}Extract-Min}}. É
dada uma seqüência ${\color{red}S}$ de ${\color{blue}n}$
\textsc{{\color{blue}Insert}} e ${\color{red}m}$
\textsc{{\color{blue}Extract-Min}}, onde cada chave em
${1,2,\ldots,{\color{blue} n}}$ é inserida exatamente uma
vez. Queremos determinar qual a chave desenvolvida pelas chamadas de
\textsc{{\color{blue}Extract-Min}}. Especificamente, queremos
preencher um vetor \textit{extracted}$[1..{\color{red}m}]$, onde para
${\color{red}i} =
1,2,\ldots,{\color{red}m},\mathit{extracted}[{\color{red}i}]$ é a
chave devolvida pela ${\color{red}i}$-ésima chamada de
\textsc{{\color{blue}Extract-Min}}. O problema é \textsl{off-line} no
sentido de que podemos processar a seqüência ${\color{red}S}$ antes de
determinar cada uma das chaves devolvidas pelos
\textsc{{\color{blue}Extract-Min}}.
\begin{itemize}
\item[a.] Para a seguinte instância do problema, cada
  \textsc{{\color{blue}Insert}} é representada por um número e cada
  \textsc{{\color{blue}Extract-Min}} é representado pela letra
  ${\color{blue}E}$:
  \begin{displaymath}
    {\color{red}4,8,{\color{blue}E},3,{\color{blue}E},9,2,6,{\color{blue}E},{\color{blue}E},{\color{blue}E},1,7,{\color{blue}E},5.}
  \end{displaymath}
  Preencha os valores corretos no vetor \textit{extracted}.
\end{itemize}

Para desenvolver um algoritmo para o problema, quebramos a seqüência
${\color{red}S}$ em subseqüências homogêneas. Isto é, representamos
${\color{red}S}$ por:
\begin{displaymath}
  {\color{DarkGreen}I}_{1},{\color{blue}E},{\color{DarkGreen}I}_{2},{\color{blue}E},{\color{DarkGreen}I}_{3},\ldots,{\color{DarkGreen}I}_{m},{\color{blue}E},{\color{DarkGreen}I}_{m+1}.
\end{displaymath}
onde cada ${\color{blue}E}$ representa um único
\textsc{{\color{blue}Extract-Min}} e cada
${\color{DarkGreen}I}_{{\color{red}j}}$ representa uma seqüência
(possivelmente vazia) de \textsc{{\color{blue}Insert}}. Para cada
subseqüência ${\color{DarkGreen}I}_{{\color{red}j}}$, colocamos
inicialmente as chaves inseridas pelas operações em um conjunto
${\color{Pink}K}_{{\color{red}j}}$, que é vazio se
${\color{DarkGreen}I}_{{\color{red}j}}$ é vazio. Fazemos então o algoritmo
da figura \ref{code:OffLineMinimum}.
\begin{figure}[htp]
  \centering
\begin{alltt}
\textsc{Off-Line-Minimum}(\({\color{red}m}, {\color{blue}n}\))
01  \textbf{para} \({\color{red}i} \leftarrow 1\) \textbf{até} \({\color{blue}n}\)
02    \textbf{faça} determine \({\color{red}j}\) tal que \({\color{red}i} \in {\color{Pink}K}\sb{{{\color{red}j}}}\)
03      \textbf{se} \({\color{red}j} \neq {\color{red}m} + 1\)
04        \textbf{então} \(\mathit{extracted}[{\color{red}j}] \leftarrow i\)
05          seja \({\color{red}e}\) o menor valor maior que \({\color{red}j}\)
              para o qual \({\color{Pink}K}\sb{{{\color{red}e}}}\) existe
06          \({\color{Pink}K}\sb{{{\color{red}e}}}\leftarrow{\color{Pink}K}\sb{{{\color{red}j}}} \cup {\color{Pink}K}\sb{{{\color{red}e}}}\), destruindo \({\color{Pink}K}\sb{{{\color{red}j}}}\)
07  \textbf{devolva} \(\mathit{extracted}\)
\end{alltt}
  \caption{Algoritmo para resolver o \textsl{problema do off-line
      minimum}.}
  \label{code:OffLineMinimum}
\end{figure}
\begin{itemize}
\item[b.] Argumente que o vetor \textit{extracted} devolvido pelo
  algoritmo \textsc{Off-Line-Minimum} está correto.
\item[c.] Descreva como implementar \textsc{Off-Line-Minimum}
  eficientemente usando florestas disjuntas. Dê um limitante justo no
  consumo de tempo de pior caso de sua implementação.
\end{itemize}

\section*{Resposta do {\color{blue} Exerc\'{i}cio 25.H}}

\newpage

\section*{{\color{blue} Exerc\'{i}cio 25.I}}

O \textsl{menor ancestral comum} de dois nós ${\color{red}u}$ e
${\color{DarkGreen}v}$ em uma árvore com raiz ${\color{red}T}$ é o nó
${\color{blue}w}$ que é ancestral de ambos ${\color{red}u}$ e
${\color{DarkGreen}v}$ e tem maior profundidade (\textsl{nível}) em
${\color{red}T}$. No \textsl{problema off-line do menor ancestral
  comum}, é dada uma árvore com raiz ${\color{red}T}$ e um conjunto
arbitrário ${\color{red}P} =
\{{{\color{red}u}_{1},{\color{DarkGreen}v}_{1}}\},\ldots,\{{\color{red}u}_{k},{\color{DarkGreen}v}_{k}\}$
de pares não-ordenados de nós de ${\color{red}T}$, e desejamos
determinar o menor ancestral comum de cada par em ${\color{red}P}$.

Para resolver esse problema, o seguinte procedimento (\ref{code:LCA})
faz um passeio em ${\color{red}T}$ com chamada inicial
\textsc{LCA}(\textit{raiz}(${\color{red}T}$)). Cada nó tem a cor WHITE
antes da chamada.

\begin{figure}[htp]
\begin{alltt}
\textsc{LCA}\(({\color{red}u})\)

01  \textsc{{\color{blue}MakeSet}}\(({\color{red}u})\)
02  \(\mathit{ancestor}[\)\textsc{{\color{blue}FindSet}}\(({\color{red}u})]\leftarrow{\color{red}u}\)
03  \textbf{para cada} \({\color{DarkGreen}v}\) filho de \({\color{red}u}\)
04    \textbf{faça} \textsc{LCA}\(({\color{DarkGreen}v})\)
05      \textsc{Union}\(({\color{red}u},{\color{DarkGreen}v})\)
06      \(\mathit{ancestor}[\textsc{FindSet}({\color{red}u})]\leftarrow{\color{red}u}\)
07  \(\mathit{color}[{\color{red}u}]\leftarrow\)BLACK
08  \textbf{para cada} nó \({\color{DarkGreen}v}\) tal que \(\{{\color{red}u},{\color{DarkGreen}v}\} \in {\color{red}P}\)
09    \textbf{faça se} \(\mathit{color}[{\color{DarkGreen}v}] =\) BLACK
10      \textbf{então} imprima "O menor ancestral comum de \({\color{red}u}\) e {\color{DarkGreen}v} é
          \(\mathit{ancestor}[\textsc{{\color{blue}FindSet}}({\color{DarkGreen}v})]\)"
\end{alltt}
  \caption{Algoritmo para achar o \textit{menor ancestral comum} de
    dois nós.}
  \label{code:LCA}
\end{figure}

\begin{itemize}
\item[a.] Argumente que a linha 10 é executada exatamente uma vez para
  cada par ${{\color{red}u},{\color{DarkGreen}v}} \in {\color{red}P}$.
\item[b.] Argumente que no momento de cada chamada de
  \textsc{LCA}$({\color{red}u})$, o número de conjuntos na floresta é
  igual à profundidade de ${\color{red}u}$ em ${\color{red}T}$.
\item[c.] Prove que \textsc{LCA} imprime corretamente o menor
  ancestral comum de ${\color{red}u}$ e ${\color{DarkGreen}v}$ para
  cada ${\color{red}u}$ em ${\color{red}T}$.
\item[d.] Analise o tempo de processamento de \textsc{LCA}, assumindo
  que a implementação de florestas disjuntas dada em aula é usada.
\end{itemize}

\section*{Resposta do {\color{blue} Exerc\'{i}cio 25.I}}

\end{document}
