RESOLUCAO LISTA 1 1

CURSO: CIÊNCIA DA COMPUTAÇÃO
DISCIPLINA: Projeto e Análise de Algorítmo
LISTA 1 DE EXERCÍCIO
1. Qual é o menor valor de n tal que um algoritmo cujo tempo de execução é 100n2 funciona mais rápido que um algoritmo cujo o tempo de execução é 2n na mesma máquina.
2. Considere a ordenação de n números armazenados no arranjo A e utilizando a função abaixo, selection sort, responda:
a) que loop invariante esse algoritmo mantém?,
b) porque ele só precisa ser executado para os n-1 elementos e não para todos o n elementos ?
c) forneça o tempo de execução para o pior caso

3. Responda as seguintes perguntas sobre a função Busca Binaria (aula 3)
a) Que acontece se while (e <= d) for trocado por while (e < d)?
b) Que acontece se while (e <= d) for trocado por while (e <= d+1)?
c) Que acontece se e = m+1 for trocado por e = m?
4. Considerando a função “Busca Binaria”. Mostre que a diferença d - e diminui a cada iteração.
5. A seguinte implementação da busca binária funciona corretamente? Qual o invariante dessa versão? Que acontece se trocarmos “while(e<d-1)” por “while(e<d)”? e = -1; d = n; while (e < d-1) { m = (e + d)/2; if (v[m] == x) return m; if (v[m] < x) e = m; else d = m;
}
return -1;
6. Suponha que o vetor “v” tem 511 elementos e que “x” não está no vetor. Quantas vezes a função busca binária comparará “x” com um elemento do vetor?
7. Se preciso de “t” segundos para fazer uma busca binária em um vetor com “n” elementos, de quanto tempo preciso para fazer uma busca em n2 elementos?

RESPOSTAS DA LISTA 1
1) Seja A um algoritmo cujo tempo de execução é dada pela fórmula 100n2 e B outro algoritmo cujo tempo de execução é 2n , para n=14 temos o tempo de execução de de A em 19.600seg e o tempo de execução de B em 16.384seg, para n=15 temos o tempo de execução de de A em
22.500seg e o tempo de execução de B em 32.768seg. Portanto para n=15 o algoritmo A funciona mais rápido que o algoritmo B.

2) O algoritmo mantém um loop invariante que começa no inicio de cada interação do