\documentclass[12pt]{article}
\usepackage[latin1]{inputenc}
\usepackage[brazil]{babel}

\def\R{\mbox{{\rm I\kern-0.22emR}}} % Set of  the  real numbers
\def\N{{\mbox{{\rm I\kern-0.22emN}}}}
\def\Z{{\rm Z}\!\!{\rm Z}}

\begin{document}
\noindent
{\footnotesize {\sc MAC--IME--USP}}  \hfill {\footnotesize {\sc Carlos Eduardo Ferreira}}

\vspace{-1mm}
\hfill {\footnotesize {\sc Sala 297A Tel.: 3091 6140}}

\vspace{-1mm}
\hfill {\footnotesize {\sc e-mail} cef@ime.usp.br}

\vspace{0.5cm}

\begin{center}
{\large
MAC 5711 -- Análise de Algoritmos
}

\vspace{0.7cm}

Terceira lista de exercícios -- entrega {\bf 20 de maio de 2003}
\end{center}

\begin{enumerate}


\item Pensando um pouco sobre árvores de busca binária formulei a seguinte
proposição. Suponha que ao buscar um elemento $k$ numa árvore de busca
binária, a busca termina numa folha $x$. Considere os conjuntos: $A$ (os elementos à
esquerda do caminho da raiz até $x$), $B$ (os elementos no caminho da raiz a
$x$) e $C$ (os elementos à direita do caminho). Então, para todo elemento
$a\in A$, $b \in B$ e $c \in C$ vale que $a\le b\le c$. Dê um contra-exemplo
que seja o menor possível para essa proposição. 

\item Qual é o maior número possível de nós internos numa árvore rubro-negra
de altura $k$? E o menor número possível? 

\item Descreva uma árvore rubro-negra com $n$ elementos (folhas nil não
contam) em que a razão entre o número de nós vermelhos e o número de nós
pretos internos seja a maior possível. Qual é o valor dessa razão? O mesmo
para a menor razão possível. 

\item Seja $R(i,j)$ o número de vezes que uma entrada da matriz $opt[i,j]$ é
referenciada no algoritmo que acha a solução ótima do problema de
multiplicação de cadeia de matrizes. Mostre que o número de referências para a
tabela inteira é
\[ \sum_{i=1}^n \sum_{j=1}^n R(i,j) = \frac{n^3 - n}{3}. \]
Você pode usar o seguinte fato: $\sum_{i=1}^n i^2 = \frac{n(n+1)(2n+1)}{6}$. 

\item Uma triangulação de um polígono convexo é uma subdivisão do seu interior
por diagonais que não se cruzam em regiões triangulares. Prove que toda
triangulação de um polígono convexo de $n$ vértices usa $n-3$ diagonais e
divide o polígono em $n-2$ triângulos. 

\item Escreva um algoritmo que recebe como entrada os vértices de um polígono
convexo (dados em ordem ``contra o sentido dos ponteiros do relógio'') e
encontra uma triangulação deste polígono que tenha custo mínimo. O custo de
uma triangulação é dado pela soma dos custos dos triângulos que a compõem e o
custo de um triângulo é igual à soma dos comprimentos de seus lados. 

\item Considere o seguinte problema. Um ladrão entrou em um salão com uma
mochila capaz de carregar $F$ quilos. Neste salão, cada um dos vários itens
que ele poderia roubar tem peso $f_i$ e valor $v_i$. O ladrão resolveu seguir
uma estratégia gulosa, roubando os itens de maior valor até que nada mais
coubesse na sua mochila. \\
a. Mostre que a estratégia do ladrão não produz a solução ótima para toda
instância de entrada possível. \\
b. Construa uma instância com $n$ itens em que a estratégia do ladrão é
ótima. \\
c. É possível garantir que se $v^*$ é o valor do melhor roubo possível com
aquela mochila, existe uma constante 
$k > 0$ tal que a estratégia do ladrão produz uma
solução de valor maior ou igual a $\frac{v^*}{k}$. Justifique detalhadamente
sua resposta.  

\end{enumerate}
\end{document}