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:

  1. Implementação de pilhas e filas persistentes usando skew binary representation.
  2. Implementação de deque persistente usando skew binary representation e LCA.
  3. Implementação de uma ABB simples funcional persistente.
  4. Implementação de fila retroativa e pilha retroativa.
  5. Implementação de fila de prioridade parcialmente retroativa.
  6. Implementação de árvore de segmentos estática e dinâmica.
  7. Implementação de uma árvore splay e de uma treap, com contadores para comparação do número de nós acessados.
  8. Implementação das rotinas de conexidade em grafos dinâmicos.
  9. 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.
  10. Implementação da construção em tempo linear do vetor de sufixos e do vetor dos lcps a partir da árvore de sufixos.
  11. 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.
  12. 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:

Datas e horários da quarta/quinta entrevista: Datas e horários da terceira/quarta entrevista: Datas e horários da segunda entrevista: Datas e horários da primeira entrevista: Esta página está em construção.
Cristina Gomes Fernandes
Sala 107C - Tel: 3091-5709
E-mail: cris at ime.usp.br