%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Time-stamp: <Tuesday 29 Apr 2008 02:32:35am 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]{Primeira 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}

\smallskip
\onehalfspacing

\begin{enumerate}
\thispagestyle{empty}  
\item{}[3~pontos] Seja dado um inteiro positivo~$N$.  Queremos gerar~$N$
  inteiros~$x_1,\dots,x_N$ em~$S=\{0,1,\dots,N^2-1\}$, \textit{sem repetição},
  com todos os inteiros em~$S$ equiprováveis.  Descreva um algoritmo para fazer
  isso.  Seu algoritmo pode usar espaço~$O(N)$ e deve ter complexidade de
  tempo não muito maior que~$O(N)$, isto é, ele deve demorar tempo não muito
  maior que~$O(N)$ (se você conseguir um algoritmo que, tipicamente, roda em
  tempo~$O(N\log N)$, já está bom).  Diga explicitamente quais são suas
  hipóteses e justifique suas afirmações ao descrever sua solução.
  
  Você deve supor que você tem acesso a um gerador de números aleatórios
  \verb|RAND()|, que devolve um inteiro em~$S$, com todos esses inteiros
  equiprováveis.
  
\item{}[3~pontos] Sejam dadas duas matrizes~$A=(a_{ij})$ e~$C=(c_{ij})$ de
  inteiros, ambas~$m\times n$, satisfazendo~$a_{ij}\leq c_{ij}$ para todo~$i$
  e~$j$.  Uma solução para o problema~$P(A,C)$ é uma matriz de
  inteiros~$B=(b_{ij})$ com~$a_{ij}\leq b_{ij}\leq c_{ij}$ para todo~$i$
  e~$j$, com a propriedade de que (a)~em toda linha de~$B$ um mesmo inteiro
  não ocorre mais de uma vez, e (b)~em toda coluna de~$B$ um mesmo inteiro não
  ocorre mais de uma vez.
  \begin{enumerate}
  \item[(\textit{i})]Considere as matrizes
    \begin{equation}
      \label{eq:1}
      A=\begin{pmatrix}
        1&2&2\\
        3&3&4
      \end{pmatrix},
      \qquad
      C=\begin{pmatrix}
        2&3&3\\
        4&5&5
      \end{pmatrix}.
    \end{equation}
    Encontre uma solução para o problema~$P(A,C)$ para as matrizes~$A$ e~$C$
    acima. 
  \item[(\textit{ii})]Exiba explicitamente uma matriz~$M$ para o Problema da
    Cobertura Generalizada (PCG) com a propriedade de que as soluções do~PCG
    para~$M$ correspondem às soluções do~$P(A,C)$, onde~$A$ e~$C$ são as
    matrizes dadas em~\eqref{eq:1}.
  \item[(\textit{iii})]Resolva~(\textit{ii}) para matrizes~$A$ e~$C$
    genéricas.  (Naturalmente, você deve descrever~$M$ de alguma forma
    sistemática, em função dos~$a_{ij}$ e~$c_{ij}$.)
  \end{enumerate}
  
\item{}[4~pontos] Seja~$B_N$ uma ABB obtida da seguinte forma: sorteamos uma
  permutação das chaves~$1,\dots,N$, com todas as~$N!$ permutações
  equiprováveis.  Inserimos essas chaves em uma ABB inicialmente vazia, na
  ordem dada pela permutação sorteada.  Seja~$B_N$ a ABB (aleatória) assim
  obtida. 
  \begin{enumerate}
  \item[(\textit{i})]Desenhe todas as ABBs com~$N=4$ nós (são 14), supondo que
    temos as chaves~$A$, $B$, $C$ e~$D$.  Diga qual é a probabilidade de obtermos
    cada uma delas como uma~$B_N$ (naturalmente, com~$N=4$).
  \item[(\textit{ii})]Considere agora o algoritmo de inserção aleatorizado,
    visto em sala (Programa 13.2 de Sedgewick), reproduzido abaixo:
  \end{enumerate}
  {\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}
  }\noindent
Considere a ABB {\small
\begin{verbatim}
                    C
                   / \
                  B   D
                 /
                A
\end{verbatim}
}\noindent Suponha que inserimos as chaves~$A$, $B$, $C$, e~$D$ em uma ABB
inicialmente vazia, usando o algoritmo de inserção aleatorizado dado acima.
Diga qual é a probabilidade de obtermos a ABB acima, quando executamos as
inserções nas três ordens abaixo:
\begin{enumerate}
\item[(\textit{a})]$A$, $B$, $C$, $D$,
\item[(\textit{b})]$D$, $C$, $B$, $A$,
\item[(\textit{c})]$B$, $D$, $A$, $C$.
\end{enumerate}
Para determinar as probabilidades pedidas acima, você deve fazer as contas
explicitamente, analisando o algoritmo passo a passo.

\end{enumerate}

\end{document}

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

