Projeto e Análise de Algoritmos – Profa. Dr. Jerusa Marchi
Lista de exercícios 1
Luiz Henrique Zambom Santana
Parte 1
Capítulo 1 - Exercícios 1.1-1, 1.1-2, 1.1-3, 1.1-4, 1.1-5, 1.2-2, 1.2-3
Capítulo 2 - Exercícios 2.1-4, 2.2-2, 2.3-6 e Problema 2-2.
1.1-1. Give a real-world example that requires sorting or a real-world example that requires computing
a convex hull.
Um exemplo do mundo real que requer ordenação é organizar os candidatos de um concurso público de
acordo com seu desempenho. Por outro lado, calcular um casco convexo pode ser necessário para
aplicações em ferramentas CAD.
1.1-2. Other than speed, what other measures of efficiency might one use in a real-world setting?
Outras exemplos de eficiencia de software no mundo real são segurança, facilidade de uso (userfriendness), escalabilidade e custo de desenvolvimento.
1.1-3. Select a data structure that you have seen previously, and discuss its strengths and limitations.
A lista ligada linear possui como principal limitação a necessidade de se percorrer toda a lista para
saber se um valor está presente entre seus elementos, a sua principal vantagem em relação à estruturas
estáticas - como matrizes e vetores -, é o fato de que seu tamanho não precisa ser definido no momento
de compilação dos programas que as usem, mas sim podem crescer o diminuir dinâmicamente durante
a execução desse programa.
1.1-4. How are the shortest-path and traveling-salesman problems given above similar? How are they
different?
Ainda que ambos sejam problemas que possam ser modelados com grafos, o problema de menor
caminho (SP) é apena uma parte do problema do caixeiro viajante (TSP). O problema do caixeiro
viajante adiciona ao problema do menor caminho a necessidade de que cada ponto seja visitado
exatamente uma vez e que se retorne ao ponto de início. Isso faz com que o segundo problema seja NPdifícil - ou seja, não se sabe se há uma solução que cresça em tempo polinomial para o mesmo. Isto
porque, o problema do caixeiro viajante contém uma permutação de todos os nós do grafo de caminho,
fazendo com que o espaço de busca do menor caminho aumente de forma exponencial.
1.1-5. Come up with a real-world problem in which only the best solution will do. Then come up with
one in which a solution that is “approximately” the best is good enough.
Um problema que envolva, por exemplo, calcular o saldo de uma conta bancária ao final de uma
sequência de transações só é aceitável se oferecer a melhor solução (mais correta) possível. Por outro
lado, o problema de previsão de temperatura para uma cidade aceita soluções que ofereçam resultados
apenas próximos à temperatura verificada.
1.2-2. Suppose we are comparing implementations of insertion sort and merge sort on the same
machine. For inputs of size n , insertion sort runs in 8n^2 steps, while merge sort runs in 64n lg n
steps. For which values of n does insertion sort beat merge sort?
A melhor forma de descrever esse problema é através da seguinte inequação:
8n^2< 64n lg n
n< 8 lg n
n/8< lg n
2^(n/8)<n
2^(n/8)-n<0
Assim, o insertion sort é melhor que o merge sort para os seguintes valores 2≤n≤43
1.2-3. What is the smallest value of n such that an algorithm whose running time is 100*n^2 runs faster
than an algorithm whose running time is 2^n on the same machine?
A melhor forma de descrever esse problema é através da seguinte inequação:
100*(n^2)<2^n
log(100*n^2)<log(2^n)
log100+log(n^2)<log(2^n)
log100+2*logn<nlog2
2+2*log n < n*0.3010
Assim, o primeiro algoritmo é executado mais rapidamente a partir de n=15
2.1-4. Consider the problem of adding two n-bit binary integers, stored in two n-element arrays A and
B. The sum of the two integers should be stored in binary form in an (n+1)-element array C. State the
problem formally and write pseudocode for adding the two integers.
Pseudocódigo:
C ← [1 ... n + 1] // C está preenchido com zeros.
for i ← 1 to n
do sum ← A[i] + B[i] + C[i]
C[i] ← sum % 2
C[i + 1] ← sum / 2 //divisão de inteiros
output C
2.2-2. Consider sorting n numbers stored in array A by first finding the smallest element of A and
exchanging it with the element in A[1]. Then find the second smallest element of A, and exchange it
with A[2]. Continue in this manner for the first n-1 elements of A . Write pseudocode for this algorithm,
which is known as selection sort . What loop invariant does this algorithm maintain? Why does it need
to run for only the first n 1 elements, rather than for all n elements? Give the best-case and worst-case
running times of selection sort in Ω notation.
SELECTION-SORT(A)
for i ← 1 to length(A) - 1
do key ← i
//encontre o i-ésimo menor elemento de A
for j ← i to length(A)
do key2 ← j
if A[key] > A[key2]
then key ← key2
//troque o i-ésimo menor elemento e o i-ésimo elemento de A
temp ← A[key]
A[key] ← A[i]
A[i] ← temp
Loop invariante: No início da primeira iteração para o loop das linhas o sub-array A[1.. i-1] consiste
dos menores elementos de A organizados de forma ordenada.
O algoritmo só deve ser executado para os primeiros n-1 elementos, pois se o último elemento é menor
que algum outro ele será trocado em alguma iteração.
O melhor e o pior caso são Θ(n^2) porque o comprimento inteiro do vetor deve ser buscado para todo
elemento do vetor, não importa a ordem inicial dos elementos.
2.3-6. Observe that the while loop of lines 5–7 of the INSERTION-SORT procedure in Section 2.1 uses
a linear search to scan (backward) through the sorted subarray A[1.., j-1]. Can we use a binary search
(see Exercise 2.3-5) instead to improve the overall worst-case running time of insertion sort to Ω (n lg
n)?
Essa modificação não ajudaria a diminuir a complexidade do algoritmo, pois, mesmo com a busca
binária, ainda seria necessário mover elementos após cada inserção, o que faz com que o algoritmo
continue Ω (n^2).
Problema 2-2. Bubblesort is a popular, but inefficient, sorting algorithm. It works by repeatedly
swapping adjacent elements that are out of order.
(algoritmo omitido)
a. Let [A] denote the output of BUBBLESORT(A). To prove that BUBBLESORT is correct, we need to
prove that it terminates and that A'[1]≤A'[2]≤…≤A'[n] where n=length[A]. What else must be proved
to show that BUBBLESORT actually sorts?
Nós precisamos também provar que os elementos A' são apenas uma permutação dos elementos de A.
b. State precisely a loop invariant for the for loop in lines 2-4, and prove that this loop invariant holds.
Your proof should use the structure of the loop invariant proof presented in this chapter.
O loop invariante para as linhas 2-4 pode ser definido da seguinte forma: o sub-array A[j..n] vai ter o
menor elemento na primeira posição, sendo que esse sub-array será uma permutação de A original.
•
•
Inicialização: inicialmente j=n, então A[j..n]=A[n], que está trivialmente consistente com o loop
invariante.
Manutenção: durante o loop invariante, A[j] é o menor elemento de A[j..n]. Se A[j]<A[j-1]
ambos terão suas posições trocadas, que garante que A[j-1] é o menor elemento de A[j-1..n], o
que mantem o loop invariante até a próxima iteração.
•
Fim: o loop irá terminar quando j=i, assim nesse momento A[i] será o menor elemento de
A[i..n].
c. Using the termination condition of the loop invariant proved in part (b), state a loop invariant for
the for loop in lines 1-4 that will allow you to prove inequality (2.3). Your proof should use the
structure of the loop invariant proof presented in this chapter.
O loop invariante para as linhas 1-4 pode ser definido da seguinte forma: o sub-array A[1..i-1] consiste
dos elementos de A[1..n] ordenados, cada um desses elementos serão menores o iguais que a sub-array
A[i..n] e esse array será apenas uma permutação do original.
•
•
•
Inicialização: inicialmente i=1, então A[1..i]=A[1], que está trivialmente consistente com o loop
invariante.
Manutenção: durante o loop invariante, A[1..i-1] está ordenado. Quando o loop interno termina,
A[i] será o menor elemento de A[i..n], que significa que A[1..i] está ordenado, mantendo o loop
invariante até a próxima iteração.
Fim: o loop irá terminar quando i=n, assim nesse momento todo array A estará ordenados.
d. What is the worst-case running time of bubblesort? How does it compare to the running time of
insertion sort?
O loop externo deve ser executado n vezes (ou seja, para todos elementos do array), enquanto o loop
interno percorre todo o array uma vez, parte do array outras n-i vezes. O tempo de execução do bubbe
sort é o mesmo do insert sort, ou seja Θ(n^2).
Parte 2
Capítulo 3 - Problema 3-2 , 3-3 (a)
Capítulo 4 - Exercícios 4.3-1, 4.3-2, 4.3-3, 4.3-6 (usando expansão telescópica)
4.4-1, 4.4-2, 4.4-3, 4.4-4, 4.4-5, 4.4-6, 4.4-7, 4.5-1, 4.5-3, 4.5-4, 4.5-5.
Problema 3-2. Indicate, for each pair of expressions (A, B) in the table below, whether A is O, o, Ω, ω,
Θ of B. Assume that k ≥ 1, > 0, and c > 1 are constants. Your answer should be in the form of the table
with “yes” or “no” written in each box.
A tabela fica da seguinte forma:
A
B
O
o
Ω
ω
Θ
lgkn
n
sim
sim
sim
não
não
n^k
n^c
sim
sim
sim
não
não
SQRT(n)
n^(sin n)
não
não
não
não
não
2^n
2^(n/2)
não
não
sim
sim
não
n^(lg c)
c^(lg n)
sim
não
sim
não
sim
lg(n!)
lg(n^n)
sim
não
sim
não
sim
Problema 3-3 (a). Rank the following functions by order of growth; that is, find an arrangement g1, g2,
. . . , g30 of the functions satisfying g1 = Ω(g2), g2 = Ω(g3), . . . , g29 = Ω(g30). Partition your list
into equivalence classes such that f(n) and g(n) are in the same class if and only if f(n) = Θ(g(n)).
O ranqueamento das funções é:
2 n+1
> 22 n > (n+1)! > n! > en > n*2n > 2n > (3/2)n > nlg lg n e (lg n)lg n > (lg n)! > n3 > n2 e 4lg n > n lg n e lg(n!)
> n e 2lg n > (√2)lg n > 2√2 lg n > lg2 n > ln n > √ lg n > ln ln n > 2lg* n > lg* (lg n) e lg* n > lg(lg* n) > 1 e n1/lg
n
1/ lg n
4.3-1. Show that the solution of T(n)=T(n-1)+n is O(n^2)
Iteração
Expansão
k=1:
T(n)=T(n-1)+n
k=2:
Encontrar T(n-1):
T(n-1)=T((n-1)-1)+(n-1)
T(n-1)=T(n-2)+n-1
Substituir T(n-1) na equação anterior:
T(n)=T(n-2)+n-1+n
T(n)=T(n-2)+2n-1
k=3
Encontrar T(n-2):
T(n-2)=T((n-2)-1)+(n-2)
T(n-2)=T(n-3)+n-2
Substituir T(n-2) na equação anterior:
T(n)=T(n-2)+2n-1
T(n)=T(n-3)+n-2+2n-1
T(n)=T(n-3)+3n-3
Generalizando para k
T(n)=T(n-k)+(k)n -(k), assim vemos que O(n^2) é solução para T(n)
4.3-2. Show that the solution of T(n)=T(n/2)+1 is O(n^2)
Resolvendo essa recorrência pelo método iterativo:
Iteração
Expansão
k=1:
T(n)=T(n/2)+1
k=2:
Encontrar T(n/2):
T(n/2)=T(n/4)+1
Substituir T(n/2) na equação anterior:
T(n)=T(n/4)+2
k=3
Encontrar T(n/4):
T(n/4)=T(n/8)+1
Substituir T(n/4) na equação anterior:
T(n)=T(n/8)+3
Generalizando para k
T(n)=T(n/2^k)+k, vemos que O(n^2) é solução para T(n)
4.3-3. We saw that the solution of 2T([n/2])+n is O (n lg n). Show that the solution of this recurrence is
also Ω (n lg n). Conclude that the solution is Θ(n lg n).
Primeiro supomos que T(n)≤cn lgn:
T(n)≤2c⌊n/2⌋lg⌊n/2⌋+n
≤cn lg (n/2)+n
≤cn lg n−cnlg2+n
≤cn lg n+(1−c)n
≤cn lg n para c≥0
Depois testamos T(n)≥ c(n+2) * lg(n+2):
T(n)≥2c*(⌊n/2⌋+2)*(lg(⌊n/2⌋+2)+n
≥2c*(n/2−1+2)*(lg(n/2−1+2)+n
≥2cn+22lgn+22+n
≥c*(n+2)*lg(n+2)−c(n+2)*lg2+n
≥c*(n+2)*lg(n+2)+(1−c)*n−2c, para n ≥ 2c/(1−c)
≥c(n+2)lg(n+2)
Por isso, T(n) é Θ(n lg n).
4.3-6. Show that the solution of T(n)=2T([n/2]+17)+n is O(n lg n).
Suponha que T(n)=2T([n/2]+17)+n para todos n e que T(n)=(n lg n) para n menos que algum limite
superior k. Uma vez que T(n)=)(n lg n) para valores menors que k, então existe uma constante c tal que
T(n)≤ cn lg n. Assim, T(⌊n/2⌋+17)≤c(⌊n/2⌋+17) lg(⌊n/2⌋+17). Portanto, T(n)≤2c(⌊n/2⌋+17)
lg(⌊n/2⌋+17)+n, assim T(n)≤cn lg n.
4.4-1. Use a recursion tree to determine a good asymptotic upper bound on the recurrence
T(n)=3T([n/2])+n. Use the substitution method to verify your answer.
A árvore de recursão é a seguinte (um mesmo nível da árvore está em cada linha):
Nível
# nós
#custo
cn
3^0
n
3 x T(n/2)
T(n/2)=3(T(n/4)+n/2
3^1
3^1*n/3=n
9 x T(n/4)
T(n/4)=3(T(n/8)+n/4
3^2
3^2*n/9=n
3^n
3^h*n=1, onde h é a
altura da árvore de
recursão
…
T(1)
Como no último nível o tamanho de n=1, temos que 3^h*n=1, por isso h=ln3 n, assim
T(n)=3^h*n+SUM(n). Dessa forma, T(n)=nT(1)+n*lg3n, e Θ(n)=(n lgn).
Pelo método de substituição supomos que T(n)≤cn^lg3+2n, então
T(n)≤cn^lg3+2n
≤3c(n/2)^lg3+2n/2+n
≤cn^lg3+2n
Assim, temos que T(n) é Θ(n^lg3)
4.4-2. Use a recursion tree to determine a good asymptotic upper bound on the recurrence
T(n)=T(n/2)+n^2. Use the substitution method to verify your answer.
A árvore de recursão é a seguinte (um mesmo nível da árvore está em cada linha). Nessa tabela, i
significa um passo qualquer da recursão e h, a quantidade de passos para que n seja 1, ou seja a altura
da árvore.
Nível
0: c(n^2)
1: T(n/2)
T(n/2)=T(n/4)+n^2/4
2: T(n/4)
T(n/4)=T(n/8)+n^2/16
i: …
T(n/2^i)=T(n/2^i)+n^2/2^i
h: T(1)
T(1)=1
Assim,
T(n)=T(1)+SUM(n^2/2^i)
T(n)=T(1)+(n^2)*SUM(1/2^i), dessa forma o somatório representa uma série geométrica e o valor T(n)
final será T(n)=T(1)+(n^2). Do qual podemos afirmar que Θ(n) é n^2.
Pelo método da substituição supomos que T(n)<=cn^2, então
T(n)≤c(n/2)^2+n^2
≤cn^2/4+n^2
≤(c/4+1)n^2, (c>4/3)
≤cn^2
Assim, Θ(n) é n^2.
4.4-5. Use a recursion tree to determine a good asymptotic upper bound on the recurrence T(n)=T(n1)+T(n/2)+n. Use the substitution method to verify your answer.
Supondo que A(n)=T(n/2)+n
T(n)=T(n-1)+A(n)=T(n-2)+A(n-1)+A(n)=...=A(1)+A(2)+...+A(n)
T(n)=sum[1..n]A(n)
T(n)=sum[i=1..n]T(i/2)+sum[i=1..n]i
assumindo que n/2 é uma divisão por inteiro, T(n/2)=T((n+1)/2) para um n par, então a primeira soma
consiste de duas metades iguais: T(1)+T(1)+T(2)+T(2)+...
T(n)=2*sum[1..n/2]T(i)+n*(n-1)/2, desde que T(n)<=T(m) para todo n<=m
T(n)<=n*T(n/2)+n*(n-1)/2, pois T(n/2)>=n/2>=(n-1)/2
T(n)<=n*T(n/2)+n*T(n/2)=2*n*T(n/2), considerando apenas para n=2^k, n=2^k e U(k)=T(2^k)
U(k)<=2*(2^k)*U(k-1)=2^(k+1)*U(k-1), se L(k)=log2 U(k)
L(k)<=k+1+L(k-1), como nas etapas 1 e 2
L(k)<=k*(k-1)/2+k=k*k/2-k/2+k<=k*k
U(k)=2^L(k)<=2^SQRT(k)
T(n)=U(log2 n)<=2^SQRT(log2 n)
4.4-6. Argue that the solution to the recurrence T(n)=T(n/3)+T(2n/3)+cn, where c is a constant, is Ω(n
lg n) by appealing to a recursion tree.
O caminho mínimo para uma folha tem log 3n níveis, sendo que o custo para cada nível é cn. Se
cortarmos a árvore exatamente abaixo da primeira folha, teremos complexidade cn*log 3n, que será Ω(n
lg n).
4.5-1. Use the master method to give tight asymptotic bounds for the following recurrences.
a. T(n) = 2T(n/4) + 1
Para essa recorrência temos a = 2, b = 4, f (n) = 1. Podemos aplicar o caso 1 do teorema para concluir
que Θ(SQRT(n)).
b. T(n) = 2T(n/4) +1
Para essa recorrência temos a = 2, b = 4, f (n) = SQRT(n). Podemos aplicar o caso 2 do teorema para
concluir que Θ(SQRT(n) lg n).
c. T(n) = 2T(n/4) + n
Para essa recorrência temos a = 2, b = 4, f (n) = n. Podemos aplicar o caso 3 do teorema para concluir
que Θ(n).
d. T(n) = 2T(n/4) + n2
Para essa recorrência temos a = 2, b = 4, f (n) = n. Podemos aplicar o caso 3 do teorema para concluir
que Θ(n^2).
4.5-3. Use the master method to show that the solution to the binary-search recurrence
T(n)=T(n/2)+Θ(1) is T(n)=Θ(lg n). (See exercise 2.3-5 for a description of binary search).
Podemos usar o caso 2 do teorema com a=1,b=2, então:
f(n)=Θ(n^log21)=Θ(1)
T(n)=Θ(lg n)
4.5-4. Can the master method be applied to the recurrence T(n)=4T(n/2)+n 2lg n? Why or why not?
Give an asymptotic upper bound for this recurrence.
Com a=4,b=2, nós temos f(n)=n2lg n ≠ O(n2−ϵ) ≠ Ω(n2−ϵ), por isso não podemos aplicar o teorea
mestre. Para descobrir o limite assintótico, supomos Θ(n2 lg2 n):
T(n)≤4T(n/2)+n2lgn
≤4c(n/2)2 lg2(n/2)+n2lg n
≤cn2lg(n/2)lgn−cn2lg(n/2)lg2+n2lgn
≤cn2lg2n−cn2 lg n lg2−cn2lg(n/2)+22lgn
≤cn2lg2n+(1−c) n2lg n−cn2lg(n/2), para c>1
≤cn2lg2n−cn2lg (n/2)
≤cn2lg2n
4.5-5. Consider the regularity condition af(n/b)≥cf(n) for some constant c<1, which is part of
case 3 of the master theorem. Give an example of constants a≥1 and b>1 and a function f(n) that
satisfies all the conditions in case 3 of the master theorem, except the regularity condition.
Se a=1, b=2, f(n)=n(2−cos n)
Assim, se provamos:
n/2*(2−cosn2)<cn
(1−cos(n/2))/2<c
c≥1−(cos(n/2))/2
MIN(cos(n/2))=−1 implica que c≥3/2. Porém, c<1.
Parte 3
Capítulo 2 - Problema 2-4
Capítulo 4 - Exercícios 4.1-5, 4.2-1, 4.2-7, 4.5-2, Problema 4-5
Capítulo 16 - Exercícios 16.1-2, 16.1-3, 16.1-5.
Problema 2-4
Inversions
Let A[1..n] be an array of n distinct numbers. If i < j and A[i] > A[j] , then the pair (i,j) is called an
inversion of A.
a. List the five inversions of the array (2, 3, 8, 6, 1).
(0, 4), (1, 4), (2, 3), (2, 4), (3, 4)
b. What array with elements from the set {1,2,..,n} has the most inversions? How many does it have?
O array na ordem inversa, assim todos pares (ou seja, n) do conjunto estarão contidos nesse array.
c. What is the relationship between the running time of insertion sort and the number of inversions in
the input array? Justify your answer.
O insertion sort tem como principal argumento a troca de inversões adjacentes.
d. Give an algorithm that determines the number of inversions in any permutation on n elements in ‚.n
lg n/ worst-case time. (Hint: Modify merge sort.)
Podemos modificar o merge sort e, da mesma forma que o algoritmo original, ele vai ter tempo n lg n
no pior caso.
MERGE_SORT(A, p, r):
if p < r then
inversoes ← 0
q ← (p + r) / 2
inversoes ← inversoes + MERGE_SORT(A, p, q)
inversoes ← inversoes + MERGE_SORT(A, q + 1, r)
inversoes ← inversoes + MERGE_SORT(A, p, q, r)
merge_sort ← inversoes
eles then
merge_sort ← 0
4.1-5. Use the following ideas to develop a nonrecursive, linear-time algorithm for the maximumsubarray problem.
MAX_SUBARRAY(A, n):
sum ← 0, max_sum ← -INF;
for i ← 1 to n do
sum ← sum + A[i]
if sum > max_sum then
max_sum ← sum
if sum < 0 then
sum ← 0;
MAX_SUBARRAY ← max_sum
4.2-1. Use Strassen’s algorithm to compute the matrix product (matriz omitida)
S1=6, S2=4, S3=12, S4=−2, S5=5, S6=8, S7=−2, S8=6, S9=−6 e S10=14
P1=1*6=6
P2=4*2=8
P3=6*12=72
P4=(−2)*5=−10
P5=6*8=48
P6=(−2)*6=−12
P7=(−6)*14=−84
Assim,
C11=48+(−10)−8+(−12)=18
C12=6+8=14
C21=72+(−10)=62
C22=48+6−72−(−84)=66
4.2-7. Show how to multiply the complex numbers a+bi and c+di using only three multiplications of
real numbers. The algorithm should take a, b, c and d as input and produce the real component ac−bd
and the imaginary component ad+bc separately.
Usando o método de Karatsuba, fazemos S1=ac, S2=bd, e S3=(a+b)(c+d). Com isso, podemos
computar:
A=S1−S2
B=S3−S1−S2
Assim, o resultado final é A+Bi.
4.5-2. Professor Caesar wishes to develop a matrix-multiplication algorithm that is asymptotically
faster than Strassen's algorithm. His algorithm will use the divide-and-conquer method, dividing each
matrix into pieces of size n/4×n/4, and the divide and combine steps together will take Θ(n2) time. He
needs to determine how many subproblems his algorithm has to create in order to beat Strassen's
algorithm. If his algorithm creates a subproblems, then the recurrence for the running time T(n)
becomes T(n)=aT(n/4)+Θ(n2). What is the largest integer value of a for which Professor Caesar's
algorithm would be asymptotically faster than Strassen's algorithm?
Para estar no terceiro caso do teorema mestre, devemos ter a<16. Nesse caso, o algoritmo será
T(n)=Θ(n2). Para o segundo caso, com a=16, T(n)=Θ(n2logn). No primeiro caso do teorema mestre,
para ser mais rápido que o algoritmo de Strassen, necessitamos log4a<log27, que será a<72=49. Assim,
o maior valor inteiro será 48.
Problema 4-5. Chip testing - Professor Diogenes has n supposedly identical integrated-circuit chips
that in principle are capable of testing each other. The professor’s test jig accommodates two chips at a
time. When the jig is loaded, each chip tests the other and reports whether it is good or bad. A good
chip always reports accurately whether the other chip is good or bad, but the professor cannot trust the
answer of a bad chip.
a. Seja b o número de chips bons e nb ser o número de chips ruins. A partir deste pressuposto,sempre
encontrar um conjunto B de bons chips e um conjunto R de chips ruins de tamanho igual ao de B.
Agora, supondo que o conjunto R de chips ruins confunda o professor da seguinte forma: para qualquer
teste, eles se declaram bons e os chips em B como ruins. Observe que os chips do conjunto B exibem
um comportamento simétrico: eles se declaram bons e os chips em R como ruins. Isto implica que
qualquer estratégia baseada na análise feita pelo professor, o comportamento dos chips em G será
indistinguível do comportamento dos chips em B, isto é, esse comportamento não permite ao professor
para determinar quais chips são bons.
b. Dividimos os chips em dois grupos e os comparando par-a-par. Descartamos o par se tem como saída
que apenas um dos chips é ruim, caso contrário (ou seja, se os dois reportam a mesma saída),
guardamos os chips no conjunto de solução. Ao final, teremos que provar no máximo metade do
conjunto total n, já que existem mais chips bons que ruins.
c. Se, pelo menos, n/2 dos chips são bons, utilizando a resposta à questão b), podemos encontrar um
chip bom. Agora, a fim de encontrar todos chips bons, nós podemos apenas testar o primeiro chip bom
com todos os outros: para cada par, se pelo menos, um dos dois chips é bom será suficiente para decidir
se o outro chip é bom ou não. Esta etapa demanda n-1 testes.
Além disso, a fim de provar que os chips podem ser encontrados com Θ(n) testes par-a-par, só
precisamos de mostrar que o número de testes para encontrar um chip é Θ(n). Para mostrar isso,
podemos escrever a número de testes T(n)≤T([n/2])+[n/2]; e T(1)=0. A solução para este recorrência é
T(n)=O(n) e pode ser calculado, por exemplo, argumentando por indução que T(n)≤2^(log n).
16.1-2. Suppose that instead of always selecting the first activity to finish, we instead select the last
activity to start that is compatible with all previously selected activities. Describe how this approach is
a greedy algorithm, and prove that it yields an optimal solution.
A abordagem proposta é também um algoritmo guloso, pois recebe-se um conjunto de atividades S =
{a1, a2, . . . , an}, onde ai = [Si , fi), e deve-se encontrar uma solução ótima ao selecionar a últma
atividade que será iniciada que seja compatível com todas atividades selecionadas anteiormente. No
lugar disso, vamos criar um conjunto S’={a1’, a2’ , . . . , an’}, onde ai’ = [ fi , si ), ou seja, S´é o inverso
de S. Claramnte, um subconjunto {ai1 , ai2 , . . . , aik } ⊆ S é compaível, se e somente se o subconjunto
também é compatível { a1 ’ , a2 ’ , . . . , ak ’ } ⊆ S ’. Assim, uma solução ótima em S também é um
solução ótima em S´e vice e versa. Por isso, o algoritmo guloso apresentado no texto retorna o mesmo
resultado ótimo quando executado em S´.
16.1-3. Not just any greedy approach to the activity-selection problem produces a maximum-size set of
mutually compatible activities. Give an example to show that the approach of selecting the activity of
least duration from among those that are compatible with previously selected activities does not work.
Do the same for the approaches of always selecting the compatible activity that overlaps the fewest
other remaining activities and always selecting the compatible remaining activity with the earliest start
time.
Existem três casos nessa pergunta, provar que: 1 – erro ao selecionar a atividade de menor duração; 2 –
erro ao selecionar a atividade com menor interseccção; e 3 – erro ao selecionar a atividade com início
mais cedo. O caso 1 está incorreto pois podemos escolher atividades que tenham uma duração muito
pequena, mas que causem um intervalo muito grande para as atividades anteriores e posteriores, por
isso, devemos também considerar seu tempo de início e sua intersecção com outras atividades. O caso 2
está incorreto pois considerando apenas a quantidade de intersecções, poderiamos desconsiderar duas
(ou mais) atividades que estivesem perfeitamente encaixadas, mas que tivesse um grande número de
interseções com outras atividades não ótimas; finalmente, o caso 3 está incorreto pois levando em
consideração apenas o tempo de início, podemos errar ao escolher uma atividade que incia muito cedo,
mas que dura um tempo tão grande que impeça a escolha de outras atividades.