Estruturas de Dados Avançadas

Segundo semestre de 2021

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 ABB simples ou funcional (persistente) ou parcialmente persistente pela técnica do node copying.
3. Implementação de pilha retroativa.
   Se a implementação usar uma ABB simples (não balanceada), vale nota parcial.
4. Implementação de fila de prioridade parcialmente retroativa.
   Se a implementação usar uma ABB simples (não balanceada), vale nota parcial.
5. Implementação de árvore de segmentos estática e dinâmica.
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 uma árvore splay e de uma treap, com contadores para comparação do número de nós acessados.
8. Implementação de florestas dinâmicas usando Euler tour trees, implementadas com uma splay tree ou uma treap.
9. 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 em tempo O(|P| + log |T|), usando estes vetores (busca simples, número de ocorrências e lista de ocorrências).
10. 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, usando a árvore de sufixos, do número de ocorrências de uma palavra P no texto T em tempo O(|P| + log |A|), onde A é o alfabeto.
11. 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 pilha e saída correspondente. Faça algo semelhante para cada uma das EDs que você implementar.

Datas e horários da segunda entrevista:

1. Sexta, 24/9, às 9h30: Luca Lopes Barcelos
2. Sexta, 24/9, às 14h: Bruno Hideki Akamine
3. Sexta, 24/9, às 14h15: Joao Vitor Magalhaes Leite
4. Sexta, 24/9, às 14h45: Arthur Prado de Fazio
5. Sexta, 24/9, às 15h: Ygor Sad Machado
6. Segunda, 27/9, às 15h45: Marcos Siolin Martins
7. Sexta, 1/10, às 9h20: Eduardo Ribeiro Silva de Oliveira
8. Sexta, 1/10, às 16h00: Gustavo Santos Moraes
9. Sexta, 1/10, às 16h20: Luã Nowacki Scavacini Santilli
10. Sexta, 1/10, às 16h40: Miguel Pereira Ostrowski
11. Segunda, 4/10, às 15h50: Lucas Hiroshi Hanke Harada
12. Segunda, 4/10, às 16h10: Marco Alves de Alcantra
13. Segunda, 4/10, às 16h30: Maximilian Cabrajac Goritz

1. Quinta, 9/9, às 16h30: Felipe Kallas Silva
2. Quinta, 9/9, às 17h: Bruno Hideki Akamine
3. Quinta, 9/9, às 17h30: Arthur Prado de Fazio
4. Quinta, 9/9, às 18h: Ygor Sad Machado
5. Sexta, 10/9, às 14h: Lucas Hiroshi Hanke Harada
6. Sexta, 10/9, às 14h30: Marco Alves de Alcantra
7. Sexta, 10/9, às 15h: Maximilian Cabrajac Goritz
8. Sexta, 10/9, às 15h30: Miguel Pereira Ostrowiski
9. Sexta, 10/9, às 16h: Marcos Siolin Martins
10. Sexta, 10/9, às 16h30: Eduardo Ribeiro Silva de Oliveira
11. Sexta, 10/9, às 17h: Rodrigo Orem da Silva
12. Sexta, 10/9, às 17h30: Gustavo Santos Morais
13. Sexta, 10/9, às 18h: Felipe Castro Noronha
14. Terça, 14/9, às 14h: Davi de Menezes Pereira
15. Terça, 14/9, às 14h30: Henrique Araujo de Carvalho
16. Terça, 14/9, às 17h: Matheus Barbosa Silva
17. Terça, 14/9, às 17h30: Guillermo Enrique Junchaya Heredia
18. Terça, 14/9, às 18h: Arthur Correia Gomes
19. Quarta, 15/9, às 18h: Vitor Antonio Costa Zaninotto
20. Quinta, 16/9, às 14h: Lua Nowacki Scavacini Santilli
21. Quinta, 16/9, às 14h30: Gustavo de Medeiros Carlos
22. Quinta, 16/9, às 15h: Leonardo Costa Santos
23. Quinta, 16/9, às 16h: Daniela Favero
24. Quinta, 16/9, às 16h30: Antonio Marcos Shiro Arnauts Hachisuca
25. Quinta, 16/9, às 17h: Eduardo Sandalo Porto
26. Quinta, 16/9, às 17h30: Julia Leite da Silva
27. Quinta, 16/9, às 18h: João Vitor Magalhães Leite (Não compareceu.)
28. Quinta, 16/9, às 18h30: William Hideki Kondo