Programação das aulas
Primeiro semestre de 2019
Fevereiro e março
Abril
Maio
- 3 de maio (Aula 12):
- Delimitações inferiores para ABB ótima
- Árvores Tango
Leitura recomendada: aula 6 do curso do Demaine.
Tarefa 7: Implementação de uma árvore splay e de uma treap.
- 8 de maio (Aula 13):
- Conectividade em grafos dinâmicos
- Florestas dinâmicas
- Sequências Eulerianas
Leitura recomendada: Caps 3 e 4 do TCC do Gabriel Russo.
- 10 de maio (Aula 14):
- Sequências Eulerianas
- ABBs implícitas
- Conectividade em grafos dinâmicos
Leitura recomendada: Caps 4 e 5 do TCC do Gabriel Russo.
- 15 de maio: não houve aula (Paralização pela Educação)
- 17 de maio (Aula 15):
- Busca de padrão
- Tries e árvores de sufixos compactadas
- Construção quadrática da árvore de sufixos
- Vetor de sufixos e longest common prefix (lcp)
- Construção dos vetores de sufixos e de lcps a partir da árvore de sufixos
Leitura recomendada: Cap 2 e Cap 4 até a Sec 4.4 do TCC do Yan Couto e partes da aula 16 do curso do Demaine.
- 22 de maio (Aula 16):
- Vetor de sufixos e longest common prefix (lcp)
- Busca de padrão com vetor de sufixos
- Construção em tempo linear dos vetores de sufixos
Leitura recomendada: Sec 7.14 até a Subsec 7.14.6 do livro Algorithms on Strings, Trees, and Sequences.
- 29 de maio (Aula 17):
- Construção em tempo linear dos vetores de sufixos e lcps
- Revisão da busca usando os vetores de sufixos e lcps
- Árvore cartesiana: construção em tempo linear
Leitura recomendada: Parte da aula 16 do curso do Demaine. Seção 3 do artigo de Kasai et al.
- 31 de maio (Aula 18):
- Estruturas de dados implícitas, sucintas e compactas
- Tries binárias sucintas - rank
Leitura recomendada: Parte da aula 17 do curso do Demaine. Leia também a entrada da wiki sobre succinct data structure.
Junho