Estruturas de Dados Avançadas

Segundo semestre de 2023

As tarefas são individuais, e alunos envolvidos em cola serão sumariamente reprovados na disciplina. Se tiver qualquer dúvida sobre o que pode ou não fazer nas suas implementações, basta perguntar no fórum.

Tarefas:

1. Implementação de deque persistente usando skew binary representation.
2. Implementação de uma treap e de uma treap funcional (persistente). Sua implementação da treap deve ser recursiva, sem apontadores parent. Se implementar uma ABB simples funcional, em vez da treap funcional, a tarefa valerá 8.0 pontos.
3. Implementação de pilha retroativa.
   Se a implementação usar uma ABB simples (não balanceada), vale nota parcial.
4. Implementação de árvore de segmentos estática e dinâmica.
5. Implementação de um heap cinético.
   Se implementar um heap cinético sem inserção/remoção, que não precisa de identificadores, vale nota parcial.
6. Implementação de uma árvore splay e de uma treap com split e join.
7. Implementação de florestas dinâmicas usando Euler tour trees, implementadas com uma splay tree ou uma treap.
8. Implementação da construção trivial do vetor de sufixos de um texto T (ordene os sufixos de T) e do vetor LCP, e implementação da construção linear, a partir do vetor LCP, dos vetores LLCP e RLCP para o texto T, e busca de uma palavra P no texto T, simples e número de ocorrências, em tempo O(|P|+lg |T|), usando estes vetores, e lista de ocorrências em tempo O(|P|+lg |T|+t), onde t é o número de ocorrências de P em T.
9. Implementação da construção em tempo linear da árvore de sufixos de T a partir do vetor de sufixos e vetor LCP, e busca de um padrão P, usando a árvore de sufixos (busca simples e número de ocorrências de P em T em tempo O(|P|)) e lista de ocorrências em tempo O(|P|+t), onde t é o número de ocorrências de P em T. Implementação da construção linear do vetor de sufixos e LCP a partir da árvore de sufixos.
10. Implementação da construção em tempo linear do vetor de sufixos de um texto T e do vetor LCP a partir do vetor de sufixos.
    Se implementar só a construção linear do LCP a partir do vetor de sufixos, vale nota parcial.

• Interfaces a serem implementadas.
• Exemplo de arquivo de entrada de teste para deque e saída correspondente.
• Exemplo de arquivos de entrada de teste para treap e treap funcional, e saídas correspondentes.
• Exemplo de arquivo de entrada de teste para pilha retroativa e saída correspondente.
• Exemplo de arquivo de entrada de teste para árvore de segmentos estática e dinâmica e saída correspondentes.
• Exemplo de arquivo de entrada de teste paro heap cinético e saída correspondente.
• Exemplo de arquivo de entrada de teste para a splay tree, e saída correspondente.
• Exemplo de arquivo de entrada de teste para a floresta dinâmica, e saída correspondente.
• Exemplo de arquivo de entrada de teste para as tarefas T8 e T10, e saída correspondente.
• Exemplo de arquivo de entrada de teste para a tarefa T9 e saída correspondente.