lista2 - Projeto e Analise de Algoritmos
2 pág.

lista2 - Projeto e Analise de Algoritmos


DisciplinaProjeto e Desenvolvimento de Algoritmos58 materiais308 seguidores
Pré-visualização1 página
Projeto e Ana´lise de Algoritmos
Raoni F. S. Teixeira
Lista 1 - Aquecimento
Exerc´\u131cios Selecionados
1. (CLRS) 1 Exerc´\u131cios: 1.1-3, 1.2-1, 1.2-3, 2.2-1, 2.2-2, 2.2-3, 2.2-4 e 2.3-7.
2. (CLRS) Problemas: 1-1 e 2-1.
3. Escreva um algoritmo para ordenar um vetor A com n elementos Experimente a seguinte
estrate´gia: encontre o menor elemento de A e troque-o com o elemento em A[1]. Repita
o processo para os primeiros n\u22121 elementos de A. Qual a complexidade deste algoritmo?
Calcule o tempo de execuc¸a\u2dco exato deste algoritmo.
4. Analise a complexidade de tempo do algoritmo a seguir que determina se um nu´mero de
entrada n e´ primo fazendo diviso\u2dces sucessivas. Este algoritmo e´ polinomial?
Trial-Division(n)
1 if n > 2 and n mod 2 = 0
2 return false
3 i\u2190 3
4 while i \u2264 b\u221anc and n mod i 6= 0
5 i\u2190 i+ 2
6 if i > b\u221anc
7 return true
8 else return false
1Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009) [1990]. Introduction
to Algorithms (3rd ed.). MIT Press and McGraw-Hill. ISBN 0-262-03384-4
1
Projeto e Ana´lise de Algoritmos Lista 01
5. Calcule o tempo de execuc¸a\u2dco exato do algoritmo busca em vetor ordenado a seguir.
Binary-Search(A, n, key)
1 l\u2190 1
2 r \u2190 n
3 while l \u2264 r
4 m\u2190 b (l+r)
2
c
5 if A[m] = key
6 return m
7 if A[m] < key
8 l\u2190 m+ 1
9 else r \u2190 m\u2212 1
10 return \u22121
6. Calcule o tempo de execuc¸a\u2dco do algoritmo de multiplicac¸a\u2dco a seguir.
Multiply(x, y)
1 x\u2190 0
2 while z > 0
3 if z is odd
4 x\u2190 x+ y
5 y \u2190 2y
6 z \u2190 b z
2
c
7 return x
2