%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Time-stamp: <2012-07-02 23:39:15 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 Substitutiva 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
%\vspace{-\medskipamount}
\noindent{\bf Importante:} faça no máximo três questões.
\smallskip

\begin{enumerate}
  \thispagestyle{empty}  

\item{}[3~pontos] Um dos objetivos principais desta disciplina é
  estudar a noção de tabela de símbolos e investigar várias
  implementações possíveis.
  \begin{enumerate}
  \item[(\textit{i})]Descreva sucintamente uma aplicação de tabelas de
    símbolos.  Seu exemplo deve ser interessante do ponto de vista
    prático ou do ponto de vista teórico.  Seu exemplo deve ser
    substancialmente diferente dos EPs dados durante o semestre.
  \item[(\textit{ii})]No EP4, você comparou várias implementações de
    tabelas de símbolos experimentalmente e escreveu um relatório com
    seus resultados experimentais e suas conclusões.  Reproduza aqui
    os pontos principais de seu relatório.  (Não deixe de descrever em
    detalhe quais experimentos você executou para comparar as várias
    tabelas de símbolos que você implementou.)
  \end{enumerate}

\item{}[3~pontos] 
  \begin{enumerate}
  \item[(\textit{i})]Defina precisamente o Problema da Cobertura
    Exata~(PCE) e o Problema da Cobertura Generalizado (PCG).  Dê um
    exemplo concreto, ilustrativo mas pequeno do PCG.  Dê todas as
    soluções possíveis de seu exemplo.

  \item[(\textit{ii})]O problema das~$N$ rainhas~$Q_N$ consiste em
    colocar~$N$ rainhas em um tabuleiro de xadrez~$N\times N$, sem que
    nenhuma rainha ataque outra.\footnote{Uma rainha ataca outra se
      elas estão na mesma linha, na mesma coluna, ou na mesma
      diagonal.}  Exiba todas as soluções desse problema
    para~$N=1,\dots,4$.

  \item[(\textit{iii})]Descreva precisamente uma redução de~$Q_N$ para
    o~PCG para um~$N$ genérico.  Ilustre sua redução para~$N=3$.
  \end{enumerate}

\item{}[2~pontos] 

  \begin{itemize}
  \item[(\textit{i})]Suponha que inserimos, nesta ordem, as chaves %
    \verb| U M A Q E T O P D R | em uma skip list inicialmente
    vazia.  Suponha que o gerador de números aleatórios fornece os
    seguintes resultados, nessa ordem: %
    \verb| 1 4 5 2 3 3 6 1 2 3 | (assim, p.ex., a célula
    de~\verb|A| fica com~$5$ ponteiros).  Desenhe o resultado final
    dessas~10 inserções.

  \item[(\textit{ii})]Descreva detalhadamente como funciona o processo
    de inserção da chave~\verb|S| na skip list que você obteve
    em~(\textit{i}); suponha que o gerador de números aleatórios
    especificou que esta chave deverá ser inserida em uma célula
    com~$5$ ponteiros.  Em particular, diga quais são todas as
    comparações entre chaves que são executadas nesta inserção.

  \end{itemize}

\item{}[4~pontos] Esta questão trata de árvores rubro-negra
  esquerdistas (ARNEs), usadas para implementar tabelas de símbolos.
  Por simplicidade, suponha que os itens e chaves são inteiros.
  \begin{enumerate}
  \item[(\textit{i})]Suponha que inserimos, nesta ordem, as chaves %
    \.|11 44 99 55 22 88 33 66 77| em uma ARNE inicialmente vazia.
    Desenhe as~9 ARNEs que resultam das~9 inserções acima.  Não
    desenhe árvores 2--3; desenhe ARNEs e execute as inserções
    seguindo rigorosamente a rotina de inserção em ARNEs.

  \item[(\textit{ii})]Escreva uma função de protótipo %
    \.|void STprint_range(Key lo, Key hi)| que imprime, em ordem
    crescente, todos os itens~\.|x| na ARNE
    com~$\.|lo|\leq\.|x|\leq\.|hi|$.  Para tanto, escreva e use uma
    função recursiva de %
    protótipo \.|void print_rangeR(link h, Key lo, Key hi)|.  Sua
    função não deve percorrer ``partes desnecessárias'' da ARNE.  O
    que ocorre quando executamos \.|STprint_range(lo, hi)| com~\.|lo|
    e~\.|hi| iguais?

  \item[(\textit{iii})]Qual é a complexidade de tempo da função
    \.|STprint_range()| que você implementou?  Sua resposta deve ser
    em função do número total de elementos~$N$ na ARNE e do número de
    elementos entre~\.|lo| e~\.|hi| na ARNE.  Justifique sua resposta.

  \end{enumerate}

  \bigskip\noindent
  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

\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:
