%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Arquivo TeX para                                                   %
%                                                                    %
% Prova 1 de MAC338 Análise de Algoritmos                            %
% BCC, 1o. semestre de 2000                                          %
% Y. Kohayakawa                                                      %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Time-stamp: <Tuesday 25 Apr 2000 03:36:00pm 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 1\hfill\sl25/4/2000}
\bigskip

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

% \medskip
% \noindent{\bf Obs.}\enspace 
% Nos exercícios com listas ligadas, vamos assumir que temos
% \begintt
%   typedef struct node *link;
%   struct node { Item item; link next; };
% \endtt
% Ademais, nos exercícios com árvores binárias, vamos assumir que temos
% \begintt
%   typedef struct Tnode *link;
%   struct Tnode { Item item; link l, r; };
% \endtt
% O tipo {\tt Item} depende de cada questão.
% Fortemente sugiro que você faça de 3 a 4 questões.

\medskip
\noindent{\bf 1.} [3 pontos]\enspace
Temos usado a notação~$O$ em sala regularmente.  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\/})}É correto dizer que~$n\log n=O(n^2)$?
\itemitem{({\it ii\/})}Suponha que deduzimos que a complexidade de
tempo de dois algoritmos~$A$ e~$B$ são, respectivamente, $O(n\log
n)$~e~$O(n^2)$, para entradas de tamanho~$n$.  É correto dizer que o
algoritmo~$A$ é pelo menos tão eficiente quanto o algoritmo~$B$ para entradas   
suficientemente grandes?  Justifique sua resposta.  [{\sl Sugestão\/}:
cuidado!] 
\itemitem{({\it iii\/})}O que é mais informativo: dizer que a
complexidade de tempo de um algoritmo é~$O\big(n(\log n)^3\big)$
ou dizer que é~$O(n^2)$?  Justifique sua resposta.

\def\bfx{{\bf x}}
\def\bfy{{\bf y}}
\medskip
\noindent{\bf 2.} [3 pontos]\enspace
Nesta questão, consideramos dois grafos orientados~$G_1$ e~$G_2$.  Fixe dois
inteiros~$k\geq2$ e~$n\geq1$.  Ambos~$G_1$ e~$G_2$ têm conjunto de
vértices~$V=[k]^n=[k]\times\cdots\times[k]$, onde~$[k]=\{1,\dots,k\}$.
Em~$G_1$, temos um arco de~$\bfx=(x_1,\dots,x_n)$ para~$\bfy=(y_1,\dots,y_n)$
se ({\it a\/})~$x_i\leq y_i$ para todo~$i$ e ({\it
  b\/})~$\sum_iy_i=1+\sum_ix_i$, isto é, todas as coordenadas de~$\bfy$ são
as mesmas de~$\bfx$ exceto por uma, que é exatamente um maior que a coordenada
correspondente de~$\bfx$.  Em~$G_2$, temos um arco de~$\bfx=(x_1,\dots,x_n)$
para~$\bfy=(y_1,\dots,y_n)$ se ({\it a\/})~$\bfx\neq\bfy$ e~({\it
  b\/})~$x_i\leq y_i$ para todo~$i$.  

\itemitem{({\it i\/})}Desenhe os grafos~$G_1$ e~$G_2$ no caso em que~$k=2$
e~$n=3$.  Note que estes grafos têm~$2^3=8$ vértices.  Ademais, eles têm~$12$
arcos e~$19$ arcos, respectivamente.  

\itemitem{({\it ii\/})}Em geral, mostre que~$G_1$ tem no máximo~$nk^n$ arcos 
e~$G_2$ tem exatamente
$$
\left\{{k\choose1}+{k\choose2}\right\}^n-k^n
={k+1\choose2}^n-k^n\eqno\hbox{(*)}
$$
arcos.  [{\sl Sugestão\/}: a grosso modo, cada arco~$(\bfx,\bfy)$ em~$G_2$
pode ser codificado como um vetor com~$n$ coordenadas, cada coordenada
assumindo um dentre $k+{k\choose2}$ valores.]  

\itemitem{({\it iii\/})}Mostre que a quantidade em~(*) é pelo menos
$$
{1\over3}{k+1\choose2}^n.
$$

\itemitem{({\it iv\/})}Mostre que~$G_1$ e~$G_2$ têm o mesmo conjunto de
ordenações topológicas.

\itemitem{({\it v\/})}Suponha que o algoritmo $\hbox{\sc Topological-Sort}$
que estudamos em sala demora~$N+M$ unidades de tempo para encontrar uma
ordenação topológica de um grafo orientado acíclico com~$N$ vértices e~$M$
arcos.  O que podemos dizer sobre o tempo de execução de $\hbox{\sc
  Topological-Sort}(G_1)$ e $\hbox{\sc Topological-Sort}(G_2)$?  Suponha agora
que~$k=2$ e~$n$ é grande.  Como você pode comparar estes dois tempos de
execução?  Dê um valor de~$n$ para o qual um tempo é pelo menos~$10$ vezes
maior que o outro.  Faça o mesmo para~$1000$.

\medskip
\noindent{\bf 3.} [3 pontos]\enspace
Faça uma tabela $3\times3$ com as linhas e colunas indexadas pelas
cores branca, cinza e preta.  Na entrada $(i,j)$ desta tabela,
indique se é possível acontecer de termos um arco de um vértice de
cor~$i$ para um vértice de cor~$j$ em uma execução de
$\hbox{\sc DFS}(G)$ para um grafo orientado~$G$.  Responda a mesma
pergunta para o caso em que~$G$ é um grafo não-orientado.  {\sl
No caso das entradas negativas, justique sua resposta.\/}

\medskip
\noindent{\bf 4.} [3 pontos]\enspace
Suponha que~$(u,v)$ é um arco de um grafo orientado~$G$ e que
executamos~$\hbox{\sc DFS}(G)$.  Por simplicidade, suponha que~$G$ não tem
laços, isto é, arcos da forma~$(u,u)$.  Mostre que~$(u,v)$ é

  \itemitem{({\it i\/})}um arco da floresta de busca ou um arco longitudinal
    descendente se e só se $d[u]<d[v]<f[v]<f[u]$,
  \itemitem{({\it ii\/})}um arco longitudinal ascendente se e só se
    $d[v]<d[u]<f[u]<f[v]$, e
  \itemitem{({\it iii\/})}um arco transversal se e só se
    $d[v]<f[v]<d[u]<f[u]$. 

\noindent Ademais, se~$x$ e~$y$ são vértices quaisquer de~$G$, 

  \itemitem{({\it iv\/})}o que podemos dizer sobre a paridade de
    $f[x]-d[x]$?  Justifique.
  \itemitem{({\it v\/})}Podemos ter $d[x]<d[y]<f[x]<f[y]$?
    Justifique. 

% \medskip
% \noindent{\bf 4.} [3 pontos]\enspace
% O algoritmo visto em sala para determinar os componentes fortemente
% conexos de uma grafo orientado descobre estes componentes em uma certa ordem
% bem definida.  Intuitivamente, podemos dizer que o algoritmo `descobre' os
% vértices do grafo~$G'$ do exercício anterior em uma certa ordem.  O que
% podemos dizer sobre esta ordem em relação ao grafo~$G'$?  Especificamente, é
% 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.  

\bye
