\documentclass[11pt]{article}

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

\pagestyle{empty}
\setlength{\textwidth}{16cm}
\setlength{\textheight}{24cm}
\setlength{\oddsidemargin}{0mm}
\setlength{\topmargin}{-5mm}

\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{3mm}
{\large
{\bf Lista 5} 
}

\vspace{1mm}
% Devolução: 3 de outubro de 2002
\end{center}

\begin{enumerate}
  
\item {\bf Exercício 6-2 do CLR} (coloquei uma cópia no xerox).

\item {\bf (Exercício 10.1-1 do CLR)} Mostre que o segundo menor
  elemento dentre $n$ elementos pode ser encontrado em 
  $n+\ceil{\lg n}-2$ comparações no pior caso. (Dica: use uma
  estratégia como a do \texttt{mergesort}.)

\item {\bf (Exercício 10.1-2 do CLR)} Mostre que $\ceil{3n/2}-2$
  comparações são necessárias no pior caso para encontrar o máximo e o
  mínimo de $n$ números. (Dica: considere quantos números são
  potencialmente ou o máximo ou o mínimo e investigue como uma
  comparação afeta esse contador.)

\item {\bf (Exercício 10.2-1 do CLR)} Escreva uma versão iterativa
  (não-recursiva) do \texttt{seleciona} aleatório (o
  \texttt{randomized-selection} do CLR). 

\item {\bf (Exercício 10.3-1 do CLR)} No \texttt{seleciona}, os
  elementos da seqüência são divididos em grupos de 5. O algoritmo
  continua linear se dividirmos os elementos em grupos de 7? E em
  grupos de 3? 
  
\item {\bf (Exercício 10.3-5 do CLR)} Dado um algoritmo linear
  ``caixa-preta'' para encontrar uma mediana de um vetor, dê um
  algoritmo simples, linear, que resolve o problema do $k$-ésimo
  mínimo. 

\item {\bf (Exercício 10.3-8 do CLR)} Sejam $X[1..n]$ e $Y[1..n]$ dois
  vetores, cada um contendo $n$ números ordenados. Dê um algoritmo
  $O(\log n)$ para encontrar a mediana de todos os $2n$ elementos nos
  vetores $X$ e $Y$. 

\item {\bf (Exercício 31.2-1 do CLR)} Use o método de Strassen para calcular o
  produto das seguintes matrizes:
\[ \left( \begin{array}{cc}
               1 & 3 \\
               5 & 7
          \end{array} \right)
   \left( \begin{array}{cc}
               8 & 4 \\
               6 & 2
          \end{array} \right). \]
Mostre os seus cálculos. 

\item {\bf (Exercício 31.2-3 do CLR)} Qual é o maior $k$ tal que se você
  multiplicar matrizes $3 \times 3$ usando $k$ multiplicações, então você pode
  multiplicar matrizes $n \times n$ em tempo assintoticamente melhor que
  $\Theta(n^{\lg 7})$ (mais precisamente, em tempo $o(n^{\lg 7})$)? Qual seria
  o tempo de execução deste algoritmo (em notação assintótica)? 

\item {\bf (Exercício 31.2-6 do CLR)} Mostre como multiplicar números
  complexos $a+bi$ e $c+di$ usando apenas três multiplicações reais. O seu
  algoritmo deve ter os números $a, b, c$ e $d$ como entrada, e produzir como
  saída dois números reais: a parte real, $ac-bd$, e a parte imaginária,
  $ad+bc$, do produto.

\end{enumerate}

\vspace{1cm}

\begin{center}
{\bf Entregue no dia 3/10 os exercícios 10.3-1, 10.3-5, 10.3-8 e 31.2-3.}
\end{center}

\end{document}

