Programação das aulas

Agosto

Setembro

• 4 a 8 de setembro: recesso (Semana da Pátria)

• 11 de setembro (Aula 9):
  • Árvores de segmentos
  • Técnicas de conversão de EDs para DSPs em retroativas
  • Dinamização de EDs: árvores de segmentos dinâmica
  Slides [pdf].
  Leitura recomendada: 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.; para dinamização de EDs para DSPs, veja o artigo Decomposable Searching Problems I. Static to Dynamic Transformation.
  Tarefa 4: Implementação de árvore de segmentos estática e dinâmica.

• 13 de setembro (Aula 10):
  • Estruturas de dados cinéticas
  • Predecessor cinético
  Slides [pdf].
  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.

• 18 de setembro (Aula 11):
  • Heap e torneio cinético
  • Ideias do algoritmo cinético do par de pontos mais próximos
  Slides [pdf].
  Leitura recomendada: Cap 2 do TCC do Marcos Siolin Martins. Para saber mais sobre o algoritmo para o par mais próximo, veja o Cap 3 do TCC do Marcos.
  Tarefa 5: Implementação de um heap cinético.

• 20 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.
  Tarefa 6: Implementação de uma splay tree e de uma treap, com split e join.

• 25 de setembro: não houve aula por conta da paralisação dos alunos.
  Houve uma conversa, via google meeting, sobre as expectativas em vista da paralisação e aproveitamos para tirar dúvidas sobre as tarefas. Na quarta-feira, caso a paralisação persista, combinamos que faremos a aula remotamente, online, e ela será gravada para quem não puder/quiser assistir no horário usual da aula.

• 27 de setembro: tiramos dúvidas sobre as tarefas via google meeting.