IPRJ – PROJETO E ANÁLISE DE ALGORITMOS
LISTA DE EXERCÍCIOS 05
1
) Considere uma Trie não-comprimida criada a partir do seguinte conjunto de
palavras: {banana, goiaba, laranja, limão, abacaxi, abobora, lima, batata}. Baseado
nesta Trie, responda:
a)Qual o altura da Trie?
b)Qual o total de nós folha na Trie?
c) Qual o total de nós internos Trie?
2
) Considere uma Trie comprimida criada a partir do seguinte conjunto de palavras:
{
banana, goiaba, laranja, limão, abacaxi, abobora, lima, batata}. Baseado nesta Trie,
responda:
a)Qual o altura da Trie?
b)Qual o total de nós folha na Trie?
c) Qual o total de nós internos Trie?
3
4
) Existem diversas variantes na escolha do pivot do Algoritmo de Partição utilizado
no Quicksort. Uma dessas variantes, obriga que o tempo para o melhor caso do
Quicksort seja O(n log n). Verdadeiro ou Falso? Justifique sua resposta.
) Um cientista está analisando o DNA de um animal recentemente descoberto para
verificar se ele tem alguma relação com as espécies conhecidas de animais
terrestres. Para isso, o cientista conta com uma base de dados π, composta por
amostras de DNA de N espécies. Porém, comparar manualmente o DNA
desconhecido com as amostras presentes em π levaria mais de 1 ano. Para ajudar o
cientista, você deve desenvolver um algoritmo que seja capaz de resolver esse
problema de forma eficiente. Um fragmento do DNA da espécie desconhecida é
apresentado a seguir: ACAAGATGCCATTGTCCCCCGGCCTCCTGCTGCTGCTGCTCTCC
GGGGCCACGGCCACCGCTGCCCTGCC.
5
) Dentre os diversos algoritmos de ordenação, o Merge Sort básico, isto é, o
algoritmo original sem nenhum aprimoramento extra, é a melhor opção de
