MAC-IME-USP CARLOS EDUARDO FERREIRA

SALA 297A TEL.: 3091 6140

E-MAIL cef@ime.usp.br

MAC 5711 - Análise de Algoritmos

Terceira lista de exercícios - entrega 20 de maio de 2003

1. 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.

2. 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?

3. 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.

4. 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}$.

5. 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.

6. 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.

7. 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.