DAA 2022/2023 (CC2001) - DCC/FCUP

Aula Prática #06 - Árvores Binárias de Pesquisa Equilibradas
(aulas de 13/04 e 17/04)

Exercícios para submissão

Para efeitos da nota atribuída à resolução de exercícios ao longo do semestre, os exercícios a submeter desta aula são:

[DAA 021] Outra vez bakugans (peso 50%) (exercício do guião principal)
[DAA 022] Árvores red-black (peso 50%) (exercício do guião principal)
[DAA 023] Palavras numeradas (peso 50%) (exercício extra)
[DAA 024] Letras distintas (peso 50%) (exercício de desafio)

Prazo de submissão: 3 de maio (submeter no Mooshak de DAA)

Não se esqueçam que qualquer ajuda que tenham recebido de outros colegas deve ser reconhecida nos comentário do programa que submetem.
Depois do prazo os problemas continuarão disponíveis no Mooshak, mas as submissões não contarão para a sua nota. Relembre que cada aula vale 10% da nota desta componente.
Para um problema contar tem acertar todos os testes. Mesmo que resolva todos os problemas, o máximo numa aula é de 100%.

Conteúdos das teóricas

Nesta aula iremos abordar conceitos de programação dinâmica. Será por isso conveniente ver o que foi falado nas teóricas:

Slides (capítulo "5 - Árvores Binárias de Pesquisa Equilibradas")
Vídeos: (vídeos #14 e #15)

Exercício 1) Usando as implementações de árvores de pesquisa da sua linguagem

Quase todas as linguagens têm uma implementação de árvores de pesquisa equilibradas que garantem operações logarítmicas para pesquisa, inserção e remoção. O objectivo deste exercício é conhecer duas dessas estruturas, que nas versões actuais dos compiladores respectivos são implementadas usando árvores red-black:

Conjuntos de elementos:
- C++: set (ver documentação)
- Java: TreeSet (ver documentação)
Mapa de elementos (associar valores a chaves):
- C++: map (ver documentação)
- Java: TreeMap (ver documentação)

Para os estudantes que usam C, a ideia neste exercício é verem o código de C++. Vão notar que o código é quase igual, incluindo na maneira de ler e escrever (podem pensar no C como um subset do C++), mas que usa pedaços de C++ quando necessário. Para compilarem basta usar g++ na linha de comando em vez de gcc (ex: g++ -Wall -o bst bst.cpp)

Código exemplo de uso de conjuntos e mapas:
- C++: bst.cpp
- Java: BST.java

Façam download do programa respectivo, executem-no e procurem perceber o que o programa faz, seguindo a documentação dada quando necessário.

Exercício 2) Um problema de estruturas de dados

Implemente e submeta uma solução para o problema [DAA 021] Bakugans.

Basicamente o problema pede-lhe para arranjar maneira eficiente (logarítmica) de suportar três operações:
- Inserir elementos num conjunto (podem haver elementos repetidos)
- Retirar o elemento mínimo
- Retirar o elemento máximo
As estruturas de dados set e TreeSet não suportam elementos repetidos, pelo que temos de lidar com isso. Fica a sugestão de usarem uma de duas hipóteses:
- Usar um multiset de C++ que suporta elementos repetidos (ver documentação). Para retirar um elemento podem simplesmente chamar a operação erase sobre um iterador "normal" (não invertido - para irem à posição final podem ir ao .end() e decrementar uma posição).
- Usar um map (C++) ou TreeMap (Java) de inteiros para inteiros onde guardam para cada energia de bakugan o número de elementos com essa energia. Assim, ao adicionar podem incrementar o contador respectivo e ao retirar pode decrementar, apagando-o do mapa se o número chegar a zero.
- Se usar Java, não se esqueça de ler com a classe FastScanner (podem existir 110 mil linhas de input)

Exercício 3) Um problema de implementação de árvores

Implemente e submeta uma solução para o problema [DAA 022] Árvores Red-Black.

Use como ponto de partida o seguinte código base que já tem definida uma estrutura de dados para guardar uma árvore e que já lê o input:

Código inicial para o problema "[DAA 022] Árvores Red-Black"
- C: daa022.c
- C++: daa022.cpp
- Java daa022.java

Concentre-se em criar (e testar) uma função separada para cada uma das propriedades desejadas na árvore:
- É uma árvore binária de pesquisa?
- Obedece à root property?
- Obedece à red property?
- Obedece à black property?

Exercício extra) Usando mapas

Este exercício é um extra, e não é considerado essencial no contexto desta aula. Use-o se quiser consolidar os seus conhecimentos.

Implemente e submeta uma solução para o problema [DAA 023] Palavras Numeradas.

Exercício de Desafio

Todas as semanas vou colocar disponível pelo menos mais um exercício um pouco mais desafiante.

Para esta semana o desafio é mais fácil que os das semanas anteriores, e não envolve nenhum tipo de matéria de que não tenhamos já falado. A dificuldade passa unicamente em como ser eficiente na resposta das queries (que podem ser 100 mil), sendo que por isso um algoritmo quadrático não passará no tempo. O problema está disponível para submissão no Mooshak:

[DAA 024] Letras distintas

Se já tiverem feito tudo e estiverem "presos" neste, e quiserem mesmo fazer o desafio, podem contactar-me para eu "dosear" as dicas.