%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Time-stamp: <Monday 23 Jun 2008 08:55:36pm BRT yoshi@turan.ime.usp.br>   
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\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\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[MAC0323 Estruturas de dados]{Segunda Prova de Estruturas de 
  Dados\\BCC, 1{\tiny o.} semestre de 2008} %\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}

%\medskip\noindent
%\textbf{Faça no máximo 3 questões!}
\medskip

\onehalfspacing

\begin{enumerate}
\thispagestyle{empty}  
\item{}[4~pontos]
  \begin{enumerate}
  \item[(\textit{i})]Suponha que inserimos, nesta ordem, as chaves %
    \verb| Q U E S T A O F C I L | em uma árvore 2-3-4 inicialmente vazia.
    Desenhe as árvores 2-3-4 que temos ao longo do processo.  Desenhe pelo
    menos 11 árvores; para dizer como o árvore evolui, voce pode (deve?)
    desenhar árvores intermediárias/auxiliares.
  \item[(\textit{ii})]Suponha agora que inserimos, nesta ordem, as chaves %
    \verb| Q U E S T A O F C I L | em uma árvore rubro-negra esquerdista
    (ARNE) inicialmente vazia.  Desenhe as ARNEs correspondentes às
    últimas~$3$ árvores 2-3-4 do item~(\textit{ii}) (desenhe as~$3$
    árvores resultantes da inserção de~\verb|C|, \verb|I| e~\verb|L|).
  \item[(\textit{iii})]Descreva cuidadosamente como ocorre a inserção
    de~\verb|L| na sua ARNE (queremos saber aqui como a 2a.~ARNE que
    você desenhou no item~(\textit{ii}) acima evolui para se tornar a
    3a.~ARNE que você desenhou).  Para responder a este item, desenhe
    várias ARNEs (ou partes de ARNE) para ilustrar a execução do
    algoritmo de inserção em ARNEs.  O código de inserção em ARNEs
    segue abaixo.
  \end{enumerate}
%  {\small
\begin{verbatim}
   link RBinsert(link h, Item item)
   {  Key v = key(item);
      if (h == z) 
         return NEW(item, z, z, 1); /* o 1 indica ponteiro vermelho */
      if (h->l->red && h->r->red)) colorFlip(h);
      if (less(v, key(h->item))) h->l = insert(h->l, item); 
                            else h->r = insert(h->r, item); 
      if (h->r->red) h = rotL(h);
      if (h->l->red && h->l->l->red) h = rotR(h);
      return h;
   }
   void STinsert(Item item)
   {  head = RBinsert(head, item); head->red = 0; }
\end{verbatim}
%  }\noindent
  
\newpage
\item{}[4~pontos] 
  \begin{enumerate}
  \item[(\textit{i})]Desenhe todas as possíveis árvores 2-3-4 para~$N$ itens,
    para~$1\leq N\leq7$.  (Use as chaves \verb|A B C D E F G|.)
    \observacao{Para~$N=3$, temos duas tais árvores e para~$N=7$ temos~$9$.}
  \item[(\textit{ii})]Suponha que inserimos as chaves %
    \verb| A B C D E | em uma das~$5!=120$ ordenações possíveis, com
    todas as possibilidades equiprováveis, em uma árvore 2-3-4
    inicialmente vazia.  Diga quais são as possíveis árvores que
    podemos obter nesse processo.
  \item[(\textit{iii})]Suponha que inserimos as chaves %
    \verb| A B C D E | em uma das~$5!=120$ ordenações possíveis, com
    todas as possibilidades equiprováveis, em uma ARNE inicialmente
    vazia.  Quais ARNEs com~$5$ nós internos podemos obter?  Diga a
    probabilidade de obtermos cada uma dessas árvores.
  \end{enumerate}
  
\item{}[2~pontos] Suponha que inserimos, nesta ordem, as chaves %
  \verb| Q U E S T A O F C I L | em uma tabela de hashing inicialmente
  vazia com~$M=12$ entradas.  Suponha que usamos a função de hashing
  $13k\bmod M$ para transformar a $k$-ésima letra do alfabeto no
  endereço da tabela (por exemplo, \verb|A|~é levado ao endereço~$1$
  e~\verb|S| é levado ao endereço~$7$).  Mostre claramente a evolução
  da tabela nesse processo. Considere os seguintes dois casos: 
  \begin{enumerate}
  \item[(\textit{i})]Neste item, suponha que usamos resolução de
    colisões por encadeamento (\textit{separate chaining}). 
  \item[(\textit{ii})]Neste segundo item, suponha que usamos
    resolução de colisões por \textit{linear probing}.
  \end{enumerate}

\item{}[1~pontos] Desenhe a \textit{trie} que obtemos ao inserirmos as
  seguintes chaves em uma \textit{trie} inicialmente vazia:
\begin{verbatim}
01111100
10101100
00011101
01011101
10111100
01111101
01101100
11011100
\end{verbatim}
  Nesta questão, você não precisa desenhar cada etapa do processo de
  inserção; basta desenhar o resultado final.  

\end{enumerate}

\end{document}

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

