%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Time-stamp: <Monday 25 Sep 2006 10:06:42am BRT 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\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\\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{}[2 pontos] Diga se são verdadeiras ou falsas as seguintes fórmulas:
  \begin{itemize}
  \item[(\textit{i})] $1+2+\dots+n=\sum_{1\leq k\leq n}k=O(n^2)$ 
  \item[(\textit{ii})] $1^5+2^5+\dots+n^5=\sum_{1\leq k\leq n}k^5=O(n^6)$ 
  \item[(\textit{iii})] $1+2+2^2+\dots+2^n=\sum_{0\leq k\leq n}2^k=O(2^n)$  
  \item[(\textit{iv})] $2^{S_n}=O(2^{2^n})$, onde~$S_n=\sum_{0\leq k\leq
      n}2^k$ é como em~(\textit{iii})
  \end{itemize}
  Procure justificar 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<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<i$)).

  \begin{itemize}
  \item[(\textit{i})] Suponha que a entrada é 
    $$
    (3,4), (4,9), (8,0), (2,3), (5,6), (5,9), (7,3), (4,8), (6,1).
    $$
    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 a solução que vimos para este problema que
    consome tempo~$O(M\log N)$.  Não é necessário escrever o código C
    correspondente a sua solução, bastando descrever a estrutura de dados e os
    algoritmos usados (mas faça isso de forma bem precisa).
    
  \item[(\textit{iii})] Por que esta solução consome tempo~$O(M\log N)$?
    Argumente da forma mais precisa que você conseguir.

  \end{itemize}

  \medskip  
\item{}[3 pontos] Escreva um algoritmo para resolver o seguinte problema.
  Dada uma cadeia de caracteres, determinar o número de ocorrências de
  \textit{números naturais} na cadeia.
  
  Um número natural deve ser entendido como uma cadeia não-vazia maximal de
  dígitos, sem sinal.  Isto é, um número natural é uma cadeia não-vazia de
  dígitos (\verb|'0'..'9'|) que não pode ser estendida nem à esquerda nem à
  direita.  Por exemplo, com a entrada
  $$
  \text{Pergunte-me 123 e responderei 456.  Tão simples como 789 só 10.}
  $$
  seu algoritmo deve devolver~$4$.
  
  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}{Numero\_de\_naturais$(s)$}

\ts1. \dots

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

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

\ts4. \x \dots

\ts5. \textbf{devolva} cont
\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 elem_max(link h); 
\end{verbatim}
  que recebe como entrada um ponteiro para a cabeça de lista \verb|heada| de
  uma lista, e devolve (um ponteiro para) uma célula desta lista que tem campo
  \verb|item| máximo.  Ademais, a célula que é devolvida por \verb|elem_max()|
  deve ser removida da lista dada.  Supomos que temos uma cabeça de lista mas
  não temos cauda em nossa lista.  Se a lista dada for vazia (isto é, se
  \verb|h->next == NULL|), a função deve devolver \verb|NULL|.

  O que ocorreria se não tivéssemos cabeça de lista nesta questão?
  
  \medskip  
\item{}[2 pontos] Escreva uma função de protótipo
\begin{verbatim}
  link ordene(link h); 
\end{verbatim}
  que recebe como entrada um ponteiro para a cabeça de lista \verb|heada| de
  uma lista, e devolve um ponteiro para uma nova lista constituída pelas
  células na lista original, mas em ordem não-decrescente.  A lista que você
  criar deve ter uma cabeça de lista.  Use a função \verb|elem_max()| 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: