MAC-IME-USP CARLOS EDUARDO FERREIRA

SALA 297A TEL.: 3091 6140

E-MAIL cef@ime.usp.br

MAC 5711 - Análise de Algoritmos

Segunda lista de exercícios - entrega 8 de abril de 2003

1. Mostre que para todo $a,b > 0$ vale que
   
   $$(\log n)^a=O(n^b).$$
   
   

2. Onde pode estar o menor elemento de um vetor com a propriedade heap? E o terceiro maior elemento?

3. Considere um heap $d$-ário, em que cada elemento tem exatamente $d$ filhos.
   1. Como representar um heap $d$-ário em um vetor?
   2. Qual é a altura de um heap $d$-ário com $n$ elementos?
   3. Escreva um algoritmo para a operação Extrai-Máximo. Qual a complexidade de tempo de seu algoritmo?
   4. Escreva um algoritmo para a operação de Inserção, e analise a sua complexidade de tempo.

4. Faça uma função que recebe um vetor $v$ com $n$ inteiros e utilizando espaço adicional constante coloca os números pares no começo do vetor e os números ímpares no fim, devolvendo o índice do primeiro número ímpar, ou $n+1$ se todos os números do vetor forem pares. Diga qual é a complexidade de sua função, e justifique.

5. Qual a profundidade mínima de uma folha na árvore de decisão de um algoritmo de ordenação baseado em comparações?

6. Mostre que são necessárias no mínimo $2n - 1$ comparações para concatenar duas listas ordenadas com $n$ elementos cada.

7. Considere $n$ inteiros no intervalo $[1,n^2]$. É possível escrever uma função para ordená-los em tempo $O(n)$? Justifique.