\documentclass[10pt]{article}

%% Escrevendo em português:
\usepackage[brazil]{babel}
\usepackage[latin1]{inputenc}

\pagestyle{empty}
\setlength{\textwidth}{18cm}
\setlength{\textheight}{23.5cm}
\setlength{\oddsidemargin}{-8mm}
\setlength{\topmargin}{-20mm}

\newcommand{\N}{\mbox{{\bf N}}}
\newcommand{\Z}{\mbox{{\bf Z}}}
\newcommand{\R}{\mbox{{\bf R}}}
\newcommand{\sse}{\Longleftrightarrow}
\newcommand{\floor}[1]{\lfloor{#1}\rfloor}
\newcommand{\ceil} [1]{\lceil{#1}\rceil}


\def\risonho{{$\bigcirc\!\!\!\!\!\lower.02cm\hbox{\vbox{\offinterlineskip\hbox{$\>\!..$}\vskip.07cm\hbox{$\scriptscriptstyle\smile$}}}$}}
\def\tristonho{{$\bigcirc\!\!\!\!\!\lower.02cm\hbox{\vbox{\offinterlineskip\hbox{$\>\!..$}\vskip.07cm\hbox{$\scriptscriptstyle\frown$}}}$}}

\begin{document}

\begin{center}
{\large
{\bf 
MAC 5711 - Análise de Algoritmos \\
}
}
{\em Departamento de Ciência da Computação} \\
Segundo semestre de 2002 \\

\vspace{2mm}
{\large
{\bf Lista 3} 
}

\vspace{1mm}
Devolução dos exercícios 3, 6, 7, 8 e 9: 9 de setembro de 2002
\end{center}

\begin{enumerate}
  
\item Mostre uma implementação do procedimento {\bf Intercala} do
  MergeSort que execute em tempo $\Theta(n)$. Argumente que de fato a
  sua implementação funciona em tempo $\Theta(n)$.

\item Considere uma função $f(n)$ que satisfaz a seguinte recorrência:
\[ f(n) =  \left\{ \begin{array}{ll}
                     c_1                              & \mbox{se $n \leq n_0$} \\
                     2f(\floor{\frac{n}{2}}) + c_2\,n & \mbox{se $n>n_0$}
                   \end{array} \right.
\]
Prove que $f(n) = \Theta(n \log n)$.  

\item Considere uma função $f(n)$ que satisfaz a seguinte recorrência:
\[ f(n) =  \left\{ \begin{array}{ll}
                     1                          & \mbox{se $n=1$} \\
                     2f(\floor{\frac{n}{2}}) + n \log n & \mbox{se $n>1$}
                   \end{array} \right.
\]
Resolva a recorrência acima, determinando qual é o comportamento assintótico
de $f(n)$ (ou seja, conclua que $f(n) = \Theta(g(n))$, para alguma função
$g(n)$ o mais simples possível). Ao resolver a recorrência, pode considerar
apenas o caso em que $n = 2^m$.

\item Mostre que \\
{\bf a)} $\floor{\log n} = \ceil{\log(n+1) - 1}$ \hspace{2cm} \\
{\bf b)} $\log (n!) = \Omega(n \log n)$ \hspace{3mm} ({\bf Dica:} Use a
fórmula de Stirling.) \\
{\bf c)} Usando o mesmo raciocínio, é possível mostrar que 
$n! = \Omega(2^{n \log n})$? \\
{\bf d)} Se $f(n) = \Omega(g(n))$, é verdade que $2^{f(n)} =
\Omega(2^{g(n)})$? É verdade que $\log f(n) = \Omega(\log g(n))$?

\item Resolva completamente (método de substituição e prova por indução) a
  seguinte recorrência: 
\[ f(n) =  \left\{ \begin{array}{ll}
               \Theta(1)                             & \mbox{se $n=1$} \\
               f(\floor{\frac{2}{3}n}) + f(\ceil{\frac{n}{3}}) + \Theta(n) 
                                                     & \mbox{se $n>1$}
                   \end{array} \right.
\]

\item Prove (por indução em $h$) que toda árvore binária de altura $h$
  tem no máximo $2^h$ folhas. 
  
\item Considere um vetor $V$ com $n$ elementos distintos. Prove que o seguinte
  processo gera uma permutação de $V[1], \ldots, V[n]$ com distribuição de
  probabilidade uniforme (ou seja, cada permutação é gerada com probabilidade
  $1/n!$). ({\bf Dica:} Use indução em n.)

\vspace{-2mm}
\begin{verbatim}
enquanto n > 1 faça 
  r := inteiro aleatório entre 1 e n (ditribuição uniforme)
  troque V[r] com V[n]
  n := n-1
\end{verbatim}
\vspace{-2mm}

\item Escreva uma função que receba um vetor $V[1..n]$ de inteiros e
  rearranje o vetor de modo que, para algum $j$ em $1..n$, tenhamos 
$$ V[i] \leq 0, \mbox{\ para todo $i \leq j$ \ e \ } 
   V[i] \geq 0, \mbox{\ para todo $i > j$.} $$
  Não use vetor auxiliar. A sua função deve executar em tempo $\Theta(n)$. 
  Explique o funcionamento da sua função (sem uma explicação razoável,
  escrita em bom português, sua resposta nem será considerada,
   portanto capriche) e argumente que ela de fato executa em tempo
   $\Theta(n)$.

\item Você tem que escrever um programa que tem como entrada dois
  inteiros $n$ e $m$ e duas listas de números distintos. A primeira
  lista tem $n$ números distintos e a segunda tem $m$ números. A cada
  leitura de um número da segunda lista, seu programa deve imprimir se
  este pertence ou não a primeira lista.

  Você pode escolher entre as seguintes opções: \\
  {\bf a)} fazer uma busca linear a cada leitura. \\
  {\bf b)} ordenar a primeira lista e fazer busca binária a cada leitura; \\
  Supondo que $m = \floor{\log \log n}$, qual dos métodos é mais eficiente? E
  qual é mais eficiente se $m = \floor{\sqrt{n}}$? Justifique suas respostas.

\end{enumerate}

\end{document}

