Programação das aulas

Os slides de todas as aulas estão acessíveis aqui.

Março

Abril

Maio

• 6 de maio (Aula 16):
  • Florestas dinâmicas
  • Euler tour trees
  Leitura recomendada: aula 20 do curso do Demaine e Caps 4 e 5 do TCC do Gabriel Russo.
  Tarefa 7: Implementação de florestas dinâmicas, usando Euler tour trees, implementadas com splay trees ou treaps.

• 8 de maio (Aula 17):
  • Conectividade em grafos dinâmicos
  • Algoritmo que usa florestas dinâmicas
  Leitura recomendada: Caps 3 e 4 do TCC do Gabriel Russo.

• 13 de maio (Aula 18):
  • Hierarquia de memória
  • Modelo de memória externa e modelo alheio ao cache
  Leitura recomendada: Começo da aula 7 do curso do Demaine.

• 15 de maio (Aula 19):
  • Hierarquia de memória
  • Manutenção de arquivos ordenados
  • Revisão de floresta dinâmica (para a T7)
  Leitura recomendada: Final da aula 7 do curso do Demaine.

• 20 de maio (Aula 20):
  • Busca de padrão
  • Vetor de sufixos
  • LCP: longest common prefix
  • Busca com vetor de sufixos e vetores de LCP
  Leitura recomendada: Cap 2 exceto pela Sec 2.4 do TCC do Marco Alves de Alcântara.
  
• 22 de maio (Aula 21):
  • Construção linear do vetor LCP
  • Tries e árvores de sufixos compactadas
  • Construção quadrática da árvore de sufixos
  • Construção dos vetores de sufixos e de LCP a partir da árvore de sufixos
  Leitura recomendada: Sec 2.4 e Cap 4 do TCC do Marco Alves de Alcântara. Tarefa 8: Implementação da construção linear do vetor de LCPs estendidos e da busca eficiente com vetor de sufixos e LCPs.

• 26 a 30 de maio: semana de break.