Consolidar conceitos de análise da correção e do desempenho de algoritmos. Consolidar estratégias algorítmicas. Desenvolver a habilidade de projetar algoritmos e estimar seu desempenho. Introduzir noções da teoria da complexidade computacional.
Análise da correção e do desempenho de algoritmos. Análise amortizada de estruturas dinâmicas. Paradigmas de projeto de algoritmos. Estudo de casos. Introdução à complexidade computacional.
Complexidade de tempo e espaço de algoritmos. Análise assintótica: notação O, Ômega e Teta. Análise de pior caso e análise probabilística. Análise amortizada de estruturas dinâmicas (tabelas dinâmicas, union find, splay trees). Paradigmas de projeto de algoritmos (programação dinâmica, divisão e conquista, aleatorização) e métodos de análise. Algoritmos gulosos. Estudo de casos: análise do algoritmo quicksort aleatorizado, análise de tabelas de hashing, problema da mochila, multiplicação de inteiros (algoritmo de Karatsuba) e matrizes (algoritmo de Strassen), árvores geradoras mínimas de grafos (algoritmos de Prim e Kruskal). Cota inferior de ordenação. Introdução à teoria da complexidade computacional. Redução entre problemas. As classes P, NP, e NP-completo. Tópicos opcionais: fluxo em redes (algoritmo de Ford-Fulkerson), programação linear, todos os caminhos mínimos num grafo (algoritmo de Floyd-Warshall), algoritmos de aproximação, algoritmos probabilísticos.
T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein, Introduction to Algorithms, 3rd ed., McGraw-Hill, 2001.T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein, Algoritmos, 3a. ed., Elsevier, 2013.S. Dasgupta, C.H. Papadimitriou, U.V. Vazirani, Algorithms, McGraw-Hill, 2007.J. Kleinberg, É. Tardos, Algorithm Design, Addison-Wesley, 2005.D.E. Knuth, The Art of Computer Programming, vols. 1 e 3, Addison-Wesley, 1973.