\documentclass[11pt]{amsart}

%% Escrevendo em português:
\usepackage[brazil]{babel}
\usepackage[latin1]{inputenc} % isso é quase redundante
\usepackage{textcomp}
%\usepackage[T1]{fontenc}
%----------------------------
\makeatletter
\renewcommand{\labelenumi}{\theenumi.}
\makeatother

\begin{document}
\title{Exercício Programa 1}
\maketitle
\thispagestyle{empty}

\noindent\textbf{Data de entrega:}\quad 8/4/2002 (tentativo)

\bigskip

\noindent\textbf{Problema.}\quad
Escreva um programa (ou vários programas) para comparar os algoritmos de
ordenação vistos até agora: ordenação por inserção (não-adaptativo e
adaptativo), seleção, bolha, e por intercalação.  O ideal é que você monte um
esquema que torne fácil adicionar mais algoritmos para serem comparados.  Por
exemplo, logo estudaremos o \textit{quicksort}, e então pedirei que você
compare o quicksort com os demais algoritmos.

Você deve entregar não só os programas (por correio eletrônico para
\texttt{yoshi@ime.usp.br} e \texttt{daniel@linux.ime.usp.br}) como também um
relatório com suas conclusões.  Envie seu relatório eletronicamente também.

\bigskip

\begin{enumerate}
\item Para os seus testes, usem entradas de pelo menos 3 tipos: aleatórias,
  ordenadas (de forma crescente e de forma decrescente),
  ``qua\-se-or\-de\-na\-das'' (você terá de pensar o que isso pode significar
  mais precisamente).
  
\item O ideal é você escrever programas para gerar também as entradas.  Assim,
  você poderá fazer experimentos com conjuntos grandes de dados.

\item Você pode usar o comando \texttt{time} para determinar o tempo gasto
  por um programa: 
  \begin{small}
\begin{verbatim}
  yoshi@erdos:~$ time date
  Fri Mar  1 14:36:59 BRT 2002
  
  real    0m0.050s
  user    0m0.000s
  sys     0m0.000s
  yoshi@erdos:~$ 
\end{verbatim}
  \end{small}

\item Use o truque do \texttt{o} (``o pequeno'') visto em sala para contar o
  número de comparações e o número de atribuições de valores envolvendo os
  elementos sendo ordenados.
  \begin{small}
\begin{verbatim}
...
#define o ncomps++

int ncomps=0;
...

if (o,a[j-1]>a[j]) 
  <troque a[j-1] e a[j]>
...
<imprima ncomps>
...

\end{verbatim}
  \end{small}
\item Explique no relatório o funcionamento do seu sistema e discuta seus
  resultados. 

\item Você pode olhar os exercícios 6.9 e 6.10 do Sedgewick (Algorithms in~C)
  para conseguir mais inspiração.
  
\end{enumerate}

\end{document}

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