%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Time-stamp: <2012-07-11 00:53:45 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\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 1 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{}[3~pontos] 
  
  \begin{enumerate}
  \item[(\textit{i})] Dê uma descrição de alto nível das estruturas de
    dados e algoritmos que você implementou para resolver o EP1.

  \item[(\textit{ii})] Faça uma discussão sobre a eficiência de sua
    solução do EP1.  Quanto tempo seu programa demora para processar
    uma instância com~$N$ palavras?  De quanto espaço seu programa
    precisa para processar uma instância com~$N$ palavras?  Faça uma
    estimativa da memória necessária no caso em que a entrada
    tem~$1$GB.  Justifique sua resposta.
    
  \item[(\textit{iii})] Você conhece outras formas de se resolver o
    EP1?  Como é a complexidade destas outras soluções?  (Faça uma
    análise como em (\textit{ii}).)

  \end{enumerate}
 
\item{}[3~pontos] Um time com~$2N$ jogadores~$1,\dots,2N$ passará uma
  semana concentrado, treinando.  Cada dois deles compartilharão um
  quarto.  Para cada par de jogadores, você sabe se eles concordam ou
  não dividir um quarto.  O seu trabalho é descobrir quais são todas
  as formas possíveis de se organizar a divisão dos~$2N$ jogadores
  em~$N$ quartos; vamos chamar esse problema de o Problema da Divisão
  em Quartos~(PDQ).
  \begin{enumerate}
  \item[(\textit{i})] Suponha que~$N=4$ e os pares de jogadores que
    concordam em compartilhar um quarto
    são~$\{1,2\},\{2,3\},\{3,4\},\{4,5\},\{5,6\},\{6,7\},\{7,8\}$,
    e~$\{1,8\}$.  Resolva esta instância (isto é, diga quais são todas
    as possíveis formas de colocar esses~$8$ jogadores em~$4$
    quartos).

  \item[(\textit{ii})] Defina (precisamente) o Problema da Cobertura
    Exata~(PCE) e dê um exemplo.

  \item[(\textit{iii})] Descreva (precisamente) uma redução do~PDQ
    para o~PCE.  Dê uma instância para o PCE cujas coberturas exatas
    correspondem à solução do exemplo em~(\textit{i}).
  \end{enumerate}
  
\item{}[4~pontos] 

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

  \item[(\textit{ii})]Descreva como funciona o processo de inserção da
    chave~\verb|J| 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~$2$ ponteiros.  Em
    particular, diga quais são todas as comparações entre chaves que
    são executadas nesta inserção.

  \item[(\textit{iii})]Suponha que o prof.~Néscio~(PN) resolve usar
    uma skip list para manter um conjunto de inteiros positivos,
    usando a ordem usual dos inteiros para ordenar as chaves (e não a
    ordem alfabética).  Suponha que~PN decide usar um gerador de
    números aleatórios um tanto complicado, com o comportamento
    descrito a seguir.  Para decidir quantos ponteiros usar em uma
    célula, o gerador examina o inteiro~$x$ presente na célula e faz o
    seguinte: se~$2^k$ divide~$x$ mas~$2^{k+1}$ não divide
    ($k\in\NN$), então o gerador devolve~$k+1$.  Assim, p.ex., o
    inteiro~$12$ ficaria em uma célula com~$3$ ponteiros, enquanto
    que~$7$ ficaria em uma célula com~$1$ ponteiro.
    \begin{itemize}

    \item[(\textit{a})]Como é a skip list do prof.~Néscio se as chaves
      presentes são os inteiros~$1,2,\dots,15$?  

    \item[(\textit{b})]Suponha agora que~$t\geq1$ e o prof.~Néscio
      insere os inteiros~$1,2,\dots,2^t-1$ em uma skip list
      inicialmente vazia.  Suponha agora que ele faz uma busca do
      inteiro~$2^t$.  Qual é a complexidade desta busca?  (Estamos
      interessados no caso em que~$t$ é grande.)  Você considera esta
      complexidade boa ou ruim?

    \item[(\textit{c})]Suponha agora que o prof.~Néscio remove todos
      os números pares de sua lista em~(\textit{b}).  Como fica sua
      skip list?  PN~agora faz uma busca do inteiro~$2^t$.  Qual é a
      complexidade desta busca?  Você considera esta complexidade boa
      ou ruim?

    \item[(\textit{d})]Explique ao prof.~Néscio por que é fácil
      para um usuário maldoso gerar instâncias ruins para o esquema de
      skip lists dele.  Por que o esquema usual de skip lists não tem
      esse defeito?

    \end{itemize}

  \end{itemize}

%\item{}[3~pontos] 

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