Programação das aulas

Agosto

Setembro

• 1 de setembro (Aula 6):
  • Técnica node copying para persistência parcial
  • Retroatividade
  • Fila retroativa
  Slides [pdf].
  Leitura recomendada: Sec 7.5 da dissertação do Yan Couto e Cap 4 do TCC da Beatriz Marouelli.
  Tarefa 2: Implementação de uma ABB simples ou funcional (persistente) ou parcialmente persistente pela técnica de node copying.

• 6 de setembro: recesso (pelo 7 de setembro)

• 8 de setembro (Aula 7):
  • Pilha retroativa
  • Fila de prioridade parcialmente retroativa
  Slides [pdf].
  Leitura recomendada: Cap 5 e começo do Cap 6 do TCC da Beatriz Marouelli.
  Tarefa 3: Implementação de pilha retroativa.

• 13 de setembro (Aula 8):
  • Fila de prioridade parcialmente retroativa
  • Problemas de busca decomponíveis (DSP)
  • Árvores de segmentos
  Slides [pdf].
  Leitura recomendada: Cap 6 do TCC da Beatriz Marouelli e 5.2 do artigo Retroactive Data Structures; para árvores de segmentos, veja a entrada da wiki, ou a sec 4.2 do livro Advanced Data Structures do Peter Brass ou a sec 10.3 do Computational Geometry de de Berg et al.
  Tarefa 4: Implementação de fila de prioridade parcialmente retroativa.

• 15 de setembro (Aula 9):
  • Comentários sobre pilha retroativa
  • Árvores de segmentos
  • Técnicas de conversão de EDs para DSPs em retroativas
  • Dinamização de EDs: árvores de segmentos dinâmica
  • Comentários sobre heap parcialmente retroativo
  Slides [pdf].
  Leitura recomendada: para dinamização de EDs para DSPs, veja o artigo Decomposable Searching Problems I. Static to Dynamic Transformation, e sec 5.2 do artigo Data Structures for Mobile Data.
  Tarefa 5: Implementação de árvore de segmentos dinâmica.

• 20 de setembro (Aula 10):
  • Estruturas de dados cinéticas
  • Predecessor cinético e heap cinético
  Slides [pdf].
  Leitura recomendada: Até a Sec 3.1 do texto da IC 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.
  Tarefa 6: Implementação de um heap cinético.

• 22 de setembro (Aula 11):
  • Torneio cinético
  • Ideias do algoritmo cinético do par de pontos mais próximos
  • Comentários sobre heap parcialmente retroativo
  Slides [pdf].
  Leitura recomendada: Até a Sec 3.2 do texto da IC do Marcos Siolin Martins. Para saber mais sobre o algoritmo para o par mais próximo, veja o Cap 4 desse texto e/ou Sec 3 do artigo Data Structures for Mobile Data.

• 27 de setembro (Aula 12):
  • Conjectura da otimalidade dinâmica
  • Árvores Splay
  Slides [pdf].
  Leitura recomendada: Aula 5 do curso do Demaine. Para splay trees, veja a lecture 12 do livro "The Design and Analysis of Algorithms", de Kozen.

• 29 de setembro (Aula 13):
  • Otimalidade dinâmica: geometria de buscas em ABBs
  • Treaps
  Slides [pdf].
  Leitura recomendada: Aula 5 do curso do Demaine.
  Tarefa 7: Implementação de uma splay tree e de uma treap.