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  
algoritmo segundo o critério de melhor caso (quando o vetor já está ordenado).  
Verdadeiro ou Falso? Justifique sua resposta.  
6
) A maior subsequência comum entre DCCFDEBDBCDF e CDFFAADBFFFD é DFDBD.  
Verdadeiro ou Falso? Justifique sua resposta construindo as matrizes geradas pelo  
algoritmo baseado em programação dinâmica.  
7
8
) Seja L um vetor com n elementos, onde cada elemento de L vale A, B ou C. Então, é  
possível ordenar L com complexidade de pior caso O(n)? Como?  
) Considere o problema P definido da seguinte forma:  
Entrada: uma palavra P com 3 caracteres e um texto T com n caracteres;  
Saída: SIM se alguma permutação da palavra P aparece no texto T e NÃO,  
caso contrário.  
Escreva o pseudocódigo de um algoritmo para resolver este problema e analise a  
sua complexidade de pior caso em função de n. Caso seja necessário, utilize T[i] e  
P[i] para acessar o i-ésimo caracter do padrão P e do texto T, respectivamente.  
9
1
) O algoritmo Counting Sort utiliza um vetor auxiliar C para armazenar o número de  
ocorrências de valores no vetor de entrada. Considerando vetor de entrada A = {2,  
1
, 5, 2, 4, 4, 5, 4, 3, 4, 1, 3, 0, 1, 3, 0}, o conteúdo armazenado no vetor C após a  
execução do Counting Sort é C = {0, 2, 5, 7, 11, 14}. Verdadeiro ou Falso? Justifique  
sua resposta.  
0) Escreva um algoritmo de tempo O(n log n) que, dado um conjunto S de n inteiros e  
outro inteiro x, determine se existem ou não dois elementos em S cuja soma seja  
exatamente x.