Programação das aulas

Fevereiro

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

• 1 de março (Aula 2):
  • Ancestrais de nível
  • Representação skew binary
  Leitura recomendada: Caps 1 e 2 da dissertação do Yan Couto.

• 8 de março (Aula 3):
  • Análise do tempo do algoritmo usando skew binary
  • Construção dos jump pointers.
  • Fila persistente
  Leitura recomendada: Cap 2 e Sec 3.2 e Cap 4 da dissertação do Yan Couto.
  Tarefa 1: Implementação de pilhas e filas persistentes usando skew binary representation.

• 13 de março (Aula 4):
  • LCA usando skew binary
  • Deque persistente
  • Técnicas gerais de conversão
  Leitura recomendada: Cap 4 e começo do Cap 7 da dissertação do Yan Couto.
  Tarefa 2: Implementação de deque persistente usando skew binary representation.

• 15 de março (Aula 5):
  • Técnicas gerais de conversão de EDs em (parcialmente) persistentes
  • Implementações funcionais, fat node, node copying
  • Comentários sobre ABBs e ABBs rubro-negras (parcialmente) persistentes
  Leitura recomendada: Sec 7.5 da dissertação do Yan Couto e Sec 7.2 do livro Advances Data Structures de Brass.
  Para uma descrição detalhada de uma ABB rubro-negra parcialmente persisitente obtida pela técnica de node copying, veja o Cap 8 da dissertação do Yan Couto.
  Tarefa 3: Implementação de uma ABB simples funcional persistente.

• 27 de março (Aula 6):
  • Retroatividade
  • Filas e pilhas retroativas
  Leitura recomendada: sec 1, 2, 4.1 e 5.1 do artigo Retroactive Data Structures [pdf].
  Tarefa 4: Implementação de fila retroativa e pilha retroativa.

• 29 de março (Aula 7):
  • Fila de prioridade parcialmente retroativa
  Leitura recomendada: sec 5.4 do artigo Retroactive Data Structures.
  Tarefa 5: Implementação de fila de prioridade parcialmente retroativa.