IPRJ – PROJETO E ANÁLISE DE ALGORITMOS
LISTA DE EXERCÍCIOS 09 – REVISÃO P1
1
) Dada a função T(n) = 2n + 1024n3 + 48n, responda verdadeiro ou falso para às
afirmações abaixo.
a) T(n) = O(n3)
b) T(n) = Ω(n)
c) T(n) = Θ(n3)
d) T(n) = O(2n)
e) T(n) = Θ(n3)
f) T(n) = Ω(log n)
2
3
) Supondo que estamos comparando duas implementações de um algoritmo em um
mesmo computador. Para entradas de tamanho n, a implementação A é executada
em 48n3 etapas, enquanto a implementação B é executada em 2n etapas. Para que
valores de n a implementação B supera a implementação A?
) Análise a complexidade do seguinte algoritmo:
int Algorithm1(string s, int n, string t, int m)
{
if (s == t)
return 0;
if (n == 0)
return m;
if (m == 0)
return n;
int[] v0 = new int[m + 1];
int[] v1 = new int[m + 1];
for (int i = 0; i <= m; i++)
v0[i] = i;
for (int i = 0; i < n; i++)
{
v1[0] = i + 1;
for (int j = 0; j < m; j++)
{
int cost = (s[i] == t[j]) ? 0 : 1;
v1[j + 1] = Minimum(v1[j] + 1, v0[j + 1] + 1, v0[j] + cost);
}
for (int j = 0; j <= m; j++)
v0[j] = v1[j];
}
return v1[m];
}
4
5
) A mediana é uma medida de tendência central que separa a metade inferior da
metade superior de um conjunto de dados. Mais concretamente, metade do
conjunto de dados terá valores inferiores ou iguais à mediana e a outra metade
terá valores superiores ou iguais à mediana. Escreva um algoritmo com a
complexidade máxima de O(n log n) que, dado um vetor V com n inteiros positivos,
retorne um novo vetor contendo somente os 6 valores mais próximos da mediana.
) Utilize o algoritmo de Karatsuba baseado na estratégia divisão e conquista para
determine o produto entre os inteiros 2101 e 1130. Apresente todos os passos e
cálculos da sua solução.
6
7
) Todos os algoritmos baseados na estratégia divisão e conquista são recursivos?
Verdadeiro ou Falso? Justifique sua resposta.
) Considerando a existência de uma mochila que suporta até 5 kg e o seguinte
conjunto de itens:
Item 1
Item 2
Item 3
Item 4
Peso
Valor
2
3
3
4
4
5
5
6
Encontre o subconjunto mais valioso de itens que caibam dentro da mochila
utilizando o algoritmo com complexidade O(nW) baseado na estratégia de
programação dinâmica. Apresente a tabela C com os valores calculados pelo
algoritmo e indique o caminho percorrido pelo algoritmo na tabela para encontrar
o subconjunto mais valioso de itens.
8
) 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 a altura da Trie?
b)Qual o total de nós folha na Trie?
c) Qual o total de nós internos da Trie?
9
) 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 (com complexidade O(nm) ou melhor). Um fragmento
do DNA da espécie desconhecida é apresentado a seguir: ACAAGATGCCATTGTCCC
CCGGCCTCCTGCTGCTGCTGCTCTCCGGGGCCACGGCCACCGCTGCCCTGCC.
1
0) Após comparar o DNA de um animal recentemente descoberto com o DNA de
outras espécies, o cientista concluiu que a espécie desconhecida pertence à família
dos primatas antropoides. Agora, o cientista deseja verificar se o animal
desconhecido possui um padrão genético que determina a sua origem.
Considerando o seguinte fragmento de DNA extraído da espécie desconhecida:
T = “ACAAGATGCCATTGTCTCACGGC”
Verifique se o padrão P = “TCACG” ocorre em T utilizando o algoritmo Boyer-
Moore. Construa o vetor L e ilustre todos os alinhamentos e comparações dos
caracteres do padrão P em T.
1
1
1) O número de nós de uma Suffix Trie não-comprimida é O(n). Verdadeiro ou Falso?
Justifique sua resposta.
2) O caixa de um supermercado possui uma quantidade limitada de troco em moedas
de 1 real, 50 centavos, 25 centavos, 10 centavos e 5 centavos. Escreva um
algoritmo que receba um vetor de moedas M (cujos valores armazenados
representam os valores das moedas disponíveis no caixa) e um valor T indicando o
valor do troco que deve ser entregue ao cliente. O algoritmo deve retornar um
vetor de moedas indicando as moedas que devem ser dadas ao cliente para
completar o seu troco usando o menor número possível de moedas. Caso não seja
possível dar o valor exato do troco para o cliente por falta de moedas de menor
valor, deve-se sempre entregar um valor superior. A complexidade do seu
algoritmo deve ser O(n log n) ou melhor.
1
3) A maior subsequência comum entre DCCFDEBDBCDF e CDFFAADBFFFD é DFDBD.
Verdadeiro ou Falso? Justifique sua resposta construindo as matrizes geradas pelo
algoritmo para encontrar a maior subsequência comum baseado em programação
dinâmica.
1
1
4) O algoritmo mais eficiente para resolver o problema da mochila tem complexidade
O(2n). Verdadeiro ou Falso? Justifique sua resposta.
5) Considere a existência de um banco de dados de URLs associadas a um conjunto de
keywords, no seguinte formato:
ID URL
KEYWORDS
1
2
3
http://en.wikipedia.org/wiki/Algorithm
algorithm, definition,
formalization, classification
algorithm, course, lecture,
stanford, coursera
https://www.coursera.org/course/algo
http://en.wikipedia.org/wiki/Sorting_algorithm algorithm, dictionary,
definition, adjective, adverb
.
n
..
...
...
...
...
Seja n o número de registros no banco de dados e m o tamanho de uma keyword a
ser buscada, proponha um algoritmo com complexidade máxima de O(m) para
realizar uma busca e retornar todas as URLs que contenham a keyword buscada.
a) Descreva e ilustre a estrutura de dados utilizada pelo algoritmo.
b) Descreva em linguagem natural ou pseudocódigo o algoritmo de busca
proposto.
1
6) 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.