Mais exercícios sugeridos

[Imre Simon <is@ime.usp.br>]

Avisos:

Nesta semana estaremos estudando o capítulo 36 do livro : P=NP?

Na segunda feira, dia 27nov00 darei um "crash-course" sobre algoritmos
em grafos.

Lembro que a última prova será realizada no dia 29nov00.

Depois disto, temos a entrega do projeto no dia 09dez00 e a
apresentação de 15 min, para cada projeto, no dia 11dez00, a partir
das 14:00 .


================

Lista de exercícios. Não é necessário entregar esta lista. Mas é muito
recomendado fazer os exercícios.

 1. Exercício 16-1-4, página 309 do CLR.

 2. Exercício 16-2-2, página 314 do CLR.

 3. Exercício 16-3-5, página 319 do CLR.

 4. Exercício 16-3-6, página 319 do CLR.

 5. Problema 16-3, página 325 do CLR.

 6. MAC 5711 - 1o semestre de 2000, Paulo Feofiloff
    http://www.ime.usp.br/~pf/mac5711/exercs/ex08.html

    Pares de livros:   Suponha dado um conjunto de livros numerados de
    1 a n. Suponha que cada livro i tem um peso p[i] tal que
    0 < p[i] < 1.

    Problema: Acondiconar os livros no menor número possível de
    envelopes de modo que cada envelope tenha 1 ou 2 livros e
    o peso do conteúdo de cada envelope não passe de 1.

    Escreva um algoritmo guloso que determine o número mínimo de
    envelopes. O consumo de tempo do algoritmo deve ser O(n logn).

    Procure provar que o seu algoritmo está correto.

 7. Exercício 17-1-2, página 333 do CLR.

 8. Exercício 17-2-5, página 337 do CLR.

 9. Exercício 17-3-6, página 344 do CLR.

10. Problema 17-1, página 353 do CLR.

11. Exercício 18-1-1, página 360 do CLR.

12. Exercício 18-1-3, página 360 do CLR.

13. Exercício 18-2-3, página 363 do CLR.

14. Exercício 18-3-2, página 366 do CLR.

15. Exercício 18-3-6, página 367 do CLR.

16. Exercício 18-4-2, página 374 do CLR.


Bom trabalho!

Imre Simon