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 5: Implementação de uma splay tree e de uma treap, com split e join; algoritmo guloso para construir um conjunto AS para uma sequência; algoritmo que decide se um conjunto de pontos é AS ou não.

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

• 22 de abril (Aula 13):
  • Estruturas de dados cinéticas
  • Predecessor cinético
  Leitura recomendada: Cap 1 do TCC do Marcos Siolin Martins e introdução do artigo Data Structures for Mobile Data. Segunda metade (a partir do minuto 31) da Aula 4 do curso do Demaine.

• 24 de abril (Aula 14):
  • Heap e torneio cinético
  Leitura recomendada: Cap 2 do TCC do Marcos Siolin Martins.
  Tarefa 6: Implementação de um heap cinético.

• 29 de abril (Aula 15):
  • Par de pontos mais próximos: algoritmo de Basch, Guibas e Hershberger
  • Par de pontos mais próximos cinético
  • Grafos dinâmicos, conexidade dinâmica: um esquenta
  Leitura recomendada: Cap 3 do TCC do Marcos Siolin Martins.