<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Time-stamp: &lt;Monday 25 Sep 2006 09:59:41am BRT yoshi@erdos.ime.usp.br&gt;   
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\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\&lt;{\langle}
\def\&gt;{\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\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]{Primeira 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{}[2 pontos] Diga se são verdadeiras ou falsas as seguintes fórmulas:
  \begin{itemize}
  \item[(\textit{i})] $5n(n-1)(n-2)=5n^3+O(n^2)$
  \item[(\textit{ii})] $5n(n-1)(n-2)=O(n^3)$
  \item[(\textit{iii})] $2^{f(n)}=O(2^{n^3})$, onde~$f(n)=5n(n-1)(n-2)$ é como
    em~(\textit{ii}) 
  \item[(\textit{iv})] $H_n=1+1/2+1/3+\dots+1/n=\sum_{1\leq k\leq n}1/k=O(\log
    n)$
  \end{itemize}
  Justifique suas respostas.

  \medskip  
\item{}[3 pontos] Considere o problema da conexidade, estudado no começo do
  semestre: são dados pares~$p_1,\dots,p_M$ com~$p_i=(x_i,y_i)$ e~$0\leq
  x_i,y_i&lt;N$ para todo~$i$.  Queremos `filtrar' esta seqüência de pares de
  forma que apenas aqueles pares `essenciais' sejam impressos (o par~$p_i$
  deve ser impresso se e só se~$x_i$ e~$y_i$ pertencem a diferentes
  componentes conexas definidas pelos pares~$p_j$ ($j&lt;i$)).

  \begin{itemize}
  \item[(\textit{i})] Suponha que a entrada é 
    $$
    (1,4), (1,9), (2,5), (6,9), (0,8), (3,7), (1,8), (2,0),
    $$
    $$
    (3,5), (3,8), (5,9), (6,0), (6,7), (2,4), (4,7).
    $$
    Qual é a saída correspondente?  Não dê apenas a saída; mostre como você
    chegou a ela (basta fazer uns diagramas e explicar o que está
    ``acontecendo'').
    
  \item[(\textit{ii})] Descreva cuidadosamente uma solução para este problema.
    (Lembre-se de que vimos várias estruturas de dados e algoritmos em sala.)
    Não deixe de exemplificar como a solução que você descreve funciona no
    exemplo em~(\textit{i}).

  \item[(\textit{iii})] O que ocorre se reordenarmos os pares na entrada dada
    em~(\textit{i})?  Mais precisamente, a saída será necessariamente
    diferente?  Poderá ser diferente?  O número de pares na saída é o mesmo
    para qualquer ordenação dos pares em~(\textit{i})?  Você consegue
    encontrar duas ordenações dos pares em~(\textit{i}) de forma que as saídas
    sejam disjuntas (um mesmo par não aparece em ambas as saídas)?  Por quê? 

  \end{itemize}

  \medskip  
\item{}[3 pontos] Escreva um algoritmo, baseado no uso de pilha, para resolver
  o seguinte problema.  Dada uma frase, a saída do algoritmo deve ser a mesma
  seqüência de palavras, mas com suas letras em ordem inversa.
    
  Por exemplo, com a entrada \textup{ESTE EXERCICIO E MUITO FACIL}, seu
  algoritmo deve ter como saída \textup{ETSE OICICREXE E OTIUM LICAF}.  Se
  você quiser, você pode supor que a frase de entrada contém apenas letras
  maiúsculas e brancos, e que o último caracter é um branco.
  
  Escreva sua solução na forma de pseudocódigo (isto é, não é necessário
  escrever em C).  A estrutura geral de sua solução deve ser como segue

{\singlespace
\begin{pseudocode}{Inverta\_Palavras$(s)$}

\ts1. \dots

\ts2. \textbf{enquanto} há caracteres para ler

\ts3. \x $c =$ próximo caracter de~$s$

\ts4. \x \dots

\end{pseudocode}
}
 
  \medskip  
\item{}[4 pontos] Nesta e na próxima questão, você deve escrever código em C.
  Ademais, supomos que temos
\begin{verbatim}
  typedef struct node *link;
  struct node { int item; link next; };
\end{verbatim}
  Escreva uma função de protótipo
\begin{verbatim}
  link elimine(link h, int x); 
\end{verbatim}
  que recebe como entrada um ponteiro para a cabeça de lista \verb|heada| de
  uma lista ligada e que devolve a mesma lista sem as células com
  item~\verb|x|.  A função deve devolver um ponteiro para \verb|heada|; a
  memória ocupada pelas células eliminadas da lista (aquelas com
  item~\verb|x|) deve ser liberada.  Você deve supor que as listas não têm
  cauda (em particular, se a lista dada está vazia, temos %
  \verb|h-&gt;next == NULL|).
  
  O que ocorreria se tivéssemos listas ligadas sem cabeça nesta questão?

  \medskip  
\item{}[2 pontos] Escreva uma função de protótipo
\begin{verbatim}
  link remova(link a, link b); 
\end{verbatim}
  que recebe como entrada ponteiros para as cabeças de lista \verb|heada| e
  \verb|headb| de duas listas ligadas e que remove da lista~\verb|a| as
  células com itens que ocorrem na lista~\verb|b|.  A função deve devolver um
  ponteiro para \verb|heada|; sua função deve manter a ordem relativa das
  células que não foram eliminadas e deve manter a lista~\verb|b| intacta. 
  
  Por exemplo, se a lista~\verb|a| tem~$10$ células, com
  itens $3,1,4,1,5,9,2,5,3,5$ respectivamente e~\verb|b| tem~$3$ células, com
  itens $2,7,1$ respectivamente, então a saída deve ter~$7$ células, com itens
  $3,4,5,9,5,3,5$.

  Use a função \verb|elimine()| da questão anterior, mesmo que você não a
  tenha feito.

\end{enumerate}  
 
\end{document}

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

</pre></body></html>