lista1-PAA

Prévia do material em texto

Lista	de	Exercícios	1	
	
1. Mostrar	 a	 operação	 do	 algoritmo	 de	 ordenação	 por	 inserção	 para	 o	
vetor	A	=	(31,41,59,26,41,58).	
2. Reescreva	 o	 algoritmo	 de	 ordenação	 por	 inserção	 para	 ordenar	 em	
ordem	não-crescente	ao	invés	de	ordem	não-decrescente.	
3. Dois	 algoritmos	 gastam	 n2	 dias	 e	 n3	 segundos,	 respectivamente,	 para	
resolverem	 uma	 instância	 de	 tamanho	 n.	 Em	 alguma	 situação	 o	
algoritmo	quadrático	é	melhor	do	que	o	algoritmo	cúbico?	Justificar.	
4. Considere	 o	 problema	 de	 pesquisar	 um	 elemento	 em	 um	 vetor:		
Entrada:	Uma	sequência	de	n	números	A	=	<a1,	a2,	...,	an	>	e	um	valor	v.		
Saída:	Um	índice	i	tal	que	A[i]	=	v	ou	0	caso	v	não	seja	encontrado	em	
A.	O	 algoritmo	 de	 pesquisa	 linear	 percorre	 o	 vetor	 sequencialmente	
procurando	pelo	valor	v.		
a. Escreva	 o	 algoritmo	 de	 pesquisa	 linear	 (utilize	 a	 pseudo-
linguagem	do	livro	ou	a	linguagem	C)	�.	
b. Considere	que	v	sempre	está	presente	em	A.	Qual	é	a	função	de	
complexidade	do	seu	algoritmo	para	o	número	de	comparações	
de	elementos	no	melhor	e	no	pior	caso.		
5. Seja	[A..n]	um	vetor	com	n	números	distintos.	Se	i	<	j	e	A[i]	>	A[j],	então	
o	par	(i,	j)	é	chamado	uma	inversão	de	A.	
a. Liste	as	inversões	do	vetor	2,	3,	8,	6,	1.	
b. Que	 vetor	 com	 elementos	 do	 conjunto	 1,	 2,	 ...,	 n	 tem	 o	maior	
número	de	inversões?	Quantas	inversões	existem?	c. Qual	 é	 a	 relação	 entre	 o	 tempo	 de	 execução	 do	 algoritmo	 de	
Ordenação	 por	 Inserção	 e	 o	 número	 de	 inversões	 do	 vetor	 de	
entrada?	Justifique	sua	resposta.