Objetivos: Estudar tópicos avançados de projeto e análise de algoritmos. A disciplina deverá proporcionar ao aluno a oportunidade de se familiarizar com resultados da teoria de algoritmos em várias áreas. Justificativa: O projeto de algoritmos é uma atividade fundamental na computação, e a análise é parte indispensável nesse projeto. Conteúdo: 1) Revisão de notação assintótica e recorrências. 2) Multiplicação de inteiros grandes. 3) Multiplicação de matrizes. 4) Transformada rápida de Fourier. 5) Algoritmos probabilísticos. 6) Quicksort probabilístico. 7) Mediana e generalizações. 8) Tabelas de dispersão (hashing). 9) Algoritmos gulosos. 10) Análise amortizada. 11) Busca de padrão. 12) Estrutura de dados para conjuntos disjuntos (union-find). 13) Tópicos em algoritmos em teoria dos números, geometria computacional, algoritmos de aproximação.
- Professor: Cristina Gomes Fernandes