Solved Exercises
1. Finding the Peak. Let A= a1,…,an be a sequence of n numbers with the following
property: there is p in {1,…,n} for which
(i) the subsequence a1,..,ap is increasing and
(ii) the subsequence ap,…,an is decreasing.
Find p in O( log n) time.
Exemplo
A=13568 6432
p=5
Solved Exercises
2. Subcadeia de Soma Máxima
Entrada
Saída: i e j tais que
a = (a1, a2, … , aN) um vetor de inteiros
S[i , j ]= ai + ai+1 + … + aj é máximo.
 quando todos os valores de a são negativos, então a subsequencia vazia é
escolhida e o valor máximo da soma é considerado 0.
Exemplo: a = (-2, 11, -4, 13, -5, -2)
Solução
 i=2 e j=4

s[2,4]= 11 - 4 + 13 = 20
Solução “força bruta”
Existem O(n2) intervalos
Para calcular s[i, j ] gasta-se O(j-i)=O(n)
Complexidade de tempo O(n3)
Solução “força bruta”
Smax 0
Para i:=1 até n faça
Para j:=i ate n faça
SA[i]
Para k:=i+1 até j faça
S  S+A[k]
if S > Smax then
Smax S
Preprocessamento ...
Calculando s[1,i], para 1≤ i ≤ n, podemos calcular as demais somas em O(1):
S[ i , j ]= s[ 1, j ] –s[ 1 , i-1 ]
O(n2) intervalos
=>
Complexidade de tempo O(n2)
Preprocessamento ...
Prefix[0]  0
Para i:=0 até n-1
Prefix[i+1]  Prefix[i] + A[i]
Smax  0
Para i:=1 até n faça
Para j:=i ate n faça
if Prefix[j] – Prefix[i-1] > Smax then
Smax Prefix[j] – Prefix[i-1]
...“dividir-e-conquistar”
Quebrar em dois subvetores menores
resposta
no centro
resposta
a esquerda
resposta
a direita
a1
a2
a1
a2
...“dividir-e-conquistar”
Quebrar em dois subvetores menores
resposta
no centro
a1
a2
T(esq): subsequencia de soma máxima que começa em algum i*
menor ou igual a n/2 e termina em n/2
T(dir): subsequencia de soma máxima que começa em n/2+1 e
termina em algum j* maior ou igual a n/2+1
Melhor resposta no centro igual a s[ i*, j* ]
…“dividir-e-conquistar”
SubseqMaxima (i,j)
Se i=j and A[i]>0 then return A[i]
Se i=j and A[i]<0 then return 0
Senão
Sleft  SubseqMaxima (i,(i+j) div 2 )
Sright SubseqMaxima ((i+j) div 2 + 1, j )
Lmax 0; aux  0
Para k:= (i+j) div 2 downto i
aux  aux + A[k]
Se aux > Lmax then Lmax  aux
Rmax  0; aux  0
Para k:= (i+j) div 2 +1 to j
aux < - aux + A[k]
Se aux > Rmax then Rmax  aux
Scenter  Lmax+ Rmax
Return max(Sleft , Scenter , Sright )
…“dividir-e-conquistar”
T(n) = esforço para resolver instância de tamanho n
T(n) = n + 2.T(n/2)
T(1) = O(1)
T(n) = O(n.log n) + O(n) = O(n log n)
Complexidade de tempo O(n log n)
…“ É possível melhorar ?”


Programação Dinâmica
Tempo Linear
Exercício 1
Ao comparar a mediana a(n/2) da primeira lista com a mediana b(n/2) da
segunda lista temos
Caso i) a(n/2) >= b(n/2). Neste caso, os elementos a(n/2+1),…,a(n) são
maiores ou iguais que n elementos e os elementos b(1),…,b(n/2) são
menores ou iguais do que n elementos. Portanto, o elemento desejado é o
(n/2)-ésimo elemento do conjunto b(n/2+1),…,b(b), a(1),…,a(n/2). Este
pode ser encontrado recursivamente
Caso ii) a(n/2) < b(n/2). Análogo ao caso i
Complexidade de Tempo
T(2n) = 1 + T(n)
T(1) =1
Resolvendo a recorrência temos T(2n)= log (2n) = O(log n)
Exercício 2
Devemos aplicar a mesma estratégia do algoritmo para contar inversões com
a seguinte modificação na hora de combinar


multiplique todos os elementos da lista direita por 2 e faça um merge
entre as duas listas para contar o número de inversões
Faça o merge com as listas originais (sem multiplicar por 2) para obter
uma lista ordenada
Exercício 3
Escreva uma função Cartão(S) que dados o conjunto S de cartões :

Retorna um dos cartões que aparece mais do que |S|/2 vezes caso este
exista

Null caso contrário
Exercício 3
Cartão (S)
Se |S|=1
Return o único cartão de S
Senão
Particione S em dois subconjuntos S1 e S2 de
tamanho mais parecido possível
a  Cartão(S1) ; bCartão(S2)
Se a = Null e b = Null
Return Null
Se a <> Null
Compare a com todos os cartões de S
Se a aparece mais do que |S|/2 vezes
Return a
Se b <> Null
Compare b com todos os cartões de S
Se b aparece mais do que |S|/2 vezes
Return b
Return Null
(*)
(**)
Exercício 3
Teorema. Cartão(S) devolve Null se nenhum cartão de S aparece mais do
que |S|/2. Se existe cartão que aparece mais do |S|/2 vezes, o
procedimento devolve tal cartão.
Indução em |S|
Base |S|=1. Ok!
Hipótese. Propriedade vale quando |S| < = k.
Passo |S|=k+1.
Reciocínio.
Caso 1.) Existe um cartão em S, digamos c, que aparece mais do que (k+1)/2
vezes. Logo, este cartão aparecerá mais do que |S1|/2 vezes em S1 ou
mais de |S2|/2 vezes em S2. Como Cartão(S1) e Cartão(S2) estão
corretos então um destes retornará c. Logo, Cartão(S) retornará c.
Caso 2) Não existe cartão em S que aparece mais do que (k+1)/2 vezes. O
procedimento retorna Null já que tanto (*) quanto (**) vão retornar Null
Exercício 3
Complexidade de Tempo
T(n) = 2n + 2T(n/2)
T(1)=1
 T(n) = O(n log n)
( comparar cartões mais duas chamadas recursivas)
Exercício 4
Exercício 5
Escreva um Rotina HSR que recebe como entrada n retas e retorna uma
partição do intervalo (-\infty,+\infty) aonde a cada intervalo é associado
a reta visível naquele intervalo. Note que cada reta esta associada a no
máximo um intervalo
Divisão. Divida as retas em dois conjuntos de n/2 retas e resolva
recursivamente cada um dos subproblemas.
Exercício 5
Conquista. Seja L_e a lista dos intervalos para as retas do conjunto da
esquerda e L_d a lista de intervalos para as retas do conjunto da direita.
Seja r_e a reta associada ao primeiro intervalo de (l_e,u_e) de L_e e r_d
a reta associada ao primeiro intervalo de (l_d,u_d) de L_d. Assuma sem
perda de generalidade que l_e <= l_d.
Calculamos o ponto de interseção entre as retas r_e e r_d. Com base
neste ponto interseção descobrimos como fica a visibilidade na interseção
entre os intervalos (l_e,u_e) e (l_d,u_d).
Se u_d > u_e aplicamos o mesmo processamento em L_d e L_e –
(l_e,u_e)
Exercício 5
Escreva um Rotina HSR que recebe como entrada n retas e retorna uma
partição do intervalo (-\infty,+\infty) aonde a cada intervalo é associado
a reta visível naquele intervalo. Note que cada reta esta associada a no
máximo um intervalo
Divisão. Divida as retas em dois conjuntos de n/2 retas e resolva
recursivamente cada um dos subproblemas.
Conquista. Faça um “merge dos intervalos” obtidos
Complexidade de Tempo
T(n)=n + 2T(n/2) ( merge + duas chamadas recursivas)
T(1)=1
 T(n) =O(log n)
Exercício 6
LocalMinimo existe ?
Óbvio. O menor elemento da árvore é um local mínimo
Exercício 6
LocalMinimo(r)
Se r é um folha
Return r
Se r< r.esq e r<r.dir
Return r
Se r.esq<r
Return LocalMinimo(r.esq)
Se r.dir<r
Return LocalMinimo(r.dir)
(i)
(ii)
(iii)
(iv)
Complexidade de Tempo
T(n) <= c + T(n/2) se n>1 ( comparações + chamada recursiva)
T(n) =1 se n=1
( caso base)
 T(n) = O(log n)
Exercício 6
Teorema. LocalMinimo (r) retorna um mínimo local da árvore enraízada em r
Prova
Indução no tamanho da árvore.
Base. r é uma folha (i). Ok.
Hipótese. Vale para árvores com 2d -1 nós
Passo. Provar para árvore T com 2d+1 -1 nós
Caso 1) A raíz é um mínimo local de T. O algoritmo devolve r (ii)
Caso 2) A raíz não é um mínimo local de T
Subcaso 2.1) r.esq < r. Então um mínimo local da árvore enraízada em r.esq
é um mínimo local de T. Como neste caso LocalMinimo(r.esq) é chamado,
segue da hip de indução que o algoritmo devolve a resposta correta
Subcaso 2.2) r.esq > r. Então r.dir < r eum mínimo local da árvore enraízada
em r.dir é um mínimo local de T. Como neste caso LocalMinimo(r.dir) é
chamado, segue da hip de indução que o algoritmo devolve a resposta correta
10-3-6 Cormen
1. Seja p(i) , para i=1,...,k o último elemento do i-ésimo quantil
2. Encontre p(k/2) utilizando o algoritmo de seleção linear. Note que
p(k/2) é o k/2 . (n/k) menor elemento do conjunto de entrada.
3. Faça um pivoteamento colocando os elementos maiores que p(k/2) a
direita e os menores a esquerda.
4. Encontre os quantil p(1),...p(k/2-1) utilizando recursão para os
elementos menores que p(k/2) e os quantils p(k/2+1),...,p(k)
utilizando recursão para os elementos maiores que p(k/2).
Complexidade de Tempo; T(k) = n + 2 .T(k/2)
T(k) = n log k
10-3-7 Cormen
1. Encontre a mediana m em tempo linear
2. Para cada elemento x de S faça
S’  S’ U |x –m|
3. Seja q o (k+1)-ésimo menor elemento de S’. Encontre q utilizando o
algoritmo de seleção em tempo linear mostrado em sala
4. Obtenha os k+1 menores elementos de S’ pivoteando em relação ao
elemento obtido em 3.
Devido a transformação no passo 2, no conjunto S’ os k menores
elementos correspondem aos k mais próximos da mediana
10-3-9 Cormen
O local ótimo deve dividir metade dos poços para cada lado.
Caso contrário seria possível melhorar diminuir o comprimento total
movendo o duto principal de modo a aproximar da maioria dos poços.
Basta calcular a mediana considerando as coordenadas y