Programação das aulas
Primeiro semestre de 2019
Fevereiro e março
Abril
- 3 de abril (Aula 8):
- Problemas de busca decomponíveis (DSP)
- Árvores de segmentos
- Dinamização de estruturas usada em DSPs
- Técnicas de conversão de EDs para DSPs em retroativas
- Comentários sobre deque retroativa
Leitura recomendada: sec 4.2 e 5.2 do artigo Retroactive Data Structures;
para árvores de segmentos, veja sec 4.2 do livro Advanced Data Structures do Peter Brass ou sec 10.3 do Computational Geometry de de Berg et al;
para dinamização de EDs para DSPs, veja o artigo Decomposable Searching Problems I. Static to Dynamic Transformation.
Tarefa 6: Implementação de árvore de segmentos estática e dinâmica.
- 5 de abril (Aula 9):
- Tempo amortizado por inserção na árvore de segmentos dinâmica vista na aula passada.
- Estruturas de dados cinéticas
- Predecessor cinético e heap cinético
Leitura recomendada: sec 5.2 do artigo Data Structures for Mobile Data.
- 10 e 12 de abril: aulas canceladas - a serem repostas.
- 17 e 19 de abril: Semana Santa
- 24 de abril (Aula 10):
- Conjectura da otimalidade dinâmica
- Árvores Splay
Leitura recomendada: aula 5 do curso do Demaine. Para splay trees, veja a lecture 12 do livro "The Design and Analysis of Algorithms", de Kozen.
- 26 de abril (Aula 11):
- Otimalidade dinâmica: geometria de buscas em ABBs
- Treaps
- Estratégia gulosa
Leitura recomendada: aula 5 do curso do Demaine.
Maio e demais meses