%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Time-stamp: <Thursday 26 Jul 2012 12:49:50pm BRT yoshi@delta-7.local>   
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\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 de Recuperação 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] 
  \begin{enumerate}
  \item[(\textit{i})]Defina precisamente o Problema da Cobertura
    Exata~(PCE) e o Problema da Cobertura Generalizado (PCG); não
    deixe de descrever exatamente as restrições sobre as colunas
    primárias e sobre as colunas secundárias.  

  \item[(\textit{ii})]Lembre-se de que você resolveu o $k$-SAT em seu
    EP2.  Defina precisamente o $k$-SAT.  

  \item[(\textit{iii})]Descreva precisamente como você reduziu o
    $k$-SAT para um problema de cobertura como em~(\textit{i}) acima.
    Caso você tenha usado um problema de cobertura diferente, não
    deixe de definir esse problema precisamente.

  \item[(\textit{iv})]O seguinte trecho vem do enunciado do EP2:
    \begin{quote}
      Fixe~$k$, $n$ e~$m$.  Podemos gerar instâncias aleatórias~$\phi$
      de $k$-SAT com~$n$ variáveis e $m$~cláusulas escolhendo~$m$
      das~$2^k{n\choose k}$ possíveis cláusulas uniformemente a acaso,
      com reposição.  Acredita-se que, para todo~$k$, existe uma
      constante~$c_k$ com a seguinte propriedade:
      \textsl{Seja~$\epsilon>0$ uma constante e suponha
        que~$n\to\infty$.  Se~$m\geq(c_k+\epsilon)n$, então~$\phi$ é
        quase-certamente não-satisfatível, enquanto que
        se~$m\leq(c_k-\epsilon)n$, então~$\phi$ é quase-certamente
        satisfatível.}  Você deverá usar seu programa para estimar
      esta constante~$c_k$ (supondo que ela existe).  Faça isso
      para~$2\leq k\leq 5$ e para alguns valores maiores de~$k$
      (como~$10$ e outros).  Verifique o quão rapidamente seu programa
      consegue resolver $k$-SAT para entradas~$\phi$ aleatórias,
      prestando atenção especialmente nos casos em que~$m$ está em
      torno de~$c_kn$.
    \end{quote}
    Descreva os resultados que você obteve.

\end{enumerate}

\item{}[3~pontos] Suponha que inserimos, nesta ordem, as~4 chaves %
  \.|44 11 33 22| em uma ABB aleatória inicialmente vazia.  Suponha
  que a árvore resultante foi a árvore a seguir: {\small
\begin{verbatim}
      44
     /  
    22   
   /  \
  11  33 
\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; dê todas as
    possibilidades).
  \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.  
  \item[(\textit{iii})]Suponha agora que estamos usando uma ABB
    \textit{padrão} (\textit{não-aleatorizada}) e que inserimos as~4
    chaves %
    \.|11 22 33 44| em uma tal ABB inicialmente vazia em alguma
    ordem.  Podemos fazer isso de~$4!$ jeitos diferentes, pois há~$4!$
    ordenações daquelas chaves.  Diga quais dessas~$4!$ 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.

{\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}
    }

  \end{enumerate}

\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 %
    \.|22 77 11 88 44 55 99 33 66| 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})]Diga exatamente quantas vezes a comparação entre
    chaves \.|less()| (veja o código abaixo) é executada em cada uma
    das~9 inserção em~(\textit{i}).

  \item[(\textit{iii})]Suponha que temos duas ARNEs, com raízes \.|h1|
    e \.|h2|.  Descreva cuidadosamente uma implementação de uma função
    de protótipo \.|void print_inter(link h1, link h2)| que imprime os
    \textit{elementos comuns} a \.|h1| e \.|h2|, isto é, os objetos de
    tipo \.|item| que ocorrem em ambas as ARNEs.  Por simplicidade,
    suponha que os objetos do tipo \.|item| são simplesmente inteiros
    \.|int|.  Sua implementação deve ter complexidade de tempo ótima.

  \item[(\textit{iv})]Qual é a complexidade de tempo da função
    \.|print_inter()| que você descreveu em~(\textit{iii})?  Qual é
    sua complexidade de espaço?  Sua resposta deve ser em função do
    número de elementos~$N_1$ e~$N_2$ nas duas ARNEs envolvidas.
    Suponha que~$N_1=N_2=10^6$ (e os objetos armazenados são
    \.|int|s).  Dê uma estimativa do espaço \textit{adicional} que sua
    função usa quando executada (sua resposta deve ser em \.|bytes|).
    Como seria sua resposta se a exigência fosse que a complexidade de
    \textit{espaço} deve ser ótima?  Justifique suas respostas
    cuidadosamente.

  \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);  

         /* Comparacoes entre chaves */
         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:
