%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Time-stamp: <Thursday 07 Dec 2006 07:23:57am EDT yoshi@erdos.ime.usp.br>   
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\documentclass[11pt,reqno]{amsart}

%% Escrevendo em português:
\usepackage[brazil]{babel}
\usepackage[latin1]{inputenc}
%----------------------------

%\usepackage{refcheck}
\usepackage{srcltx}
\usepackage{fullpage}
%\usepackage{doublespace}
\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\llfloor{\left\lfloor}
\def\rrfloor{\right\rfloor}
\def\llceil{\left\lceil}
\def\rrceil{\right\rceil}
\def\({\left(}
\def\){\right)}  
\def\<{\langle}
\def\>{\rangle}
%\let\sim=\thicksim

\newcommand{\tdots}{\,.\,.\,} % in place of \ldots
\newcommand{\larr}{\leftarrow}

\newcommand{\phentao}{\phantom{então}} 
\newcommand{\phsenao}{\phantom{senão}} 
\newcommand{\x}{\hspace*{3ex}} % era 4ex
\newcommand{\xx}{\hspace*{6ex}}
\newcommand{\xxx}{\hspace*{9ex}}
\newcommand{\xxxx}{\hspace*{12ex}}
\newcommand{\xxxxx}{\hspace*{15ex}}
\newcommand{\xxxxxx}{\hspace*{18ex}}
\newlength{\tsts}
\settowidth{\tsts}{9}
\newcommand{\ts}{\hspace{\tsts}}
\newcommand{\RM}{\textrm}
\newenvironment{pseudoc}
         {\begin{list}%
                {}%
                {%
                 \sffamily%
                 \setlength{\partopsep}{1ex}%
                 \setlength{\topsep}{1ex}%
                 \setlength{\leftmargin}{\parindent}%
                 \setlength{\parsep}{0.5ex}%
                }%
          \item}%
         {\end{list}%
         }
\newenvironment{pseudocode}%
         {\begin{pseudoc}%
          \textbf{\textrm{Algoritmo}}\hspace{0.7ex}\ignorespaces%
         }%
         {\end{pseudoc}}

\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\prof{\mathop{{\rm prof}}\nolimits}
\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}\onehalfspace 
\title[MAC0122 Algoritmos]{Terceira Prova de Princípios de Desenvolvimento de 
  Algoritmos\\BE/BM/BMA, 2{\tiny o.} semestre de 2006} %\date{Versão de \today}
\maketitle
\footskip=20pt

\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!). 
%\item \textbf{IMPORTANTE:} \textbf{Faça no máximo 3 questões.}
\end{enumerate}

\bigskip

\begin{enumerate}
%\thispagestyle{empty}  
\item{}[3 pontos] Suponha que inserimos, nesta ordem, as chaves 
\begin{verbatim}
  Q U E S T A O F C I L
\end{verbatim}
  em uma árvore binária de busca (ABB) inicialmente vazia.  Desenhe as
  ABBs resultantes após cada inserção.

\bigskip
\item{}[5 pontos] Esta questão trata de árvores binárias.  Suponha que temos
\begin{verbatim}
typedef struct node *link;
struct node { Item item; link l, r; int N; };
/* N armazena o número de nós (internos) na árvore enraizada naquele nó */
/* Por exemplo, N deve ser 11 na raiz de sua árvore da Questão 1 */

link rotR(link h)
  { link x = h->l; h->l = x->r; x->r = h; 
    return x; }

link rotL(link h)
  { link x = h->r; h->r = x->l; x->l = h; 
    return x; }

Item selectR(link h, int k)
  { int t = h->l->N;
    if (h == z) return NULLitem;
    if (t > k) return selectR(h->l, k);
    if (t < k) return selectR(h->r, k-t-1);
    return h->item;
  }

link partR(link h, int k)
  { int t = h->l->N; 
    if (t > k )
      { h->l = partR(h->l, k); h = rotR(h); }
    if (t < k )
      { h->r = partR(h->r, k-t-1); h = rotL(h); }
    return h;
  }
\end{verbatim}
  O código acima supõe que estamos adotando as várias convenções que temos
  seguido nas aulas.  Suponha que~\verb|head| aponta para a raiz de sua árvore
  da Questão~1.
  \begin{enumerate}
  \item[(\textit{i})] Desenhe o resultado de \verb|rotR(head)| e
    \verb|rotL(head)|.  Indique em seus diagramas as novas raízes nessas
    árvores. 
    
  \item[(\textit{ii})] Desenhe a árvore que temos depois de executar a
    atribuição
\begin{verbatim}
  head->l = rotL(head->l);
\end{verbatim}
    
  \item[(\textit{iii})] Qual é o resultado da execução de \verb|selectR(head, 6)|? 

  \item[(\textit{iv})] Qual é o resultado da execução de \verb|partR(head, 6)|? 
  \end{enumerate}

\bigskip
\item{}[4 pontos] 
  Dizemos que uma palavra~$s$ é um {\it anagrama\/} de uma palavra~$t$
  se~$s$ pode ser obtida de~$t$ pela permutação de suas letras.  Por
  exemplo, as palavras {\it triangle\/}, {\it relating\/}, {\it
    integral\/}, {\it altering\/}, e {\it alerting\/} são todas
  anagramas umas das outras.  Descreva {\it cuidadosamente\/} o
  projeto de um programa que resolve o seguinte problema: a entrada é
  um conjunto~$D$ de palavras e a saída deve ser um conjunto~$S$ de
  anagramas com~$S\subset D$.  Ademais, o conjunto~$S$ deve ser de
  cardinalidade máxima.
  
  O seu projeto deve supor que a entrada~$D$ pode ser grande; por
  exemplo, $D$~poderia ser o conjunto de palavras de um dicionário.
  Um programa implementado de acordo com o seu projeto deve ser tal
  que
  \begin{enumerate}
  \item[(\textit{i})] sob hipóteses razoáveis, ele leva tempo
    basicamente proporcional ao número de palavras em~$D$,
    
  \item[(\textit{ii})] ele gasta uma quantidade de memória
    proporcional ao número de palavras em~$D$.
  \end{enumerate}
  Você deve argumentar por que o programa teria estas propriedades (em
  particular, você deve explicitar as hipóteses que você usa em sua
  análise).
  
  Faça uma descrição cuidadosa de seu projeto de programa: descreva a
  estrutura de dados a ser usada e dê os protótipos das funções principais,
  com uma descrição de o que estas funções devem fazer e como elas poderiam
  ser implementadas (não esqueça do \texttt{main()}).
 
  \sugestao{Chame de {\it assinatura\/} de uma palavra~$s$ a cadeia de
    caracteres que obtemos ao ordenar as letras em~$s$.  Por exemplo,
    a assinatura de `assinatura' é `aaainrsstu'.  Use este conceito.}

\end{enumerate}  

\endgroup 
\end{document}

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

