Estruturas de Dados Avançadas
Primeiro semestre de 2019
Todas as implementações deverão ser feitas em python, usando apenas bibliotecas padrão.
Periodicamente, cada aluno será chamado para apresentar a sua implementação, os testes que está desenvolvendo, etc.
Tarefas:
- Implementação de pilhas e filas persistentes usando skew binary representation.
- Implementação de deque persistente usando skew binary representation e LCA.
- Implementação de uma ABB simples funcional persistente.
- Implementação de fila retroativa e pilha retroativa.
- Implementação de fila de prioridade parcialmente retroativa.
- Implementação de árvore de segmentos estática e dinâmica.
- Implementação de uma árvore splay e de uma treap,
com contadores para comparação do número de nós acessados.
- Implementação das rotinas de conexidade em grafos dinâmicos.
- Implementação da árvore de sufixos com ABBB nos nós (construção vista em aula, em tempo quadrático);
o algoritmo de busca do número de ocorrências de um padrão P
deve consumir tempo O(|P| log |A|), onde A é o alfabeto.
- Implementação da construção em tempo linear do vetor de sufixos
e do vetor dos lcps a partir da árvore de sufixos.
- Implementação do algoritmo de busca do número de ocorrências de um padrão P
em tempo O(|P| + log |T|) usando os vetores de sufixos e de lcps do texto T.
- Implementação do pré-processamento e da função rank1(i) para uma string binária.
Instruções:
Entrevistas:
Datas e horários das próximas duas entrevistas:
- Sexta, 5/7, às 10:30: Rafael
- Sexta, 5/7, às 13:10: Bia
- Quarta, 10/7, às 10:30: Lais
- Quarta, 10/7, às 13:00: Rafael
- Quarta, 10/7, às 14:00: Lucas
- Quarta, 10/7, às 15:00: Bia
- Quinta, 11/7, às 13:30: Lais
Datas e horários da quarta/quinta entrevista:
- Sexta, 28/6, às 9:45: Bia
- Sexta, 28/6, às 10:40: Rafael
- Segunda, 1/7, às 13:30: Lais
Datas e horários da terceira/quarta entrevista:
- Segunda, 24/6, às 9:15: Bia
- Segunda, 24/6, às 10:30: Lais
- Segunda, 24/6, às 16:15: Rafael
Datas e horários da segunda entrevista:
- Sexta, 10/5, às 10h: Lais
- Sexta, 10/5, às 10h45: Rafael
- Segunda, 13/5, às 13h30: Bia
Datas e horários da primeira entrevista:
- Quinta, 21/3, às 14h: Bia
- Quinta, 21/3, às 15h15: Rafael
- Sexta, 22/3, às 9h: Lais
- Sexta, 22/3, às 14h: Lucas
- Quarta, 27/3, às 13h30: Gabriel
- Sexta, 29/3, às 10h: Arthur
Esta página está em construção.
Cristina Gomes Fernandes
Sala 107C - Tel: 3091-5709
E-mail: cris at ime.usp.br