Programação das aulas

Agosto

• 7 de agosto (Aula 1):
  • Informações gerais
  • Estruturas de dados temporais: persistência e retroatividade
  • Pilha persistente
  Slides [pdf].
  Leitura recomendada: Introdução e Sec 3.1 da dissertação do Yan Couto.

• 9 de agosto (Aula 2):
  • Fila persistente
  • Ancestrais de nível e lowest common ancestor (LCA)
  • Representação skew binary
  Slides [pdf].
  Leitura recomendada: Sec 3.2 e Cap 1 da dissertação do Yan Couto.

• 14 de agosto (Aula 3):
  • Representação skew binary
  • Análise do tempo do algoritmo para LA usando skew binary
  Slides [pdf].
  Leitura recomendada: Cap 2 até Sec 2.3 da dissertação do Yan Couto.

• 16 de agosto (Aula 4):
  • Construção dos jump pointers
  • LCA usando skew binary
  • Deque persistente
  Slides [pdf].
  Leitura recomendada: Sec 2.4 e Cap 4 da dissertação do Yan Couto.
  Tarefa 1: Implementação de deque persistente baseada na skew binary representation.

• 21 de agosto (Aula 5):
  • Técnicas gerais de conversão de EDs em (parcialmente) persistentes
  • Implementações funcionais, fat node, node copying
  • Treaps
  Slides [pdf].
  Leitura recomendada: Cap 7 até começo da Sec 7.5 da dissertação do Yan Couto e/ou Sec 7.2 do livro Advances Data Structures de Brass.
  Tarefa 2: Implementação de uma treap e de uma treap funcional (persistente).

• 23 de agosto (Aula 6):
  • Retroatividade
  • Fila retroativa
  • Pilha retroativa: só um esquenta
  Slides [pdf].
  Leitura recomendada: Caps 4 do TCC da Beatriz Marouelli.

• 28 de agosto (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.

• 30 de agosto (Aula 8):
  • Fila de prioridade parcialmente retroativa
  • Problemas de busca decomponíveis (DSP)
  • Árvores de segmentos
  Slides [pdf].
  Leitura recomendada: Sec 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.