Exercicios Basicos Solutions (3)

Prévia do material em texto

*
*
*
Exercícios
Análise de algoritmos & Ordenação
Eduardo Laber
*
*
*
Cap 2- Tardos
Exercício 3
f2 < f3 < f6 < f1 <f4 <f5 
*
*
*
Cap 2- Tardos
Exercício 4
g3 < g4 < g1 < g5 < g2 < g7 < g6
*
*
*
Cap 2- Tardos
Exercício 5
Verdadeiro, assumindo g(n)>=1. 
log f(n) <= log (c.g(n)) <= 
log c + log g(n) <= d log g(n) para d > log c
Falso. f(n)=4n2 e g(n)=n2 
Verdadeiro. f(n)2 <= c2 g(n) 2 < d.g(n) 2 para d>c.
*
*
*
Cap 2- Tardos
Exercício 6
O(n3)
Para mostrar (n3), considere i variando de 1 a n/4 e j variando de n/4 a n
For i=1,2,...,n do
	B[i,i]A[i]
	For i=1,2,...,n
 For j=i+1,i+2,...,n
				B[i,j] B[i,j-1]+A[j]
O(n2)
*
*
*
Cap 2- Tardos
Exercício 8
Enquanto o primeiro vazo não quebra, jogar de alturas n0.5, 2n0.5,…, n0.5 n0.5
 Se ele quebrar ao jogar de altura i.n0.5
Jogar de alturas (i-1)n0.5 , (i-1)n0.5 +1 , (i-1)n0.5 +2, … até ele quebrar
Total de passo <= 2n0.5
*
*
*
Exercícios Extras
Escreva o pseudo-código da operacão de remover o elemento A[i] de um heap armazenado em um vetor A[1..n]
*
*
*
Exercício
Projete um algoritmo para fazer um merge de k listas ordenadas que execute em O(n log k), aonde n é o total de elementos nas k listas
*
*
*
Solução
Seja L(1),...,L(k) as k listas
Remova o primeiro elemento de cada lista e construa um heap com eles: O(k)
Para i=1,...,n
Remova o menor elemento do heap e insira na lista ordenada. Assuma que este elemento veio da lista j; O(log k)
Remova o primeiro elemento da lista L(j) e insira no heap. O(log k)
*
*
*
Exercício
Mostre como ordenar n inteiros no intervalo [1,n2] em tempo linear O(n)
*
*
*
Solução
Solução
Crie vetores B e C com n posições, indexadas de 0 a n-1. Cada posição pode armazenar uma lista de inteiros
Percorra o vetor A inserindo A[i] na lista B[i mod n]. 
Para i variando de 0 a n-1
Para cada elemento x da lista B[i] faça
 Insira x no final da lista C[ x div n]
Para i variando de 0 até n-1
Para cada elemento x da lista C[i] faça
 Imprima [x]
*
*
*
Exercício
A) Mostre que para fazer o merge de duas listas com n elementos é necesário realizar pelo menos 2n-1 comparações no pior caso.
B) Mostre que para fazer o merge de duas listas, uma com n elementos e outra com m elementos, é necesário realizar pelo menos comparações no pior caso.
*
*
*
Solução
Considere as duas listas A= a(1)< ... < a(n) e B=b(1) < ... < b(n) de n elementos
Seja X a ordem 
a(1)<b(1)<a(2)<b(2) <...<a(n)<b(n)
Seja Y(j), j=1,...,n, a ordem idêntica a ordem X, exceto pelo fato que a(j) > b(j)
Seja Z(j), j=2,..,n, a ordem idêntica a ordem X, exceto pelo fato que a(j) < b(j-1)
*
*
*
Solução
Se o algoritmo não comparar a(j) com b(j) ele não tem como diferenciar X de Y(j)
Se o algoritmo não comparar a(j) com b(j-1) ele não tem como diferenciar X de Z(j)
Logo são necessárias 2n-1 comparações
*
*
*
Exercício
Perdido em uma terra muito distante, você se encontra em frente a um muro de comprimento infinito para os dois lados (esquerda e direita). Em meio a uma escuridão total, você carrega um lampião que lhe possibilita ver apenas a porção do muro que se encontra exatamente à sua frente (o campo de visão que o lampião lhe proporciona equivale exatamente ao tamanho de um passo seu). Existe uma porta no muro que você deseja atravessar. Supondo que a mesma esteja a n passos de sua posição inicial (não se sabe se à direita ou à esquerda), elabore um algoritmo para caminhar ao longo do muro que encontre a porta em O(n) passos. Considere que n é um valor desconhecido (informação pertencente à instância). Considere que a ação composta por dar um passo e verificar a posição do muro correspondente custa O(1). 
*
*
*
Solução
p=0
Enquanto não encontrar o muro
	Ande até a posição 2p. Se encontrar o muro no caminho pare
	Ande até a posição -2p. Se encontrar o muro pare
	p++
Fim Enquanto
Assuma que a porta esta na posição + n. Seja p* tal que 2p*-1<n<=2p* 
O algoritmo anda no máximo 3 2p*+1 +4 .2p*+1 para encontrar o muro. Esse valor é menor que 14 n.
*
*
*
Exercício
Analise a complexidade do algoritmo abaixo
Leia(n); 
x  0
Para i  1 até n faça 
	Para j  i+1 até n faça 
		Para k  1 até j-i faça 
			x x + 1
*
*
*
Exercício
Projete o algoritmo mais eficiente que você conseguir para encontrar a mediana de um vetor de n elementos. Análise sua complexidade.
*
*
*
Solução
Ordene os elementos e retorne o elemento n/2 da lista ordenada
Complexidade: O(n log n)
Mais adiante no curso mostraremos um algoritmo O(n)
*
*
*
Exercício
Dizemos que um vetor P[1..m] ocorre em um vetor T[1..n] se  P[1..m]  =  T[s+1..s+m]  para algum s. O valor de um tal s é um deslocamento válido. 
Projete um algoritmo para encontrar todos os deslocamentos válidos de um vetor e analise sua complexidade.
*
*
*
Exercício
Seja A[1..n] um vetor que pode conter números positivos e negativos.
Projete um algoritmo com complexidade O(n3) determinar os índices i e j, com i<=j, tal que A[i] + ...+A[j] é máximo. Tente reduzir a complexidade para O(n2), depois para O(n log n) e então para O(n)
*
*
*
Exercício
Resolvas as equações abaixo encontrando uma função f(n) tal que T(n) = (f(n))
T(n)=2.T(n/2) + n2 para n>1; T(1)=1
T(n) = 2.T(n/2) + n, para n>1; T(1)=1
T(n)=T(n/2) + 1, para n>1; T(1)=1
T(n)=T(n/2) + n, para n>1; T(1)=1
*
*
*
Exercício
Seja uma matriz quadrada A com n2 números inteiros que satisfaz as segintes propriedades
A[i,j] <= A[i+1,j] para 1<=i<=n-1 e 1<=j<=n
A[i,j]<=A[i,j+1], para 1<=i<=n e 1<=j<=n-1
a) Dado um elemento x, descreva um procedimento eficiente para determinar se x pertence a A ou não. Analise a complexidade do algoritmo proposto.
b) Mostre que este problema é (n)
*
*
*
Solução
a) Considere o procedimento abaixo 
Seja y o elemento do canto superior direito da matriz. Compara y e x
Se x>y, descarte a primeira linha e aplique o procedimento recursivamente para matriz restante.
Se x<y, descarte a última coluna e aplique o procedimento recursivamente para matriz restante.
Se x=y devolva a posição de y
*
*
*
Solução
Análise
A cada passo o número de linhas ou de colunas da matriz diminui de 1, portanto o algoritmo executa no máximo 2n passos.
*
*
*
Solução
Lower Bound
Considere a seguinte entrada matriz:
	A[i,j] =0 se i+j<n+1,
	A[i,j] =n+1 se i+j>n+1
	A[i,j] é um inteiro entre 1 e n se i+j=n+1
Se x é um número entre 1 e n que não pertence a A, qualquer algoritmo tem que examinar todas as entradas A[i,j], com i+j=n+1 para concluir que x não esta em A. Logo, o problema é (n)
*
*
*
Exercício
Seja A={a(1) < .... < a(n)} uma lista de números reais. A proximidade entre a(i) e a(j) é definida como |a(i)-a(j)|. 
a) Dados os inteiros j e k, encontre os k elementos de A mais próximos de A[j] em O(k). 
*
*
*
Exercício
Seja A[1..n] um vetor com n números positivos e seja S[i]=A[1]+...+A[i]. 
Encontre o índice i que minimiza 
Minimiza | S[i] – (A[i+1] + ... +A[n]) |
*
*
*
Exercício
Mostre que
*
*
*
Solução