\documentclass[12pt]{article}
\usepackage[brazil]{babel}
\usepackage[latin1]{inputenc}
\usepackage[usenames]{color}
\usepackage{alltt}
\usepackage{graphicx}
\usepackage{latexsym}
\usepackage{amssymb}
\usepackage{amscd}
\usepackage{psfrag}
\usepackage{latexsym}

\title{Lista 5 de An\'{a}lise de Algoritmos}
\author{Nome do aluno}
\date{$1^{o}$ de outubro de 2007}
\begin{document}
\maketitle

\section*{{\color{blue} Exerc\'{i}cio 16.B}}

O seguinte algoritmo promete rearranjar o vetor $A[1..n]$ em ordem
crescente supondo que cada $A[{\color{red}j}]$ est\'{a} em
${1,\ldots,{\color{red}k}}$. O algoritmo est\'{a} correto? Estime, em
nota\c{c}\~{a}o O, o consumo de tempo do algoritmo.

\begin{alltt}
\textsc{Vito-Sort}(\(A,n,{\color{red}k}\))
1  \({\color{red}i} \leftarrow 1\)
2  para \(a \leftarrow 1\) at\'{e} \({\color{red}k} - 1\) fa\c{c}a
3    para \({\color{red}j} \leftarrow {\color{red}i}\) at\'{e} \(n\) fa\c{c}a
4      se \(A[{\color{red}j}] = a\)
5        ent\~{a}o \(A[{\color{red}j}] \leftrightarrow A[{\color{red}i}] \quad \rhd\) troca
6          \({\color{red}i} = {\color{red}i} + 1\)
\end{alltt}


\section*{Resposta do {\color{blue} Exerc\'{i}cio 16.B}}

R

\section*{{\color{blue} Exerc\'{i}cio 17.C}}

Escreva uma vers\~{a}o iterativa do algoritmo Select Aleatorizado (=
Randomized Select).

\section*{Resposta do {\color{blue} Exerc\'{i}cio 17.C}}

R

\section*{{\color{blue} Exerc\'{i}cio 18.A}}

No algoritmo \textsl{Select-BFPRT} a entrada \'{e} dividida em grupos
de {\color{red}5} elementos. O algoritmo consumir\'{a} tempo linear se
a entrada for for dividida em grupos de {\color{red}7} elementos?
Argumente que o algoritmo n\~{a}o ser\'{a} linear se a entrada for
dividida em grupos de {\color{red}3} elementos.

\section*{Resposta do {\color{blue} Exerc\'{i}cio 18.A}}

R

\section*{{\color{blue} Exerc\'{i}cio 18.B}}

Suponha que voc\^{e} tenha uma \textit{caixa preta} que resolve o
problema da mediana em tempo linear. Descreva um algoritmo simples que
determina o {\color{red}i}-\'{e}simo elemento em tempo linear.

\section*{Resposta do {\color{blue} Exerc\'{i}cio 18.B}}

R

\section*{{\color{blue} Exerc\'{i}cio 18.C}}

Suponha que sejam dados dois vetores ordenadors ${\color{red}X[1..n]}$ e ${\color{red}Y[1..n]}$. Descreva um algoritmo que determina a medana dos ${\color{red}2n}$ elementos dos vetores ${\color{red}X}$ e ${\color{red}Y}$ em tempo ${\color{red}O(lg\; n)}$.

\section*{Resposta do {\color{blue} Exerc\'{i}cio 18.C}}

R

\end{document}
