%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Arquivo TeX para                                                   %
%                                                                    %
% Prova 2 de MAC338 Análise de Algoritmos                            %
% BCC, 1o. semestre de 2000                                          %
% Y. Kohayakawa                                                      %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Time-stamp: <Tuesday 04 Jul 2000 09:47:18am BRT yoshi@jaca>   
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\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 3\hfill\sl4/7/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.

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

\medskip
\noindent{\bf 1.} [3 pontos]\enspace
\itemitem{({\it i\/})} Prove que $n^\alpha=O(n^\beta)$ se e só
se~$\alpha\leq\beta$. 

\itemitem{({\it ii\/})} Determine uma condição necessária e suficiente para
os pares~$(\alpha_1, \alpha_2)$ e~$(\beta_1, \beta_2)$ para que tenhamos
$n^{\alpha_1}(\log n)^{\alpha_2}=O\((n^{\beta_1}(\log n)^{\beta_2}\))$. 

\itemitem{({\it iii\/})} Sabe-se que o $k$-ésimo primo~$p_k$ é tal que
$p_k=\Theta(k\log k)$.  Seja~$\pi(n)$ o número de números primos~$p$
com~$1<p\leq n$.   Deduza que $\pi(n)=\Theta(n/\log n)$.

\medskip
\noindent{\bf 2.} [3 pontos]\enspace
O {\it Problema da Seleção\/} $s(n,k,{\bf x})$ tem como entrada inteiros
$1\leq k\leq n$ e uma seqüência de inteiros ${\bf x}=(x_1,\dots,x_n)$.   Neste
problema, queremos encontrar um~$x$ tal que
$$
\big|\{i\: x_i\leq x\}\big|\geq k
\quad\hbox{ e }\quad
\big|\{i\: x_i\geq x\}\big|\geq n-k+1.
$$
Por exemplo, o problema $s(n,1,{\bf x})$ consiste na determinação do menor
elemento em~$\bf x$ e o problema $s(n,\lfloor n/2\rfloor,{\bf x})$ consiste na
determinação da mediana dos elementos em~$\bf x$.

\itemitem{({\it i\/})} Descreva um algoritmo para resolver $s(n,k,{\bf x})$.
O seu algoritmo deve ter complexidade de pior caso~$O(n\log n)$.

\itemitem{({\it ii\/})} Suponha agora que os inteiros que ocorrem em~$\bf x$
são todos distintos e que formam um conjunto (desconhecido)~$X$.  Suponha que
queremos resolver~$s(n,k,{\bf x})$, onde~$\bf x$ é uma dentre todas as~$n!$
possíveis permutações de~$X$, com todas estas permutações equiprováveis.
Descreva um algoritmo para resolver $s(n,k,{\bf x})$ nestas condições que tem
complexidade de caso médio~$O(n)$.

\itemitem{({\it iii\/})} Argumente que o seu algoritmo em~({\it ii\/}) de fato
tem complexidade de caso médio~$O(n)$.  Para sua resposta estar completa, você
precisa fazer uma análise quantitativa de seu algoritmo.

\medskip
\noindent{\bf 3.} [3 pontos]\enspace
Nesta questão, estamos interessados em grafos orientados~$G$.  Suponha que
represetamos nossos grafos por matrizes de adjacência~$A(G)=(a_{ij})$, onde
colocamos~$a_{ij}=1$ se o arco~$(i,j)$ está presente em~$G$ e~$a_{ij}=0$ caso 
contrário.  Considere agora o seguinte trecho de código:
\begintt
for (y = 0; y < n; y++)
  for (x = 0; x < n; x++)
    if (a[x][y])
      for (j = 0; j < n; j++)
        if (a[y][j]) a[x][j] = 1;
\endtt
(Os vértices de~$G$ são~$0,\dots,n-1$.)
\itemitem{({\it i\/})} Dê um limitante superior para o número de vezes que a
atribuição {\tt a[x][j]=1;} é executada.

\itemitem{({\it ii\/})} Descreva o efeito do trecho de código acima (para
tanto, você poderia considerar o grafo que a nova matriz representa.)

\medskip
\noindent{\bf 4.} [3 pontos]\enspace
Considere a função abaixo, que é utilizada na manipulação de heaps.
\begintt
void fixDown(Item a[], int k, int N)
  { int j;
    while (2*k <= N)
      { j = 2*k;
        if (j < N && less(a[j], a[j+1])) j++;
        if (!less(a[k], a[j])) break;
        exch(a[k], a[j]); k = j;
      }
  }
\endtt
\itemitem{({\it i\/})} Em que situação usamos {\tt fixDown()}?  Descreva
cuidadosamente as hipóteses sobre o heap no momento em que chamamos esta função
e explicite qual é o efeito da execução de {\tt fixDown()}.

\itemitem{({\it ii\/})} O que se entende pela {\it altura\/} de um elemento em
uma árvore?  Não deixe de dar um exemplo ilustrativo.  Lembre-se de que
folhas têm altura~$0$.

\itemitem{({\it iii\/})} Dê um limitante superior para o número de vezes que
executamos {\tt exch()} em função da altura do elemento apontado por
{\tt k} no momento da chamada de {\tt fixDown()}.  

\itemitem{({\it iv\/})} Relacione o tempo de construção de um heap a partir de
um vetor arbitrário com~$n$ elementos com a soma das alturas dos nós da árvore
binária completa com~$n$ nós.

\itemitem{({\it v\/})} Seja~$f(n)$ a soma das alturas dos nós da árvore
binária completa com~$n$ nós.  Mostre que~$f(n)$ satisfaz a recorrência 
$f(1)=0$ e $f(n)=f(\lfloor n/2\rfloor)+\lfloor n/2\rfloor$ para~$n\geq2$. 

\itemitem{({\it vi\/})} Mostre que~$f(n)=n-b(n)$, onde~$b(n)$ é o número de
bits~$1$ na expansão binária de~$n$.  Deduza que podemos construir um heap a
partir de um vetor arbitrário com~$n$ elementos executando no máximo~$n$
trocas de elementos do vetor (execuções de {\tt exch()}).

\bye



