%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Arquivo TeX para                                                   %
%                                                                    %
% Prova Rec de MAC338 Análise de Algoritmos                          %
% BCC, 1o. semestre de 2000                                          %
% Y. Kohayakawa                                                      %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Time-stamp: <Monday 28 Aug 2000 08:22:50am BRT yoshi@rebutosa>   
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\input acentos
\hyphenpenalty=500
\tolerance=500
\overfullrule=0pt
\nopagenumbers
\font\sc=cmcsc10

\catcode`@=11 % borrow the private macros of PLAIN (with care)
% (now Appendix E resumes again)
% macros for verbatim scanning
\chardef\other=12
\def\ttverbatim{\begingroup
  \catcode`\\=\other
  \catcode`\{=\other
  \catcode`\}=\other
  \catcode`\$=\other
  \catcode`\&=\other
  \catcode`\#=\other
  \catcode`\%=\other
  \catcode`\~=\other
  \catcode`\_=\other
  \catcode`\^=\other
  \obeyspaces \obeylines \tt}

\outer\def\begintt{$$\let\par=\endgraf \ttverbatim \parskip=\z@
  \catcode`\|=0 \rightskip-5pc \ttfinish}
{\catcode`\|=0 |catcode`|\=\other % | is temporary escape character
  |obeylines % end of line is active
  |obeyspaces|global|let =| % spaces are active
  |gdef|ttfinish#1^^M#2\endtt{#1|vbox{#2}|endgroup$$}}

\centerline{MAC338\hfill\bf PROVA REC\hfill\sl21/8/2000}
\bigskip

\medskip
\noindent{{\sl Duração da prova\/}: 2 horas e 30 minutos}

\def\({\left(}
\def\){\right)}  
\let\:=\colon
\let\sim=\thicksim
\def\<{\langle}
\def\>{\rangle}
\let\epsilon=\varepsilon
\let\rho=\varrho

\medskip
\noindent{\bf 1.} [2 pontos]\enspace
Lembre que podemos
escrever~$O(f(n))$ no lugar de qualquer função~$g(n)$ para a qual
existam~$C>0$ e~$n_0\geq1$ tais que
$$
|g(n)|\leq Cf(n)\qquad\hbox{para todo~$n\geq n_0$.}
$$
\itemitem{({\it i\/})} Considere as funções~$f(n)=(\log
n)^A$ e~$g(n)=n^\epsilon$.  Em quais casos (em termos dos valores de~$\epsilon$ e~$A$), 
temos~$g(n)=O(f(n))$?  Justifique sua resposta. 
\itemitem{({\it ii\/})} Determine uma condição necessária e suficiente para
as triplas~$(\alpha_1,\alpha_2,\alpha_3)$ e~$(\beta_1,\beta_2,\beta_3)$ para
que tenhamos $n^{\alpha_1}(\log n)^{\alpha_2}(\log\log
n)^{\alpha_3}=O\((n^{\beta_1}(\log n)^{\beta_2}(\log\log n)^{\beta_3}\))$.
Neste item, você deve enunciar a condição claramente.

\itemitem{({\it iii\/})} Justifique sua resposta ao item~({\it ii\/}) acima.

\medskip
\noindent{\bf 2.} [3 pontos]\enspace
Seja~$G$ um grafo orientado.  Defina o grafo~$G'=(V',E')$ como sendo o
seguinte grafo orientado: $V'$~é o conjunto dos componentes fortemente conexos
de~$G$.  Formalmente,
$$
  V'=\{[x]\:x\in V\},
$$
%
onde~$[x]$ denota o componente fortemente conexo de~$x$ em~$G$.  O
arco~$([x],[y])$ existe em~$G'$ se e só se existe um arco~$(x',y')\in E(G)$
com~$x'\in[x]$ e~$y'\in[y]$.
  
\itemitem{({\it i\/})}Mostre que~$G'$ é necessariamente um grafo orientado
acíclico, isto é, não contém circuitos orientados.

\itemitem{({\it ii\/})}Descreva o algoritmo de Kosaraju e Sharir, visto
durante o semestre, para determinar os componentes fortemente conexos de um
grafo orientado.

\itemitem{({\it iii\/})}Com base em sua resposta ao item~({\it ii\/}) acima,
deduza em que ordem o algoritmo descobre os componentes fortemente conexos do
grafo dado.  Intuitivamente, podemos dizer que o algoritmo `descobre' os
vértices do grafo~$G'$ do item~({\it i\/}) em uma certa ordem.  É verdade que
estes vértices são descobertos em uma ordem topológica de~$G'$?  (As fontes
são descobertas primeiro, depois os vértices `intermediários', e por fim os
sorvedouros.)  Justifique sua resposta.

\medskip
\noindent{\bf 3.} [2 pontos]\enspace
Podemos representar a estrutura das chamadas recursivas do mergesort através
de uma árvore binária, que é ``quase balanceada''.  Seja~$h(n)$ a altura desta
árvore quando a entrada tem~$n$ elementos.  Ademais, seja~$k(n)$ a profundidade
mínima de uma folha em tal árvore.  Mostre que temos, para todo~$n>0$,
\itemitem{({\it i\/})}$h(n)=\lceil\log_2n\rceil$,  
\itemitem{({\it ii\/})}$k(n)=\lfloor\log_2n\rfloor$.  
\itemitem{({\it iii\/})}Deduza que esta árvore é balanceada se~$n$ é uma
potência de~$2$.

\medskip
\noindent{\bf 4.} [3 pontos]\enspace
Considere a seguinte função de partição de Kernighan e Pike, dado no livro
{\it The Practice of Programming}. 
\begintt
int partition(Item a[], int l, int r)
  { int i, last; Item v = a[r];
    last = r;
    for (i=r-1; i>=l; i--) {
      if (less(v, a[i]))
        { --last; exch(a[i], a[last]); }
    }
    exch(a[last], a[r]);
    return last;
  }
\endtt

\noindent Nesta questão, você deve supor que {\tt a[]} contém os
elementos~$\{0,\dots,n-1\}$, em alguma ordem.

\itemitem{({\it i\/})} Quantas vezes a troca {\tt exch(a[i], a[last])} é
executada quando~${\tt a[r]}=k$?

\itemitem{({\it ii\/})} Suponha agora que a entrada {\tt a[]} contém uma
permutação de $\{0,\dots,n-1\}$, com todas as permutações equiprováveis.
Mostre que o número esperado de trocas {\tt exch(a[i], a[last])} que serão
executadas é~$(n-1)/2$.

\noindent
Considere agora a função de partição de Sedgewick abaixo.
\begintt
int partition(Item a[], int l, int r)
  { int i = l-1, j = r; Item v = a[r];
    for (;;)
      { while (less(a[++i], v)) ;
        while (less(v, a[--j])) if (j == l) break;
        if (i >= j) break;
        exch(a[i], a[j]);
      }
    exch(a[i], a[r]);
    return i;
  }
\endtt

\itemitem{({\it i\/})} Qual é o número total de comparaçãos que fazemos dos
elementos de {\tt a[]} com {\tt v}?  (Isto é, número de comparações {\tt
less(a[++i], v)} mais o número de comparações {\tt less(v, a[--j])}.)

\itemitem{({\it ii\/})} Suponha agora que ${\tt a[r]}=k$.  Seja~$q$ o
número índices~$i$ ($0\leq i<k$) para os quais temos ${\tt a[{\it i\/}]}\geq
k$.  Quantas vezes executamos a troca {\tt exch(a[i], a[j])}?

\itemitem{({\it iii\/})} Suponha agora que a entrada {\tt a[]} contém uma
permutação de $\{0,\dots,n-1\}$, com todas as permutações equiprováveis.  Qual
é o valor esperado de~$q$ do item~({\it ii\/}), {\it supondo que ${\tt
a[r]}=k$\/}? 

\itemitem{({\it iv\/})} Determine o número esperado de execuções da troca {\tt
exch(a[i], a[j])}, supondo novamente que a entrada {\tt a[]} contém uma
permutação de $\{0,\dots,n-1\}$, com todas as permutações equiprováveis.

\bye



