AAED - Lista de exercícios 4

Prévia do material em texto

Pós-Graduação em Ciência da Computação Universidade Federal de São Paulo - São José dos Campos
Exerćıcios sobre Algoritmos de Ordenação
AAED — Análise de Algoritmos e Estruturas de Dados
Prof. Jurandy G. Almeida Jr.
1o Semestre de 2020
Exerćıcios
1. Faça uma comparação entre todos os métodos de ordenação estudados em aula com relação a
estabilidade e a ordem de complexidade, levando em consideração o número de comparações
e movimentações.
2. Forneça um esquema simples para tornar estável qualquer algoritmo de ordenação.
3. Dada a sequência de números: 3 4 9 2 5 8 2 1 7 4 6 2 9 8 5 1, ordene-a em ordem crescente,
apresentando a sequência obtida após cada passo, segundo todos os algoritmos de ordenação
vistos em aula.
4. Dada a sequência de números: 8 4 12 9 23 2 4 21 12 17 4 11 14 8 3 2 17 2, ordene-a em ordem
decrescente, apresentando a sequência obtida após cada passo, segundo todos os algoritmos
de ordenação vistos em aula.
5. Que algoritmo de ordenação você usaria para cada um dos seguintes casos:
(a) A ordenação original de elementos com chave idêntica precisa ser mantida.
(b) O tempo de execução não deve apresentar grandes variações para nenhum caso.
(c) A lista de elementos a ser ordenada já está bem próxima da ordenação final.
(d) A lista de elementos a ser ordenada ocupa todo o espaço da memória principal.
6. Um amigo lhe diz que é capaz de ordenar qualquer conjunto de 6 números com no máximo 8
comparações. O seu amigo está falando a verdade ou mentindo? Justifique.
7. No algoritmo de ordenação por inserção, a cada passo é realizada uma procura pelo local de
inserção. Essa procura pode ser realizada sequencialmente ou por busca binária. Analise o
desempenho de ambas as abordagens em relação ao número de comparações e movimentações.
8. Forneça um exemplo de vetor de entrada para demonstrar que o algoritmo de ordenação
por seleção não é um método estável. Mostre os passos da execução do algoritmo até que a
estabilidade seja violada.
9. Reescreva o algoritmo de ordenação da bolha apresentado em aula para que ele efetue passa-
gens sucessivas em direções opostas.
10. Qual método executa mais rápido em um vetor com chaves idênticas: seleção ou inserção?
Justifique sua resposta.
11. Quais são os números mı́nimo e máximo de elementos em um heap de altura h?
12. Onde em um heap máximo o menor elemento poderia residir, supondo-se que todos os ele-
mentos sejam distintos?
13. A sequência {23, 17, 14, 6, 13, 10, 1, 5, 7, 12} é um heap máximo?
14. Execute o procedimento para refazer o heap sobre o arranjo A = {27, 17, 3, 16, 13, 10, 1, 5, 7, 12,
4, 8, 9, 0}, apresentando a sequência obtida após cada passo.
15. Qual é o efeito de chamar o procedimento para refazer o heap, Refaz(A, esq, dir), quando o
elemento A[esq] é maior do que seus filhos?
16. Qual é o efeito de chamar o procedimento para refazer o heap, Refaz(A, esq, dir), sobre um
arranjo A com n = dir − esq + 1 elementos, quando esq > n/2?
17. Execute o procedimento para construir um heap sobre o arranjo A = {5, 3, 17, 10, 84, 19, 6, 22, 9},
apresentando a sequência obtida após cada passo.
18. Por que queremos que o ı́ndice do laço do procedimento para construir um heap, Cons-
troi(A,n), sobre um arranjo A com n elementos diminua de bn/2c até 1, em vez de aumentar
de 1 até bn/2c?
19. Qual é a ordem de complexidade, em termos do número de comparações e movimentações,
do algoritmo de ordenação usando heap sobre um arranjo A com n elementos que já está
ordenado em ordem crescente? E em ordem decrescente?
20. Desenvolva um algoritmo usando um heap de k elementos para encontrar os maiores k números
num grande vetor não ordenado de n números, em que n >> k.
21. Escreva um algoritmo Intercala(x, c1, f1, c2, f2) que presuponha que os elementos em x[c1]
até x[f1] e x[c2] até x[f2] estão ordenados e intercale os dois intervalos em x[c1] até x[f2].
22. Considere a seguinte versão recursiva da ordenação por intercalação que usa a função In-
tercala do exerćıcio anterior. Inicialmente, ela é chamada por MergeSort(x, 0, n − 1).
Reescreva essa função eliminando a recursividade e simplificando-a. Qual a diferença entre a
função resultante e a apresentada aqui?
MergeSort(int *x, int c, int f)
{
int m;
if (c != f) {
m = (f + c) / 2;
MergeSort(x, c, m);
MergeSort(x, m+1, f);
Intercala(x, 0, m, m+1, f);
}
}
23. Sabe-se que o algoritmo Merge-Sort executa no pior caso em tempo Θ(n lg n) e o algoritmo
Insertion-Sort no pior caso em tempo Θ(n2). No entanto, os fatores constantes deste último
o tornam mais rápido que o primeiro para um pequeno valor de n. Assim, faz sentido usar
o algoritmo Insertion-Sort quando os sub-problemas tornam-se suficientemente pequenos.
Considere a seguinte modificação no algoritmo Merge-Sort: nk sub-listas de comprimento
k são ordenadas usando o algoritmo Insertion-Sort e então combinadas (merged) usando
o mecanismo de intercalação do algoritmo Merge-Sort, sendo k o valor a ser determinado.
(a) Mostre que as nk sub-listas, cada uma de comprimento k, podem ser ordenadas pelo
algoritmo Insertion-Sort no pior caso em tempo Θ(nk).
(b) Mostre que as sub-listas podem ser combinadas (merged) no pior caso em tempo
Θ(n lg nk ).
(c) Dado que o algoritmo modificado executa no pior caso em tempo Θ(nk + n lg nk ), qual é
o maior valor assintótico (usando notação Θ) de k como uma função de n para o qual o
algoritmo modificado tem o mesmo tempo de execução assintótico do algoritmo padrão?
(d) Na prática, como o valor de k seria escolhido?
24. Execute a função Particão o método QuickSort sobre o arranjo A = {13, 19, 9, 5, 12, 8, 7, 4,
11, 2, 6, 21}, apresentando a sequência obtida após cada passo.
25. Qual é a ordem de complexidade, em termos do número de comparações e movimentações,
do algoritmo de ordenação por partição sobre um arranjo A com n elementos em que todos
os elementos têm o mesmo valor?
26. Discuta como a escolha do pivô pode influenciar no desempenho do algoritmo de ordenação
por partição. Proponha estratégias para a escolha do pivô, visando melhorar seu desempenho.
27. Um programador inexperiente afirma que a seguinte implementação da função de partição
rearranja o vetor v[p..r], com p < r, e devolve um ı́ndice j ∈ [p, r − 1], tal que v[p..j] ≤
v[j + 1..r].
int Particao(int v[], int p, int r)
{
int q, i, j, t;
i = p;
j = r;
q = (p + r) / 2;
do {
while (v[i] < v[q]) i++;
while (v[j] > v[q]) j--;
if (i <= j) {
t = v[i];
v[i] = v[j];
v[j] = t;
i++;
j--;
}
} while (i <= j);
return i;
}
Mostre um exemplo em que essa função não dá o resultado esperado. E se trocarmos return
i por return i-1? É posśıvel fazer algumas poucas correções de modo que a função dê o
resultado esperado?
28. Para arranjos muito pequenos o algoritmo de ordenação por partição se torna ineficiente,
principalmente no caso de utilizar chamadas recursivas. Modifique o algoritmo visto em aula
para que, quando uma partição tiver m ou menos elementos, o algoritmo de ordenação por
inserção seja utilizado nessa partição.
29. Modifique a função Partição(A, p, r) do método QuickSort de modo que o valor do meio
(mediano) de A[p], A[q] e A[r], em que q = (p+r)/2, seja usado para particionar o vetor. Em
que casos o QuickSort usará esse método com mais eficiência do que a versão apresentada
em aula? Em que casos ele será menos eficiente?
30. Um trabalhador de um depósito precisa rearranjar todas as caixas dispońıveis no estoque de
acordo com algum critério. Nesse caso, o custo de comparações é pequeno comparado com
o custo da troca de posições entre as caixas. Há espaço (extra) suficiente para apenas uma
caixa. Qual algoritmo de ordenação deveria ser utilizado nessa situação? Justifique a sua
resposta.
31. A ordenação por inserção bidirecional é uma modificaçãoda ordenação por inserção
simples. Nela, dado um arranjo A[1..n] com n números inteiros, o primeiro passo é criar um
arranjo auxilar B de tamanho n. Esse arranjo auxiliar atua como uma estrutura circular.
Inicialmente, o primeiro elemento do arranjo de entrada (A[1]) é posicionado no elemento do
meio do arranjo auxiliar (B[n/2]). Assim que um grupo cont́ıguo de elementos estiver no
arranjo auxiliar B, será aberto espaço para um novo elemento deslocando todos os elementos
menores um passo para a esquerda ou todos os elementos maiores um passo a direita. A
escolha do deslocamento é feita para provocar o menor número de movimentações. Escreva
uma função para implementar essa técnica. Qual é o custo de melhor e pior caso desse
algoritmo?
32. Considere a seguinte ordenação por seleção quadrática: divida os n elementos do vetor
em
√
n grupos de
√
n elementos cada. Encontre o maior elemento de cada grupo e insira-
o num vetor auxiliar. Encontre o maior elemento desse vetor auxiliar. Esse será o maior
elemento do vetor. Em seguida, substitua esse elemento dentro do vetor pelo maior elemento
seguinte do grupo a que ele pertencia. Ache novamente o maior elemento do vetor auxiliar.
Esse será o segundo maior elemento do vetor. Repita o processo até que o arquivo esteja
ordenado. Escreva uma função para implementar uma ordenação por seleção quadrática o
mais eficiente posśıvel. Qual é o custo de melhor e pior caso desse algoritmo?
33. Um torneio é uma árvore estritamente binária quase completa na qual cada nó não-folha
contém o maior de dois elementos em seus dois filhos. Por conseguinte, o conteúdo das folhas
de um torneio determina totalmente o conteúdo de todos os seus nós. Um torneio com n
folhas representa um conjunto de n elementos.
(a) Desenvolva um algoritmo Insira(t, n, elt) para incluir um novo elemento elt num torneio
contendo n folhas representadas por um vetor t.
(b) Desenvolva um algoritmo RemoveMax(t, n) para eliminar o elemento máximo de um
torneio com n elementos, substituindo a folha contendo o elemento máximo por um valor
artificial menor que qualquer elemento posśıvel (por exemplo, -1 num torneio de inteiros
não-negativos) e reajustando, em seguida, todos os valores no caminho a partir dessa
folha até a raiz.
34. A ordenação por transposição de par-impar ocorre da seguinte maneira. Dado um
arranjo A[1..n] com n números inteiros, percorra esse arranjo várias vezes. Na primeira
passagem, compare A[i] com A[i+ 1] para todo i ı́mpar. Na segunda passagem, compare A[i]
com A[i+ 1] para todo i par. Toda vez que A[i] > A[i+ 1], troque A[i] e A[i+ 1] de posição.
Continue alternando dessa maneira até que o vetor esteja ordenado.
(a) Qual é a condição para o término da ordenação?
(b) Escreva uma função para implementar essa técnica.
(c) Qual é o custo de melhor e pior caso desse algoritmo?
35. A ordenação por inserção intercalada é a seguinte:
Passo 1: Para todo i par entre 0 e n − 2, compare x[i] a x[i + 1]. Posicione o maior na
próxima posição de um vetor large e o menor na próxima posição de um vetor small. Se n
for ı́mpar, posicione x[n − 1] na última posição do vetor small. O vetor large é de tamanho
ind, em que ind = (n− 1)/2; e o vetor small é de tamanho ind ou ind + 1, dependendo de n
ser ı́mpar ou par.
Passo 2: Ordene o vetor large usando a inserção intercalada recursivamente. Sempre que um
elemento large[j] for transferido para large[k], small[j] será também movido para small[k].
No final desse passo, large[i] ≤ large[i + 1] para todo i menor que ind, e small[i] ≤ large[i]
para todo i menor ou igual a ind.
Passo 3: Copie small[0] e todos os elementos de large em x[0] a x[ind].
Passo 4: Defina o inteiro num[i] como (2i + 1 + (−1)i)/3. Começando com i = 0 e conti-
nuando de 1 em 1 enquanto num[i] ≤ (n/2) + 1, insira os elementos small[num[i + 1]] até
small[num[i] + 1] em x, por vez, usando a inserção binária. Por exemplo, se n = 20, os su-
cessivos valores de num são num[0] = 1, num[1] = 1, num[2] = 3, num[3] = 5 e num[4] = 11,
que é igual a (n/2) + 1. Dessa forma, os elementos de small serão inseridos na seguinte or-
dem: small[2], small[1]; em seguida, small[4], small[3]; depois small[9], small[8], small[7],
small[6], small[5]. Nesse exemplo, não existe small[10].
Escreva uma função para implementar essa técnica.
36. Considere o problema de busca de um elemento em um vetor de tamanho n, cuja resposta é
o ı́ndice da posição do elemento no vetor ou −1 se o elemento não estiver no vetor. Qual é a
cota inferior para esse problema no modelo de árvore de decisão binária? Justifique.
37. Considere um vetor A com n números reais. Projete um algoritmo de complexidade O(n)
para o problema de determinar um número que não está no vetor. Mostre que esse problema
tem cota inferior Ω(n), e portanto seu algoritmo é ótimo.
38. Para cada um dos problemas listados abaixo: (1) projete um algoritmo ótimo para resolver
esse problema; e (2) prove que o algoritmo apresentado é ótimo.
(a) Considere um arranjo A com n elementos não ordenados. O problema é encontrar o
maior valor dentre estes n elementos.
(b) Considere um arranjo A com n elementos não ordenados. O problema é encontrar o
maior e o menor valores dentres estes n elementos.
(c) Considere um arranjo A com n elementos não ordenados. O problema é ordenar estes n
elementos usando somente comparações entre chaves.
(d) São dados 2n elementos distintos distribúıdos em dois arranjos A e B, cada um com n
elementos ordenados, tal que A[0] < A[1] < ... < A[n − 2] < A[n − 1] e B[0] < B[1] <
... < B[n − 2] < B[n − 1]. O problema é encontrar o n-ésimo menor valor dentre estes
2n elementos.
39. Considere o seguinte problema: você tem n jarros de cor azul e n de cor vermelha. Cada jarro
de cor azul comporta uma quantidade de água diferente de todos os demais jarros azuis. A
mesma propriedade vale para os jarros vermelhos. Além disso, existe, para cada jarro de cor
azul, um jarro de cor vermelha que comporta exatamente a mesma quantidade de água do
azul. Sua tarefa é formar n pares de jarros de cores distintas, mas de mesma capacidade. Você
só pode comparar as capacidades de jarros de cores distintas e usando a seguinte operação:
enche o jarro vermelho e despeja a água do vermelho no azul, determinando assim se a
capacidade do azul é maior, igual, ou menor que a do vermelho.
(a) Projete um algoritmo que use Θ(n2) comparações para agrupar os jarros em pares.
(b) Prove uma cota inferior Ω(n log n) para o número de comparações que um algoritmo
para esse problema deve efetuar no modelo de árvore de decisão binária.
(c) Dê um algoritmo de complexidade O(n log n) no caso médio para este problema. Qual é
o número de comparações no pior caso do seu algoritmo?
40. Considere o problema de construir um vetor ordenado C[1..m+n] composto de m+n números
distintos obtidos de dois vetores ordenados A[1..m] e B[1..n].
(a) Determine uma cota inferior para esse problema, expressa em notação Ω.
(b) Projete um algoritmo ótimo para resolver esse problema, ou seja, um algoritmo que
tenha a cota inferior do problema como limite assintótico superior de seu tempo de
execução de pior caso.
41. Um vetor A[1..n] contém n números distintos aleatoriamente ordenados. Suponha que cada
permutação dos n números é igualmente provável. Qual é a esperança do ı́ndice do maior
elemento do vetor? Qual é a esperança do ı́ndice do menor elemento do vetor?
42. Seja A[1..n] um vetor de n números distintos. Se i < j e A[i] > A[j], então o par (i, j) é
chamado de uma inversão de A. Suponha que os elementos de A formam uma permutação
aleatória uniforme de 〈1, 2, . . . , n〉. Utilize variáveis aleatórias para calcular o número esperado
de inversões.
43. No algoritmo Select-BFPRT, os elementos de entrada são divididos em grupos de 5. O
algoritmo irá executar em tempo linear se eles forem divididos em gruposde 7? Argumente
que o algoritmo não executa em tempo linear se grupos de 3 forem utilizados.
44. Sabendo que é posśıvel determinar a mediana de um conjunto de n elementos em tempo
O(n) no pior caso, use esse algoritmo como “caixa-preta” para projetar um algoritmo que
determina qual é o k-ésimo menor elemento do conjunto em tempo O(n) no pior caso.
45. Descreva um algoritmo de complexidade de pior caso O(n) que determina, para um conjunto
de n elementos e um inteiro k, k ≤ n, os k elementos mais próximos da mediana do conjunto.
Você pode usar como “caixa-preta” o algoritmo linear para encontrar a mediana de um
conjunto.
46. Seja X e Y dois vetores ordenados de n elementos. Projete um algoritmo de complexidade
O(log n) no pior caso para encontrar a mediana de todos os 2n elementos nos vetores X e Y .
47. Seja X e Y dois vetores ordenados de m e n elementos, respectivamente. Projete um algoritmo
de complexidade O(logm + log n) no pior caso para encontrar o k-ésimo menor elemento da
união desses dois vetores.
48. Execute o algoritmo de ordenação por contagem sobre o arranjo A = {6, 0, 2, 0, 1, 3, 4, 6, 1, 3, 2},
apresentando a sequência obtida após cada passo.
49. Sejam n registros armazenados em um vetor A. Proponha um algoritmo para ordenar o vetor
em tempo linear que não necessite de espaço adicional para os seguintes casos.
(a) Todas as chaves são ou 0 ou 1.
(b) Todas as chaves são números inteiros no intervalo [0..k] em que k é uma constante.
50. Suponha que o ı́ndice do penúltimo laço do algoritmo de ordenação por contagem visto
em aula, Contagem(A,n, k), sobre um vetor A[1..n] em que cada A[i] está em {0, . . . , k},
aumente de 1 até n, em vez de diminuir de n até 1. O algoritmo funciona corretamente? O
algoritmo modificado é estável?
51. O seguinte algoritmo promete rearranjar o vetor A[1..n] em ordem crescente supondo que
cada A[i] está em {0, . . . , k}. O algoritmo funciona corretamente? Qual é a sua ordem de
complexidade, levando em consideração o número de operações de atribuição?
C-Sort(A,n, k)
1 para i← 0 até k faça
2 C[i]← 0
3 para j ← 1 até n faça
4 C[A[j]]← C[A[j]] + 1
5 j ← 1
6 para i← 0 até k faça
7 enquanto C[i] > 0 faça
8 A[j]← i
9 j ← j + 1
10 C[i]← C[i]− 1
52. O seguinte algoritmo promete rearranjar o vetor A[1..n] em ordem crescente supondo que
cada A[j] está em {1, . . . , k}. O algoritmo funciona corretamente? Estime a sua ordem de
complexidade, levando em consideração o número de comparações e movimentações.
Vito-Sort(A,n, k)
1 i← 1
2 para a← 1 até k − 1 faça
3 para j ← i até n faça
4 se A[j] = a então
5 A[j]↔ A[i] . troca
6 i← i + 1
53. Execute o algoritmo de ordenação digital sobre a seguinte lista de palavras em inglês: COW,
DOG, SEA, RUG, ROW, MOB, BOX, TAB, BAR, EAR, TAR, DIG, BIG, TEA, NOW,
FOX, apresentando a sequência obtida após cada passo.
54. Mostre como ordenar n inteiros no intervalo de 1 a n2 − 1 em tempo O(n).
55. Mostre como ordenar n inteiros no intervalo de 1 a n3 − 1 em tempo O(n).
56. Descreva um algoritmo eficiente para ordenar n inteiros que representam CPFs de pessoas.
Qual é a complexidade de tempo e de espaço de seu algoritmo?
57. Descreva como você modificaria o algoritmo de ordenação digital para ordenar cadeias de
caracteres de tamanho diferente. Por exemplo, a chave “carrega” deve estar antes de “carre-
gamento” e depois de “borboleta”.