%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Time-stamp: %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \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\\BCC, 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 estamos utilizando uma tabela de hashing com {\tt M} entradas, com resolução de colisões por encadeamento (as {\tt M} listas não são mantidas em ordem). Suponha que usamos a função de hashing que devolve $11k\bmod {\tt M}$ quando a entrada é a $k$-ésima letra do alfabeto (por exemplo, {\tt C} corresponde a $k=3$). Suponha que inserimos em uma tabela inicialmente vazia, nesta ordem, as chaves \begin{verbatim} E A S Y Q U T I O N \end{verbatim} onde ${\tt M}=5$. Desenhe diagramas que ilustram este processo de inserção. \bigskip \item{}[4 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; }; /* item nao sera usado nesta questão */ /* N armazena o número de nós na árvore enraizada naquele nó */ /* Por exemplo, N = 1 nos nós sem filhos */ \end{verbatim} Suponha ainda que não temos nós externos em nossas árvores (a árvore vazia é representada com o ponteiro \verb|head = NULL|). A \textit{profundidade}~$\prof(x)$ de um nó~$x$ em uma árvore com raiz~$r$ é a `distância' de~$r$ a~$x$ na árvore. Alternativamente, a profundidade de um nó~$x$ é definida como sendo~$0$ se~$x=r$ e, se~$x\neq r$, então~$\prof(x)=\prof(x')+1$, onde~$x'$ é o pai de~$x$ na árvore. O \textit{comprimento interno}~$I$ de uma árvore~$T$ é definido como \begin{equation} \label{eq:I_def} I=\sum_x\prof(x), \end{equation} onde a soma é sobre todo nó~$x$ em~$T$. \begin{enumerate} \item[(\textit{i})] Desenhe todas as árvores binárias com~$4$ nós (são~$14$). \item[(\textit{ii})] Determine o comprimento interno de todas as árvores em~(\textit{i}) (várias delas têm~$I=6$). \item[(\textit{iii})] Escreva uma função em~C que recebe uma árvore (isto é, um ponteiro para a raiz de uma árvore) e que devolve o comprimento interno dessa árvore. Sua função deve ter complexidade de tempo proporcional ao número de nós na árvore. \end{enumerate} \bigskip \item{}[4 pontos] Descreva o projeto de um programa que recebe uma cadeia de caracteres~$T$ como entrada e devolve o trecho repetido mais comprido neste texto. Por exemplo, se o texto de entrada for \texttt{aacabcabcbabcbabac}, então a saída de seu programa deve ser \texttt{abcbab}. 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()}). O seu projeto deve supor que a entrada~$T$ pode ser grande; por exemplo, $T$~poderia um livro todo. 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 a $n\log n$, onde~$n$ é o número de caracteres em~$T$, \item[(\textit{ii})] ele gasta uma quantidade de memória proporcional ao número de caracteres em~$T$. \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). \sugestao{Um \textit{sufixo} de uma cadeia de caracteres~$T$ é um `segmento final' dela. Os sufixos de \texttt{abcde} são \texttt{abcde}, \texttt{bcde}, \texttt{cde}, \texttt{de}, \texttt{e}, e a cadeia vazia, com~$0$ caracteres ($6$~sufixos no total). Considere os sufixos de~$T$.} \end{enumerate} \endgroup \end{document} % Local Variables: % mode: latex % eval: (Portug-mode) % TeX-master: t % End: