Programação das aulas
Primeiro semestre de 2021
Agosto
Setembro
Outubro
4 de outubro (Aula 14):
Estratégia gulosa
Delimitações inferiores para ABB ótima
Leitura recomendada:
aula 6
do curso do Demaine.
6 de outubro (Aula 15):
Delimitações inferiores de Wilber
Árvores Tango
Slides
[
pdf
].
Leitura recomendada:
aula 6
do curso do Demaine e o artigo
The geometry of binary search trees
11 de outubro:
recesso (pelo 12 de outubro)
13 de outubro (Aula 16):
Conectividade em grafos dinâmicos
Algoritmo que usa florestas dinâmicas
Slides
[
pdf
].
Leitura recomendada:
Caps 3 e 4 do
TCC do Gabriel Russo
.
18 de outubro (Aula 17):
Florestas dinâmicas
Euler tour trees
Conectividade em grafos dinâmicos
Slides
[
pdf
].
Leitura recomendada:
aula 20
do curso do Demaine e Caps 4 e 5 do
TCC do Gabriel Russo
.
Tarefa 8:
Implementação de florestas dinâmicas, usando Euler tour trees, implementadas com splay trees ou treaps.
20 de outubro (Aula 18):
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)
Slides
[
pdf
].
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.
25 de outubro (Aula 19):
Construção dos vetores de sufixos e de lcps a partir da árvore de sufixos
Árvore cartesiana: construção em tempo linear
Slides
[
pdf
].
Leitura recomendada:
Sec 7.14 até a Subsec 7.14.6 do livro Algorithms on Strings, Trees, and Sequences. Sobre treaps e árvores cartesianas, veja este
site
.
Tarefa 9:
Implementação da construção linear do vetor de LCPs estendidos e da busca eficiente com vetor de sufixos e LCPs.
27 de outubro (Aula 20):
Construção linear da árvore de sufixos a partir dos vetores de sufixos e LCP
Construção linear dos vetores de sufixos
Construção linear do vetor LCP do vetor de sufixos
Slides
[
pdf
].
Leitura recomendada:
Parte da
aula 16
do curso do Demaine. Seção 3 do
artigo de Kasai et al.
Tarefa 10:
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.
Tarefa 11:
Implementação da construção linear do vetor de sufixos e da construção linear do vetor LCP a partir do vetor de sufixos.
Novembro e demais meses