| Ementa/Descrição: |
Tempo de execução e análise assintótica. Corretude de algoritmos iterativos e recursivos. Recorrências e técnicas de solução de recorrências. Enumeração e backtracking. Divisão e conquista (sugestões de exemplos: Mergesort, multiplicação de inteiros, matrizes, par mais próximo, contagem de inversões). Aleatorização (sugestões de exemplos: Quicksort aleatorizado, problema da seleção). Tópicos opcionais: análise amortizada. |
| Referências: |
"CORMEN, Thomas H.; LEISERSON, Charles E.; RIVEST, Ronald L.; STEIN, Clifford. Algoritmos: teoria e prática. Rio de Janeiro, RJ: Elsevier, 2012. 926 p.
DASGUPTA, Sanjoy; PAPADIMITRIOU, Christos H.; VAZIRANI, Umesh V. Algorithms. Boston, USA: McGraw-Hill, 2008. 320 p.
SEDGEWICK, Robert. Algorithms in C, Parts 1-4: Fundamentals, Data Structure, Sorting, Searching. 3. ed. Reading, USA: Addison-Wesley Publishing, 1998. 702 p.
Bibliografia complementar
KLEINBERG, Jon; TARDOS, Éva. Algorithm Design. 1. ed. Boston, USA: Addison-Wesley, 2006. 864 p.
MANBER, Udi. Introduction to Algorithms: A Creative Approach. Boston, USA: Addison-Wesley, 1989. 478 p.
SEDGEWICK, Robert; WAYNE, Kevin. Algorithms. 4. ed. Boston, USA: Addison-Wesley, 2011. 955 p."
|
