Programação das au11;rgb:0000/0000/0000la 20las

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

Março

Abril

Maio

Junho

• 3 de junho (Aula 22):
  • Construção dos vetores de sufixos e de LCP a partir da árvore de sufixos
  • Árvore cartesiana: construção em tempo linear
  • Construção linear da árvore de sufixos a partir dos vetores de sufixos e LCP
  Leitura recomendada: Sec 4.3 do TCC do Marco Alves de Alcântara. Sobre treaps e árvores cartesianas, veja este site.
  Tarefa 9: Implementação da construção linear da árvore de sufixos a partir dos vetores de sufixo e LCP, e da busca eficiente com árvore de sufixos. Construção linear do vetor de sufixos e LCP da árvore de sufixos.

• 5 de junho: aula cancelada.

• 10 de junho (Aula 23):
  • Construção linear dos vetores de sufixos
  Leitura recomendada: Cap 3 do TCC do Marco Alves de Alcântara.
  Há também uma construção linear da árvore de sufixos. Para uma descrição detalhada desta construção, veja a Sec 4.5 do TCC do Yan Soares Couto.
  Tarefa 10: Implementação da construção linear do vetor de sufixos e da construção linear do vetor LCP a partir do vetor de sufixos.

• 12 de junho (Aula 24):
  • Estruturas de dados implícitas, sucintas e compactas
  • Tries binárias sucintas - rank
  • Tries binárias sucintas - select
  Leitura recomendada: Cap 1 do TCC do Maximilian Cabrajac Göritz. Leia também a entrada da wiki sobre succinct data structure.

• 17 de junho (Aula 25):
  • Tries binárias: uma segunda representação sucinta
  • Vetor de sufixos comprimido
  Leitura recomendada: Parte final da aula 17 e parte da aula 18 do curso do Demaine. Para uma descrição detalhada de como encontrar o par de um parêntesis numa sequência balanceada, veja o Cap 2 do TCC do Maximilian Cabrajac Göritz. Leia também a entrada da wiki sobre compressed suffix array.

• 19 de junho: feriado de Corpus Christi

• 24 de junho (Aula 26):
  • Vetor de sufixos compacto
  • Árvore de sufixos sucinta
  Leitura recomendada: Final da aula 18 do curso do Demaine.