MO640 – Biologia Computacional
Ata de Exercícios (18/10/2004)
Autor: José Augusto Amgarten Quitzau - RA962569.

Os exercícios desta aula correspondem ao artigo:
Meidanis e Telles 2004 - TELLES, G. P.; MEIDANIS, J. Building PQR Trees in Almost-Linear Time. Submetido a publicação, 2004.


1. Escreva cada nó novo das operações das Figuras 3 a 6 do artigo de Telles e Meidanis, 2004 em função dos nós antigos e de S, usando as operações de intersecção, união não disjunta e diferença não contida.
R.:

Figura 3.
Figura 4.
Figura 5.	Não há nós novos nesta figura.
Figura 6.	Não há nós novos nesta figura.

Obs.: Na Figura 3, equação para v, v' indica o nó v antigo.

2. Escreva uma coleção de tamanho mínimo que corresponda à árvore PQR da Figura 2 do artigo de Meidanis, Porto e Telles, 1998. O tamanho de uma coleção é dado pela soma dos tamanhos dos conjuntos que a compõe.
R.: {be, bf, dg, dh, ef, befh}