Lista de exercicio 8 Analise e Projeto de Algoritmos

Aluno: Vinícius Barcelos Silva
Matricula: 108251
Lista 8 8.1­1
Será θ(n) ou mais precisamente dizendo, será n­1. Pois este será o número minimo de comparações que precisaremos realizar para verificar se o array está ordenado para retorna­lo. 8.2­3
O COUNTING­SORT vai funcionar corretamente, mas a modificação fara com que na saída do array ordenado os elementos iguais estejam na ordem inversa. 8.2­4
Como mostrado no COUNTING­SORT, podemos produzir um array C de tal modo que C[i] tem o número de elementos menor ou igual a i, para contarmos o número de inteiros em [a, … , b], consideramos o C[b] ­
C[a­1], assim teremos o numero de inteiros que se encontram no intervalo pedido. 8.3­2
O insertion sort e o merge sort são estáveis e o heapsort e o quicksort são instáveis.
Para tornarmos qualquer algoritmo estável, podemos mapear um array em pares de arrays, onde o primeiro elemento de cada par é o elemento original e o segundo será o seu indice. Aplicando a ordenação lexicográfica (ordem alfabetica), nós teremos um esquema com θ(n) espaço adicional. 8.3­4
Usando o radix sort, no caso de termos 2 digitos na base n. Logo teremos o tempo de execução do radix sort sendo: θ(2(n + n))

= θ(4n) = θ(n) .

8.3­5
Como se trata de um problema que se torna exponencial, teremos de executar θ(k

d

) passos no pior caso.

O operador precisaria de θ(nk) pilhas para controlar no pior caso. 8.4­2
O tempo de execução do bucket sort sera θ(n2) no pior caso, um exemplo do pior caso seria quando todos os elementos estivessem no mesmo balde e totalmente desordenados.
Podemos usar o merge sort ou o heapsort para fazer com que o tempo de execução no pior caso seja O(n lg n).