%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Time-stamp: <2012-07-11 17:09:11 yoshi>   
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\documentclass[11pt,reqno]{amsart}

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

%\usepackage{refcheck}
\usepackage{srcltx}

\usepackage{fullpage}
\usepackage{setspace}

\let\:=\colon
\let\.=\verb
\let\epsilon=\varepsilon
\def\e{{\rm e}}
\def\dist{\mathop{\rm dist}\nolimits}
\def\supp{\mathop{\rm supp}\nolimits}
\def\ex{\mathop{\rm ex}\nolimits}
\def\bsigma{\bar\sigma}
\def\RR{\mathbb R}
\def\NN{\mathbb N}
\def\ZZ{\mathbb Z}
\def\({\left(}
\def\){\right)}  
\def\<{\langle}
\def\>{\rangle}
%\let\sim=\thicksim

\def\inR{\mathrel{\in_{\text R}}} 

\def\cA{\mathcal A}
\def\cB{\mathcal B}
\def\cC{\mathcal C}
\def\cD{\mathcal D}
\def\cF{\mathcal F}
\def\cG{\mathcal G}
\def\cH{\mathcal H}
\def\cI{\mathcal I}
\def\cL{\mathcal L}
\def\cP{\mathcal P}
\def\cR{\mathcal R}
\def\cS{\mathcal S}

\def\barp{{\bar p}}

\def\Bi{\mathop{{\rm Bi}}\nolimits}
\def\Var{\mathop{{\rm Var}}\nolimits}
\def\Cov{\mathop{{\rm Cov}}\nolimits}
\def\dev{\mathop{{\rm dev}}\nolimits}
\def\og{\mathop{{\rm og}}\nolimits}

\def\EE{\mathop{\hbox{\hbox{${\mathbb E}$}}}\nolimits}
\def\PP{\mathop{\hbox{\raise.03ex\hbox{${\mathbb P}$}}}\nolimits}
\def\FF{\mathop{\hbox{\raise.03ex\hbox{${\mathbb F}$}}}\nolimits}

\def\RP{\mathbf{RP}}
\def\BPP{\mathbf{BPP}}

\def\bfx{\textbf{x}}
\def\bfy{\textbf{y}}

\makeatletter
\renewcommand{\labelenumi}{\theenumi.}
\makeatother

\def\datedue#1{$\{$\textsl{Data de entrega}: #1$\}$}
\def\sugestao#1{[\textit{Sugestão.} #1]}
\def\observacao#1{[\textit{Observação.} #1]}

\begin{document}
\title[MAC323 Estruturas de dados]{Prova 2 de Estruturas de 
  Dados\\BCC, 1{\tiny o.} semestre de 2012}
\date{Versão de \today}
\maketitle
\footskip=20pt

\vspace{-\medskipamount}
\noindent{\bf Instruções:}
\begin{enumerate}\small
\item Não destaque as folhas do caderno de soluções.
\item A prova pode ser feita a lápis.  Cuidado com a legibilidade.
%\item Há~$3$ questões na prova. Verifique antes de começar a prova
%se o seu caderno de questões está completo.
\item Não é permitido o uso de folhas avulsas para rascunho.
%\item Nas questões que envolvem elaboração de programas, coloque
%comentários suficientes para que o programa seja facilmente
%compreendido.
\item Não é necessário apagar rascunhos no caderno de soluções.
\item Asserções imprecisas valem pouco.  Justifique suas asserções (dentro do
  razoável). 
\end{enumerate}

\smallskip
\onehalfspacing

\begin{enumerate}
  \thispagestyle{empty}  

\item{}[4~pontos] Suponha que inserimos, nesta ordem, as~6 chaves %
  \.|33 11 44 55 99 22| em uma ABB aleatória inicialmente vazia.
  Suponha que a árvore resultante foi a árvore a seguir: {\small
\begin{verbatim}
             55
            /  \
          33    99
         / \
        22 44
       /
      11
\end{verbatim}
  }
  \begin{enumerate}
  \item[(\textit{i})]Mostre como se deu essa evolução da ABB vazia até esta
    ABB resultante (desenhe as várias ABBs intermediárias).  
  \item[(\textit{ii})]Determine a probabilidade de termos essa ABB
    resultante com base no algoritmo de inserção em ABBs aleatorizadas
    (as rotinas são dadas a seguir).  Mostre como você chegou a seu
    resultado.  {\small
  \begin{verbatim}
    link insertT(link h, Item item)
      { Key v = key(item);
        if (h == z) return NEW(item, z, z, 1); 
        if (less(v, key(h->item))) { h->l = insertT(h->l, item); h = rotR(h); }
                              else { h->r = insertT(h->r, item); h = rotL(h); }
        return h;
      }

    link insertR(link h, Item item)
      { Key v = key(item), t = key(h->item);
        if (h == z) return NEW(item, z, z, 1);
        if (rand() < RAND_MAX/(h->N+1)) return insertT(h, item); 
        if (less(v, t)) h->l = insertR(h->l, item);
                   else h->r = insertR(h->r, item);
        (h->N)++;
        return h;
      }

    void STinsert(Item item)
      { head = insertR(head, item); }
  \end{verbatim}
    }

  \item[(\textit{iii})]Suponha agora que estamos usando uma ABB
    \textit{padrão} (\textit{não-aleatorizada}) e que inserimos as~6
    chaves %
    \.|11 22 33 44 55 99| em uma tal ABB inicialmente vazia em alguma
    ordem.  Podemos fazer isso de~$6!$ jeitos diferentes, pois há~$6!$
    ordenações daquelas chaves.  Descreva quais dessas~$6!$ ordenações
    resultam na árvore dada no diagrama acima.  Explique sua resposta.

  \item[(\textit{iv})]Explique a relação entre suas respostas
    para~(\textit{ii}) e~(\textit{iii}) acima.
  \end{enumerate}

\item{}[4~pontos] Esta questão trata de árvores rubro-negra
  esquerdistas (ARNEs).
  \begin{enumerate}
  \item[(\textit{i})]Suponha que inserimos, nesta ordem, as chaves %
    \.|22 11 66 33 55 88 44 77 99| em uma ARNE inicialmente vazia.
    Desenhe as~9 ARNEs que resultam das~9 inserções acima.
  \item[(\textit{ii})]Suponha que inserimos, nesta ordem, as chaves %
    \.|11 22 33 44 55 66 77 88 99| em uma ARNE inicialmente vazia.
    Desenhe a ARNE final desse processo.
  \item[(\textit{iii})]Repita~(\textit{ii}) com a seqüência %
    \.|99 88 77 66 55 44 33 22 11|.
  \end{enumerate}
  As duas rotinas principais envolvidas na inserção em ARNEs são dadas
  a seguir.
  {\small
\begin{verbatim}
     link LLRBinsert(link h, Item item)
       { Key v = key(item);
 
        /* Insert a new node at the bottom*/
         if (h == z) return NEW(item, z, z, 1, 1);  

         if (less(v, key(h->item))) hl = LLRBinsert(hl, item); 
                               else hr = LLRBinsert(hr, item); 

         /* Enforce left-leaning condition */
         if (hr->red && !hl->red) h = rotL(h);
         if (hl->red && hll->red) h = rotR(h);
         if (hl->red && hr->red) colorFlip(h);

         return fixNr(h);
       }
     
     void STinsert(Item item)
       { head = LLRBinsert(head, item); head->red = 0; }
\end{verbatim}
  }\noindent
  
\item{}[3~pontos] Queremos um programa \.|ind| que faz o seguinte: a
  entrada de \.|ind| será um arquivo texto, contendo um livro, com as
  páginas separadas por um caracter especial, por exemplo, \.|^L|
  (isto é, todo fim de página é marcado por uma linha que contém
  \.|^L| no início e nada mais).  Ao receber essa entrada, \.|ind|
  deve gerar como saída um ``índice remissivo completo'', isto é, a
  lista de palavras distintas que ocorrem no livro dado, em ordem
  alfabética, com cada palavra seguida de uma lista de números,
  indicando em quais páginas essa palavra ocorre: se a palavra~$w$
  ocorre nas páginas de número~$p_1,p_2,\dots$, então a linha

  $w\quad p_1,p_2,\dots$

  \noindent
  deve ocorrer nesse índice.
  \begin{itemize}
  \item[(\textit{i})]Descreva, muito brevemente e em linhas gerais,
    como você poderia implementar~\.|ind|.  Se um livro~$T$ tem~$N$
    palavras no total e~$M$ palavras distintas, quanto tempo sua
    implementação de \.|ind| levará para processar~$T$?  (Responda
    usando a notação~$O$.)  Justifique sua resposta (naturalmente,
    você deve descrever uma implementação eficiente para \.|ind|).

  \item[(\textit{ii})]Suponha agora que \.|ind| recebe também como
    entrada uma lista ordenada~$D$ de palavras que contém todas as
    palavras do português.  Além de produzir o índice remissivo para o
    livro~$T$, como descrito acima, \.|ind| deve também produzir a
    lista de palavras que \textit{ocorrem} em~$T$ mas \textit{não
      ocorrem} em~$D$ (assim, \.|ind| serve como um verificador
    ortográfico).  Descreva, em algum detalhe, como você implementaria
    essa parte adicional em \.|ind|.  Quanto tempo sua implementação
    de \.|ind| levaria para executar \textit{essa tarefa adicional},
    supondo que~$T$ tem~$N$ palavras no total, $M$~palavras distintas,
    e~$D$ tem~$P$ palavras?  (Responda usando a notação~$O$.)
    Justifique sua resposta (naturalmente, você deve descrever uma
    implementação eficiente para essa parte adicional também).

  \item[(\textit{iii})] Suponha que \.|ind| seja implementado como
    você descreveu em~(\textit{i}) e~(\textit{ii}) acima.  Com base na
    experiência que você adquiriu com os EPs dessa disciplina, estime
    quanto tempo ele levará para processar um livro com, digamos,
    $N=300.000$ e~$M=30.000$ (esses são, aproximadamente, os
    parâmetros para \textit{Ulysses}, de James Joyce), supondo que~$D$
    tenha~$3.000.000$ palavras (esse é um número arbitrário).  Sua
    estimativa pode ser algo como ``poucos segundos'', ``poucos
    minutos'', ``alguns minutos'', etc.  Relate experiências
    concretas que você teve que o levam a dar esta estimativa.

  \end{itemize}

\end{enumerate}

\end{document}

%%% Local Variables: 
%%% mode: latex
%%% eval: (iso-accents-mode t)
%%% eval: (auto-fill-mode t)
%%% eval: (LaTeX-math-mode t)
%%% TeX-master: t
%%% End:
