Lista3-ED1-2014-1

Prévia do material em texto

Estruturas de Dados I
Lista de Exercícios 3
Prof. Marcelo Cezar Pinto
Prof. Leandro M. Zatesko
1
o. semestre de 2014
Exercício 1. Julgue as asserções a seguir como V ou F.
(a) n2 =O(n3);
(b) n3 =O(n2);
(c) O(n2) =O(n3);
(d) O(n3) =O(n2);
(e) n4+n3−2n2+√5n+10−2n =O(n4);
(f) (n+1)2 =O(n2);
(g) (n+1)2 =Ω(n2);
(h) (n+1)2 =Θ(n2);
(i) (n+1)2 = ω(n2);
(j) (n+1)2 = o(n2);
(k) 2n =O(n!);
(l) nn = ω(2n);
(m) n2 =Ω(2n);
(n) en =O(2n);
(o) en =O(2n
2
);
(p) O(2logn) =O(n).
Exercício 2. Escreva um algoritmo em pseudocódigo que recebe dois núme-
ros naturais x e y, codificados em binário, e devolve x + y, também codificado
em binário.
(a) Usando a notação O, qual a complexidade de tempo de seu algoritmo em
função de x e de y?
(b) Qual é o tamanho da entrada de seu algoritmo?
(c) Usando a notação O, qual a complexidade de tempo de seu algoritmo em
função do tamanho da entrada?
(d) Seu algoritmo é logarítmico, quadrático, linear ou exponencial?
Exercício 3. Considere a seguinte versão em pseudocódigo do Crivo de Era-
tóstenes (http://migre.me/iv2BR), o qual, dado um número n > 2, codificado
em binário, devolve todos os números primos menores que n.
CrivoDeEratóstenes(n):
1 se n = 2, devolva ∅;
2 pi← 1;
3 Π[0]← 2;
4 para i de 3 até n− 1, faça;
5 j← 1; primo←V;
6 enquanto j 6 pi e Π[j] 6
√
i e primo, faça:
7 se imod j = 0, então, primo← F;
8 j← j +1;
9 se primo, então:
10 Π[pi]← i;
11 pi← pi +1;
12 devolva Π[0], . . . ,Π[pi − 1].
Algoritmo 1
(a) Faça um teste de mesa para CrivoDeEratóstenes(20).
(b) Implemente o algoritmo em linguagem C e use-o para imprimir todos os
números menores que 100.
(c) Use sua implementação para imprimir num arquivo todos os números
primos que cabem num unsigned int de 32 bits.
(d) Estime a complexidade de tempo do Crivo de Eratóstenes.
(e) Compare sua estimativa com a complexidade mais justa conhecida (pes-
quise!).
Exercício 4. Resolva o problema #1410 — Ele Está Impedido — do URI On-
line Judge.
Exercício 5. Escreva um código na linguagem C para a função que avalia
polinômios, cujo protótipo está indicado a seguir. Não é permitido usar po-
tenciação e seu código deve ter complexidade de tempo linear sobre o grau do
polinômio.
double avalia_polinomio(int n, double coef[], double x);
O polinômio p(x) de grau n está representado por um vetor com n+1 coe-
ficientes:
p(x) =
n∑
i=0
ai · xi = an · xn + an−1 · xn−1 + . . .+ a1 · x + a0
2
Avaliar p(x) significa indicar, dado um valor numérico α para x, qual o
valor de p(α).
Exemplo:
Seja p(x) = 2x2 + x − 5, o valor de p(1) é −2 e o valor de p(2) é 5. O grau do
polinômio é n = 2 e existem 3 coeficientes: a0 = −5, a1 = 1 e a2 = 2.
3