Tp Aeds

Projeto e An´lise de Algoritmos a UFMG/ICEx/DCC

Lista de Exerc´ ıcios 1
P´s-Gradua¸˜o em Ciˆncia da Computa¸˜o o ca e ca

1o Semestre de 2010

Observa¸˜es: co • As quest˜es, a seguir, tratam do projeto de algoritmos. CLSR ´ a referˆncia do exerc´ no livro-texto. o e e ıcio
• Das primeiras 18 quest˜es, escolha oito para resolver e dos ultimos cinco problemas escolha dois problemas o ´ para implementar.
Quest˜o 1 [CLSR, Ex 2.2-4, pg 27] a Como podemos modificar quase que qualquer algoritmo para ter um bom tempo de execu¸˜o para o melhor caso? ca Quest˜o 2 [CLSR, Ex 2.3-4, pg 37] a O algoritmo de Ordena¸˜o por Inser¸˜o pode ser expresso como um procedimento recursivo da seguinte forma: ca ca para ordenar A[1 . . n], ordena-se recursivamente A[1 . . n − 1] e ent˜o insere-se A[n] no vetor ordenado A[1 . . n − 1]. a Escreva uma equa¸˜o de recorrˆncia para o tempo de execu¸˜o dessa vers˜o recursiva, resolva essa equa¸˜o e ca e ca a ca indique o crescimento da pilha de recurs˜o. a Quest˜o 3 [CLSR, Ex 2.3-6, pg 37] a Observe que o la¸o while das linhas 5–7 do procedimento Insertion-Sort (apresentado na se¸˜o 2.1 do livro c ca
CLSR, pg. 24 e mostrado abaixo) usa uma pesquisa linear para percorrer de tr´s para frente o vetor ordenado a A[1 . . j − 1]. Pode-se usar a pesquisa bin´ria para melhorar o tempo de execu¸˜o no pior caso do Insertion-Sort a ca para Θ(n log n)?
Insertion-Sort(A)
1 for j ← 2 to length[A]
2
do key ← A[j]
3
£ Insert A[j] into the sorted sequence A[1 . . j − 1].
4
i←j−1
5
while i > 0 and A[i] > key
6
do A[i + 1] ← A[i]
7
i←i−1
8
A[i + 1] ← key
Quest˜o 4 [CLSR, Ex 2.3-6, pg 37] a Descreva um algoritmo com complexidade de tempo Θ(n log n) que, dado um conjunto S de n inteiros e um outro inteiro x, determina se existe ou n˜o dois elementos de S cuja soma ´ exatamente x. a e
Quest˜o 5 [CLSR, Problema 2-1, pg 37] a (Ordena¸˜o por Inser¸ao em pequenos vetores no Mergesort.) Sabe-se