Programa

• Introdução
• Tipos abstratos de dados e o tipo dicionário
• Árvores
  • Definições
  • Árvores Binárias de Busca
  • Aplicações
  • Árvores Balanceadas
    • AVL
    • Red-Black
    • Splay
    • B
  • Árvores Digitais
    • Trie
    • Patricia
  • Fila de Prioridade (Heap)
• Tabelas de Dispersão (hashing)

Objetivo

Apresentar e analisar algoritmos e estruturas de dados para representação do Tipo Abstrato de dados Dicionário. Apresentar e analisar algoritmos e estruturas de dados para representação de conjuntos não totalmente ordenáveis.

Notas e Avaliação

Duas provas e trabalhos. A média dos trabalhos tem o mesmo peso que uma prova.

Veja suas notas aqui.

Calendário

• Início: 02/08/2023 (não teremos aulas de 24 a 28 de julho - SBPC)
• Término: 01/12/2023
• 11/08/2023: não teremos aula (decisão do professor)
• 23/08/2023 e 25/08/2023: não teremos aula (SABER)
• 20/09/2023: Prova 1 (CONFIRMADO!!)
• 22/09/2023 e 27/09/2023: não teremos aula (viagem do professor)
• 09/10/2023: entrega do trabalho 1
• 13/10/2023: não teremos aula (recesso - feriado na véspera)
• 18/10/2023 e 20/10/2023: não teremos aula (SIEPE)
• 03/11/2023: não teremos aula (recesso - feriado na véspera)
• 29/11/2023: Prova 2 (tentativa!!)
• 08/12/2023: Prova final

Material de leitura e exercícios

• Especificação do primeiro trabalho prático
• Arquivos de exemplo para o primeiro trabalho prático
• Especificação do segundo trabalho prático
• Arquivo exemplo (texto de Eneida) para o segundo trabalho prático
• Implementação de Árvore Binária de Busca (exemplo adaptado pelo professor)
• Árvore Rubro-Negra - Siang Wun Song - Universidade de São Paulo - IME/USP - MAC 5710 - Estruturas de Dados - 2008
• Red-black trees - MIT Open Courses - Erik D. Demaine and Charles E. Leiserson
• Data Structure Visualizations - David Galles - Computer Science - University of San Francisco
• Estruturas de Dados notas de aula baseadas no livro Algorithms (de Sedgewick e Wayne) - Paulo Feofiloff - IME/USP

Bibliografia

[1] Introduction to Algorithms. Third Edition. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, e Clifford Stein. 2009.

[2] Algorithm Design. Jon Kleinberg e Éva Tardos. 2005.

[3] Algorithms. S. Dasgupta, C. H. Papadimitriou e U. Vazirani. McGraw Hill. 2006

[4] Estruturas de Dados e seus Algoritmos. J.L. Szwarcfiter, L. Markenzon. LTC-Livros Técnicos e Científicos, Rio de Janeiro, RJ, 1994.

[5] Data Structures and Algorithms. A.V. Aho, J.E. Hopcroft, J.D. Ullman. Addison-Wesley, Reading, Massachusetts, 1983.

[6] Algorithms and Data Structures. N. Wirth. Prentice-Hall, 1986 (Tradução: Algoritmos e Estruturas de Dados. Prentice-Hall do Brasil Ltda, 1989).

[7] The Art of Computer Programming vol. 1, D.E. Knuth.

Bibliografia complementar

[8] Donald E. Knuth. The art of computer programming, volume 3: (2nd ed.) sorting and searching. Redwood City, CA, USA: Addison Wesley Longman Publishing Co., Inc., 1998. ISBN : 0-201-89685-0.

[9] Udi Manber. Introduction to Algorithms: A Creative Approach. Boston, MA, USA: Addison-Wesley Longman Publishing Co., Inc., 1989. ISBN : 0201120372.

[10] Robert Sedgewick. Algorithms in C. Addison-Wesley, 1990, p. 657.

[11] Michael Mitzenmacher e Eli Upfal. Probability and Computing: Randomized Algorithms and Probabilistic Analysis. New York, NY, USA: Cambridge University Press, 2005. ISBN : 0521835402.

[12] Robert Sedgewick e Philippe Flajolet. An Introduction to the Analysis of Algorithms. 512 pages. (ISBN 0-201-40009-X). Addison-Wesley Publishing Company, 1996.