Programação das aulas

Sujeito a mudanças...

Março

Abril

• 3 de abril:
  • Prova 1
    Matéria da prova: listas lineares: pilhas, filas e filas duplas; representação seqüencial (em vetor) e ligada (como uma lista ligada); aplicações; listas ligadas de todos os tipos: simples, circulares, duplamente ligadas, com cabeça, sem cabeça; aplicações (ordenação topológica, polinômios e matrizes esparsos).

• 6 de abril (Aula 9):
  • Árvores e árvores binária
  • Algoritmos em árvores (percursos pré, in e pós-ordem, etc)
  • Lista 3 (árvores, árvores binárias e ABBs) [ps.gz] [pdf]

  Leitura recomendada: CLRS, sec 10.4.

• 10 e 13 de abril:
  • Semana Santa (segunda semana de break)

• 17 de abril (Aula 10):
  • Árvore binária de busca (ABB): definição, busca, máximo, sucessor, inserção.

  Leitura recomendada: CLRS, secs 12.1-12.3.

• 20 de abril (Aula 11):
  • ABBs: remoção.
  • Árvores com fios
  • Lista 4 (mais uns de árvores) [ps.gz] [pdf]

  Exercícios: Reescreva as funções minimo, sucessor, busca, insere para uma ABB com fios.

  Leitura recomendada: sec 3.6 do livro do Jayme Szwarcfiter e Lilian Markenzon, Estruturas de Dados e seus Algoritmos.

• 24 de abril (Aula 12):
  • Altura de árvores de busca binária aleatórias (CLRS sec 12.4; a análise que fizemos em aula foi tirada do CLR na verdade)

• 27 de abril (Aula 13):
  • Árvores rubro-negras: definição e análise da altura (CLRS cap 13)
  • Rotações