%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Arquivo LaTeX2e para                                               %
%                                                                    %
% Exercícios de Computação II, Ciências Moleculares                  %
% 1o. semestre de 2002                                               %
% Y. Kohayakawa                                                      %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Time-stamp: <Friday 21 Jun 2002 08:23:15am BRT yoshi@erdos.ime.usp.br>   
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\documentclass[11pt,reqno]{amsart}

\usepackage[colorlinks,backref]{hyperref}

%% Escrevendo em português:
\usepackage[brazil]{babel}
\usepackage[latin1]{inputenc} % isso é quase redundante
%----------------------------
\renewcommand{\datename}{\textit{Data}:}

\let\:=\colon
\let\epsilon=\varepsilon
\def\e{{\rm e}}
\def\dist{\mathop{\rm dist}\nolimits}
\def\RR{\mathbb R}
\def\NN{\mathbb N}
\def\ZZ{\mathbb Z}
\def\({\left(}
\def\){\right)}  
\def\<{\langle}
\def\>{\rangle}
%\let\sim=\thicksim

\def\inR{\mathrel{\in_{\text R}}} 

\def\cA{\mathcal A}
\def\cB{\mathcal B}
\def\cF{\mathcal F}
\def\cG{\mathcal G}
\def\cH{\mathcal H}
\def\cL{\mathcal L}
\def\cR{\mathcal R}

\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\EE{\mathop{\hbox{\raise.03ex\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}}

\makeatletter
\renewcommand{\labelenumi}{\theenumi.}
\makeatother

\def\datedue#1{$\{$\textsl{Data de entrega}: #1$\}$}

\begin{document}
\title[Computação II]{Exercícios de Computação II\\1{\tiny o.} semestre de 2002} 
\date{Versão de \today}
\maketitle

\begin{enumerate}
  \thispagestyle{empty}
  
\item Exercícios 6.5 e 6.6.\footnote{A menos de menção explícita em contrário,
    estes exercícios são do Sedgewick, Algorithms in~C, Partes
    1~a~4.} \datedue{5/4/2002} 
  
\item Exercícios 6.14, 6.18, e 6.22. \datedue{5/4/2002}

\item Exercício 8.1. \datedue{5/4/2002}

\item Suponha que executamos o Programa~6.2 (ordenação por seleção) sobre um
  vetor aleatório com~$n$ elementos.  Procure estabelecer uma estimativa para
  o número (médio) de vezes que a atribuição \texttt{min = j} é executada.
  (Você pode fazer isso experimentalmente.  Sugestão: considere a função
  $n\log n$, onde o logaritmo é na base~$e=2.718\dots$.) \datedue{12/4/2002}

\item Exercício 6.7 (veja a definição de algoritmo de ordenação
  \textit{estável} na Definição~6.1 de Sedgewick).  Você pode achar útil
  estudar a Seção~6.7 do Sedgewick. \datedue{12/4/2002}
  
\item Escreva um algoritmo que recebe como entrada um vetor de~$n$ elementos e
  um inteiro~$1\leq k\leq n$, e devolve o $k$-ésimo menor elemento do vetor.
  O seu algoritmo deve ser tal que, em média, ele leva tempo~$O(n)$ qualquer
  que seja o valor de~$k$.  Você não precisa provar formalmente esta
  propriedade de seu algoritmo, mas você deve apresentar um argumento
  intuitivo.  \datedue{9/4/2002}.

\item Suponha que alteramos o trecho de \texttt{prog7.1.c}
\begin{verbatim}
      while (scanf("%d", &a[N]) == 1) N++;
    }
    quicksort(a, 0, N-1);
    for (i = 0; i < N; i++) printf("%3d ", a[i]);
\end{verbatim}
para
\begin{verbatim}
      while (scanf("%d", &a[N]) == 1) N++;
    }
    quicksort(a, 0, N-1);
    quicksort(a, 0, N-1);
    for (i = 0; i < N; i++) printf("%3d ", a[i]);
\end{verbatim}
Ademais, suponha que alteramos o trecho de \texttt{prog7.4.c}
\begin{verbatim}
    }
    sort(a, 0, N-1);
    for (i = 0; i < N; i++) printf("%3d ", a[i]);
\end{verbatim}
para
\begin{verbatim}
    }
    sort(a, 0, N-1);
    sort(a, 0, N-1);
    for (i = 0; i < N; i++) printf("%3d ", a[i]);
\end{verbatim}
Sejam \texttt{prog7.1.b.c} e \texttt{prog7.4.b.c} os programas assim obtidos.
Execute estes programas para valores grandes de \texttt{N}, e meça os
respectivos tempos de execução.  Por que \texttt{prog7.1.b.c} é tão mais
demorado? \datedue{12/4/2002}

\item Dizemos que uma palavra~$s$ é um \textit{anagrama} de uma palavra~$t$
  se~$s$ pode ser obtida de~$t$ pela permutação de suas letras.  Por exemplo,
  as palavras \textit{triangle}, \textit{relating}, \textit{integral},
  \textit{altering}, e \textit{alerting} são todas anagramas umas das outras.
  Neste exercício, você é convidado a encontrar anagramas `interessantes' nas
  listas de palavras que você pode encontrar em
  \href{http://www.ime.usp.br/~yoshi/dicios}{\texttt{http://www.ime.usp.br/\textasciitilde
      yoshi/dicios}}.  Por exem\-plo, você pode procurar pares~$(s,t)$ de
  anagramas compridos (isto é, $s$~e~$t$ longos), você pode procurar conjuntos
  grandes de anagramas~$\{s_1,\dots,s_k\}$ (isto é, $k$~grande), etc.
  [\textit{Sugestão}.\quad Chame de \textit{assinatura} de uma palavra~$s$ a
  cadeia de caracteres que obtemos ao ordenar as letras em~$s$.  Por exemplo,
  a assinatura de `assinatura' é `aaainrsstu'.  Use este conceito.  Você
  também pode achar o utilitário \texttt{uniq} do Unix útil.]
  \datedue{26/4/2002}
  
\item Seja~$R(N)$ a soma das alturas dos nós de uma árvore binária completa
  com~$N$ nós.  Para um inteiro não-negativo~$N$, escrevermos~$b_1(N)$ para o
  números de bits~$1$ na representação de~$N$ na base~$2$.  Prove
  que~$R(N)=N-b_1(N)$.  Em particular, $R(N)\leq N$ para todo~$N$.
  \datedue{30/4/2002}

\item Explique porque podemos omitir o primeiro \texttt{if} e a primeira
  chamada recursiva na função \texttt{radixMSD()} (\texttt{prog10.2.c}) quando
  estamos ordenando \texttt{strings}.  \datedue{3/5/2002}
  
\item Escreva um programa como segue.  O seu programa deve receber na linha de
  comando dois inteiros, digamos~$M$ e~$N$, ambos~$\leq 10^9$, e deve devolver
  uma lista aleatória de~$N$ inteiros \textit{distintos}, todos não-negativos
  e menores que~$M$.  Você pode supor que o seu programa será usado para
  valores de~$M$ e~$N$ com~$N$ substancialmente menor que~$M$, digamos~$N\leq
  M/2$.  O seu programa deve executar em poucos minutos para~$M=10^9$
  e~$N=5\times10^8$. \datedue{7/5/02}
  
\item Escreva um módulo \texttt{radixL} (\texttt{radixL.c} e
  \texttt{radixL.h}) que pode ser usado para ordenar uma lista ligada com nós
  do tipo
\begin{verbatim}
  typedef struct node_struct {
    long key;
    struct node_struct *link;
  } node;
\end{verbatim}
  A linha
\begin{verbatim}
  lista = ordene(lista);
\end{verbatim}
  em um programa cliente deve ordenar os elementos da lista ligada cujo
  primeiro elemento é apontado por \texttt{lista}, em ordem crescente de seus
  campos \texttt{key}.  Use o LSD Radix Sort fornecido em
  \href{http://www.ime.usp.br/~yoshi/2002i/CompII/exx/LTSs/CWEB/}{\texttt{http://www.ime.usp.br/\textasciitilde
      yoshi/2002i/CompII/exx/LTSs/CWEB/}}
  \\\datedue{17/5/2002}

\item Seja~$T_n$ o número de árvores binárias com~$n$ nós internos.  Por
  exemplo, $T_0=T_1=1$, $T_2=2$, $T_3=5$, etc.  
  \begin{enumerate}
  \item[(\textit{i})]Prove que, para todo~$n>0$, temos~$T_n=\sum_{0\leq
      k<n}T_kT_{n-k-1}$. 
  \item[(\textit{ii})]Quantos times (mistos) de futebol podemos escalar se
    temos~$m$ meninos e~$n$ meninas?
  \item[(\textit{iii})]Prove a \textit{identidade de Vandermonde} para
    coeficientes binomiais: para todo~$m$, $n$, e~$k\geq0$ inteiros, temos 
    \begin{equation}
      \label{eq:Vandermonde}
      \sum_j{m\choose j}{n\choose k-j}={m+n\choose k},
    \end{equation}
    onde a soma do lado esquerdo é sobre todo~$j$ inteiro.  Se~$x\in\RR$
    e~$k\in\ZZ$, definimos
    $$
    {x\choose k}=
    \begin{cases}
      0 &\text{se~$k<0$}\\
      {1\over k!}x(x-1)\dots(x-k+1) &\text{se~$k\geq0$.}
    \end{cases}
    $$
    (Note que a definição acima coincide com a definição usual de coeficientes
    binomiais para~$x$ e~$k$ inteiros não-negativos.)
  \item[(\textit{iv})]Prove que~\eqref{eq:Vandermonde} vale também na forma 
    \begin{equation}
      \label{eq:VandermondeR}
      \sum_{j\in\ZZ}{x\choose j}{y\choose k-j}={x+y\choose k},
    \end{equation}
    para todo~$x$ e~$y$ reais.  [\textit{Sugestão}.\quad Considere
    inicialmente o caso em que~$x$ é um inteiro fixo.  Neste caso, tanto o
    lado esquerdo como o lado direito de~\eqref{eq:VandermondeR} são
    polinômios na variável real~$y$; use este fato.]
  \item[(\textit{v})]Prove a identidade
    \begin{equation*}
      \label{eq:half}
      {-1/2\choose n}=\(-1\over4\)^n{2n\choose n}, 
    \end{equation*}
    válida para todo~$n$ inteiro, e deduza que
    \begin{equation*}
      \label{eq:half2}
      {1\over n+1}{2n\choose n}=2(-4)^n{1/2\choose n+1}
    \end{equation*}
    para todo~$n$ inteiro.
  \item[(\textit{vi})]O \textit{$n$-ésimo número de Catalan}~$C_n$ é dado por
    $$
    C_n={1\over n+1}{2n\choose n}.
    $$
    Faça uma tabela dos~$C_n$ para valores pequenos de~$n$.
  \item[(\textit{vii})]Prove que~$T_n=C_n$ para todo~$n$.
    [\textit{Sugestão}.\quad Note que basta provar que~$T_n$ e~$C_n$
    satisfazem uma mesma recorrência.]  \datedue{21/5/2002}
  \end{enumerate}

\item (\textit{i})~Escreva uma função de cabeçalho
\begin{verbatim}
    int int_path_length(link h);
\end{verbatim}
  que, ao ser chamada com parâmetro~\texttt{h}, determina o comprimento
  interno da árvore binária cuja raiz é apontada por~\texttt{h}.
  (\textit{ii})~Escreva uma função de cabeçalho
\begin{verbatim}
    int ext_path_length(link h);
\end{verbatim}
  que, ao ser chamada com parâmetro~\texttt{h}, determina o comprimento
  externo da árvore binária cuja raiz é apontada por~\texttt{h}.
  \datedue{21/5/2002}
  
\item Escreva um programa (ou programas) para estudar a altura `típica' de
  árvores binárias de busca (ABBs).  Você deve considerar duas formas de se
  gerar tais árvores:
  \begin{enumerate}
  \item[(\textit{i})]gere~$N$ chaves distintas em ordem aleatória e as insira
    em uma ABB inicialmente vazia;
  \item[(\textit{ii})]considere as~$N$ primeiras palavras distintas de um
    texto longo e as insira em uma ABB inicialmente vazia.  Você pode achar
    útil o utilitário \texttt{tr} (experimente aplicar \texttt{tr -d ".,;:"}
    em um texto).
  \end{enumerate}
  Você deve fazer estes experimentos para vários valores de~$N$ e então usar o
  \texttt{GNUPLOT} para comparar a altura destas árvores com a função $c\log
  N$ (a idéia é você determinar a constante~$c$, e também ver se esta função
  aproxima bem a altura).  \datedue{24/5/2002}
  
\item Prove a Propriedade 13.3 do Sedgewick considerando apenas
  se\-qüên\-cias de 3~inserções.  \datedue{28/5/2002}

\item Faça o exercício 14.10 do Sedgewick.  \datedue{4/6/2002}

\item Escreva um programa para resolver o seguinte problema.  Dado um texto e
  um inteiro~$K$, determine as~$K$ palavras (distintas) mais freqüentes no
  texto.  O seu programa deve imprimir estas~$K$ palavras em ordem decrescente
  de freqüência.  Cada palavra deve ser impressa juntamente com o número de
  vezes que ela ocorre no texto.
  
  O seu programa deve ser eficiente para que determinar as~$1000$ palavras
  mais comuns nos livros que você pode encontrar no
  \href{http://promo.net/pg/}{Projeto Gutenberg} seja `trivial'.
  
  O natural para se resolver este problema é usar tabelas de símbolos.
  Experimente várias implementações de tais tabelas (pelo menos, você deve
  usar ABBs e ABBs aleatórias; tente também usar tabelhas de
  espalhamento).  \datedue{7/6/2002} 

\item Resolva o problema do estacionamento enunciado em sala na aula de
  7/6/2002.  \datedue{14/6/2002}

  
\item Altere o programa os programas em
  \begin{center}
      \href{http://www.ime.usp.br/~yoshi/2002i/CompII/exx/g6}{\texttt{http://www.ime.usp.br/\textasciitilde
      yoshi/2002i/CompII/exx/g6}} 
  \end{center}
  para que, dados dois vértices do grafo gerado, um caminho de comprimento
  mínimo entre eles é determinado e impresso.  \datedue{28/6/2002}

\end{enumerate}

\end{document}

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