Estruturas de Dados Avançadas

Primeiro semestre de 2025

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 de discussão da disciplina.

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á 7.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. Parte 1: Implementação de uma árvore splay e de uma treap com split e join. Veja a interface abaixo.
   Parte 2: Implementação do algoritmo guloso visto em aula que, dado um conjunto S de pontos, produz um conjunto de pontos arboreamente satisfeito contendo o conjunto S. O conjunto S de pontos sempre será a visão geométrica de uma sequência de buscas. Essa parte da tarefa recebe um inteiro n e uma sequência de inteiros entre 1 e n, e aciona o algoritmo guloso tendo como entrada os pontos da visão geométrica da sequência dada. Se a sequência tiver comprimento m, seu algoritmo deve consumir tempo O(mn).
   Veja a interface que você deve implementar abaixo, e alguns arquivos de entrada e de saída.
   Parte 3: Implementação do algoritmo visto em aula para decidir se um conjunto dado de pontos é arboreamente satisfeito ou não. As coordenadas dos pontos são inteiros positivos. Se as x-coordenadas dos pontos são inteiros entre 1 e n, e há t pontos na coleção dada, sua implementação deve consumir tempo O(tn).
   Veja a interface que você deve implementar abaixo, e alguns arquivos de entrada e de saída.
6. 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.
7. Implementação de florestas dinâmicas usando Euler tour trees, implementadas com ABBB (splay tree, treap, rubro-negra, AVL).
8. Implementação da construção trivial do vetor de sufixos de um texto T (ordene os sufixos de T) e construção linear dos vetores LCP, LLCP e RLCP. 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 O(n lg A) da árvore de sufixos de um texto T com n caracteres, num alfabeto de tamanho A, 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| lg A)) e lista de ocorrências em tempo O(|P| lg A + 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.

• Interfaces a serem implementadas.
• Exemplos de arquivos de entrada de teste para deque e saídas correspondente.
• Exemplos de arquivos de entrada de teste para treap e treap funcional, e saídas correspondentes.
• Exemplos de arquivos de entrada de teste para pilha retroativa e saídas correspondente.
• Exemplos de arquivos de entrada de teste para árvore de segmentos estática e dinâmica e saídas correspondentes.
• Exemplos de arquivos de entrada de teste para a splay tree e treap, e saídas correspondente.
• Exemplos de arquivos de entrada de teste para o algoritmo guloso e de verificação de conjuntos arboreamente satisfeitos, e saídas correspondente.
• Exemplo de arquivo de entrada de teste para o heap cinético 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 a tarefa T8 e saída correspondente.
• Exemplo de arquivo de entrada de teste para a tarefa T9 e saída correspondente.