lista2 - Projeto e Analise de Algoritmos

Prévia do material em texto

Projeto e Ana´lise de Algoritmos
Raoni F. S. Teixeira
Lista 1 - Aquecimento
Exerc´ıcios Selecionados
1. (CLRS) 1 Exerc´ıcios: 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−1 elementos de A. Qual a complexidade deste algoritmo?
Calcule o tempo de execuc¸a˜o 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˜es sucessivas. Este algoritmo e´ polinomial?
Trial-Division(n)
1 if n > 2 and n mod 2 = 0
2 return false
3 i← 3
4 while i ≤ b√nc and n mod i 6= 0
5 i← i+ 2
6 if i > b√nc
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˜o exato do algoritmo busca em vetor ordenado a seguir.
Binary-Search(A, n, key)
1 l← 1
2 r ← n
3 while l ≤ r
4 m← b (l+r)
2
c
5 if A[m] = key
6 return m
7 if A[m] < key
8 l← m+ 1
9 else r ← m− 1
10 return −1
6. Calcule o tempo de execuc¸a˜o do algoritmo de multiplicac¸a˜o a seguir.
Multiply(x, y)
1 x← 0
2 while z > 0
3 if z is odd
4 x← x+ y
5 y ← 2y
6 z ← b z
2
c
7 return x
2