%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Time-stamp: <Monday 30 Oct 2006 11:49:30am ESADT yoshi@RANDOM>   
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\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]{Segunda 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{}[4 pontos] Nesta questão, supomos que temos
\begin{verbatim}
  typedef struct node *link;
  struct node { int item; link next; };
\end{verbatim}
  Ademais, supomos que nossas listas não tem cabeça nem cauda.  Considere a
  função recursiva
\begin{verbatim}
link delete(link x, int v)
  { if (x == NULL) return NULL;
    if (x->item == v)) { link t = x->next; free(x); return delete(t, v); }
    x->next = delete(x->next, v);
    return x;
  }
\end{verbatim}
  \begin{enumerate}
  \item[(\textit{i})] Suponha que \verb|x| aponta para a primeira célula de
    uma lista cujas células contêm os inteiros $22,77,11,88,22,88,11$, nesta
    ordem.  Diga exatamente o efeito da chamada \verb|x = delete(x, 11)| (não
    é necessário ``simular'' a execução da função; basta você descrever o
    resultado precisamente), mas justifique como você chegou em sua resposta. 
    
  \item[(\textit{ii})] Escreva uma função \textbf{recursiva} que remove a
    \textbf{última} célula com item~\verb|v| (se existe tal célula; se não
    existe, sua função deve devolver a lista inalterada).  Sua solução deve
    ter tempo de execução~$O(n)$ para listas com~$n$ células.  Você pode
    escrever uma função de protótipo
\begin{verbatim}
  link delete(link x, int v)
\end{verbatim}
    que chama a função recursiva \verb|deleteR()|, com protótipo adequado para
    implementar a recursão.
    
  \item[(\textit{iii})] Escreva uma função recursiva de protótipo 
\begin{verbatim}
  int count(link x, int v)
\end{verbatim}
    que, ao ser chamado com \verb|x| apontando para a primeira célula de uma
    lista ligada e \verb|v| um inteiro, devolve o número de células na
    lista que tem item igual a~\verb|v|.

  \end{enumerate}

  \newpage
\item{}[4 pontos] Considere a seguinte implementação do quicksort, de
  Kernighan e Pike (``The Practice of Programming'', Addison Wesley Longman,
  1999):
\begin{verbatim}
void swap(int v[], int i, int j)
{ int temp = v[i]; v[i] = v[j]; v[j] = temp; }

void quicksort(int v[], int n)
{   int i, last;
    if (n <= 1) return; /* nothing to do */
    last = 0;
    for (i = 1; i < n; i++)
        if (v[i] < v[0])                   /* v[0] is the pivot */
            swap(v, ++last, i);
    swap(v, 0, last);                      /* restore pivot */
    quicksort(v, last);                    /* recursively sort */
    quicksort(v + last + 1, n - last - 1); /* each part */
}
\end{verbatim}
Lembre-se também do \verb|partition()| que conhecemos:
\begin{verbatim}
int partition(int a[], int l, int r)
  { int i = l-1, j = r; int v = a[r];
    for (;;) { 
        while (a[++i] < v) ;
        while (v < a[--j]) if (j == l) break;
        if (i >= j) break;
        exch(a[i], a[j]);
      }
    exch(a[i], a[r]);
    return i;
  }
\end{verbatim}

  \begin{enumerate}
  \item[(\textit{i})] Note que o algoritmo de partição de Kernighan e Pike é
    diferente do algoritmo em \verb|partition()|.  Dê uma entrada para a qual
    o algoritmo de Kernighan e Pike escreve valores no vetor~\verb|v| pelo
    menos~$2n$ vezes para particionar um vetor com~$n$ itens (note que
    \verb|swap()| escreve duas vezes em~\verb|v|).
    
  \item[(\textit{ii})] Dê uma cota superior para o número de vezes que
    \verb|partition()| escreve valores no vetor sendo particionado~\verb|a|. 

    
  \item[(\textit{iii})] Sejam~$C_1(n)$ e~$C_2(n)$ o número de comparações
    entre itens que fazem os dois algoritmos de partição acima, para vetores
    com~$n$ entradas.  Dê boas cotas superiores para~$C_1(n)$ e~$C_2(n)$.
    
%  \item[(\textit{iv})] O que você pode concluir de~(\textit{i}), (\textit{ii})
%    e~(\textit{iii})?

  \end{enumerate}

  \newpage
\item{}[4 pontos] Considere o algoritmo de intercalação visto em sala abaixo. 
\begin{verbatim}
Item aux[maxN];
void merge(Item a[], int l, int m, int r)
  { int i, j, k;
    for (i = m+1; i > l; i--) aux[i-1] = a[i-1];
    for (j = m; j < r; j++) aux[r+m-j] = a[j+1];
    for (k = l; k <= r; k++)
       if (less(aux[i], aux[j])) 
          a[k] = aux[i++];
       else
          a[k] = aux[j--];
  }
\end{verbatim}
  \begin{enumerate}
  \item[(\textit{i})] Seja~$N=r-l+1$.  Quantas comparações %
    \verb|less(aux[i], aux[j])| são feitas em uma chamada de %
    \verb|merge(a, l, m, r)|?
    
  \item[(\textit{ii})] Seja~$C(N)$ o número de comparações feitas por
    mergesort para ordenar um vetor com~$N$ elementos.  Prove então que 
    \begin{equation}
      \label{eq:mergosrt.1}
      C(1)=0
    \end{equation}
    e
    \begin{equation}
      \label{eq:mergosrt.2}
      C(N)=C(\lfloor N/2\rfloor)+C(\lceil N/2\rceil)+N\quad\text{para~$N>1$}. 
    \end{equation}

  \item[(\textit{iii})] Faça uma tabela para~$C(N)$ para valores pequenos
    de~$N$. 
    
  \item[(\textit{iv})] Podemos provar que
    \begin{equation}
      \label{eq:mergesort.3}
      C(N)=N\lceil\log_2N\rceil+N-2^{\lceil\log_2N\rceil}.
    \end{equation}
    Em vez de provar~\eqref{eq:mergesort.3} em geral, prove que esta fórmula
    vale se~$N=2^k$ para um inteiro~$k\geq0$.  \sugestao{Use indução em~$k$.}
    
\end{enumerate}


\end{enumerate}  
 
\end{document}

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