Programação das aulas

Os slides de todas as aulas estão acessíveis aqui.

Março

Abril

• 1 de abril (Aula 9):
  • Árvores com chaves só nas folhas
  • Árvores Splay
  • Split e join
  Leitura recomendada: Para splay trees, veja a lecture 12 do livro "The Design and Analysis of Algorithms", de Kozen e o Cap 2 do TCC do Bruno Armond Braga.

• 3 de abril (Aula 10):
  • Conjectura da otimalidade dinâmica
  • Otimalidade dinâmica: geometria de buscas em ABBs
  Leitura recomendada: Cap 3 do TCC do Bruno Armond Braga e aula 5 do curso do Demaine.

• 8 de abril (Aula 11):
  • Estratégia gulosa
  • Delimitações inferiores para ABB ótima
  Leitura recomendada: Caps 4 e 5 do TCC do Bruno Armond Braga e aula 6 do curso do Demaine.

• 10 de abril (Aula 12):
  • Prova do lema da aula passada
  • Delimitações inferiores de Wilber para OPT(X)
  • Árvores Tango
  Leitura recomendada: Cap 6 do TCC do Bruno Armond Braga e aula 6 do curso do Demaine e o artigo The geometry of binary search trees
  Tarefa 6: Implementação de uma splay tree e de uma treap, com split e join; algoritmo que decide se um conjunto de pontos é AS ou não; algoritmo guloso para construir um conjunto AS para uma sequência.

• 14 a 19 de abril: recesso (Semana Santa)