MAC0338/lista4.md

1. Escreva uma função que recebe um vetor com n letras A’s e B’s e, por meio de trocas, move todos os A’s para o início do vetor. Sua função deve consumir tempo $O(n)$.

A função vai receber o vetor C que possi n elementos.

OrdenaAB(C, n)
1.    dir <- 1
2.    esq <- n
3.    enquanto dir < esq
4.        se C[dir] igual 'A'
5.            dir <- dir + 1
6         senão se C[esq] igual 'B'
7.            esq <- esq + 1
8.        senão
9.            C[esq] <-> C[dir]
10.           dir <- dir + 1
11.           esq <- esq + 1

Note que em cada interação obrigatoriamente dir vai ser subtraído ou esq vai ser adicionado. Com isso o número máximo de vezes que a linha 3 pode ser executada é $O(n)$. Note que as linhas posteriores a essa vão ser executadas menos vezes que essa, portanto o código continuará $O(n)$.

2. Escreva uma função que rearranje um vetor v[p..r] de inteiros de modo que tenhamos v[p..j−1] ≤ 0 e v[j..r] > 0 para algum j em p..r+1. Faz sentido exigir que j esteja em p..r? Procure fazer uma função rápida que não use vetor auxiliar. Repita o exercício depois de trocar v[j..r] > 0 por v[j..r] ≥ 0. Faz sentido exigir que v[j] seja 0?

OrdenaZero(v, n)
1.    dir <- 1
2.    esq <- n
3.    enquanto dir < esq
4.        se C[dir] <= 0
5.            dir <- dir + 1
6         senão se C[esq] > 0
7.            esq <- esq + 1
8.        senão
9.            C[esq] <-> C[dir]
10.           dir <- dir + 1
11.           esq <- esq + 1

Não faz muito sentido exigir que j esteja em p..r, pois pense no caso em que temo o vetor completo de números negativas, nesse caso se j estiver em p..r, algum desses elemntos será > 0, criando uma contradição.

Para trocarmos v[j..r] > 0 por v[j..r] ≥ 0 basta alterar a linha 6 do programa. No entanto não faz sentido exigir que v[j] seja 0, pois dessa forma nunca saberíamos em qual parte do vetor encontramos os zeros.

3. Sejam X[1..n] e Y [1..n] dois vetores, cada um contendo n números ordenados. Escreva um algoritmo $O(lg n)$ para encontrar uma das medianas de todos os 2n elementos nos vetores X e Y .

Vamos tentar usar o método de divisão e consquista. Vamos supor que temos os seguintes vetores:

1 2 3 4 5 6 7 1 2 3 5 8 9 9

É claro que a mediana deles é 4 e 5. Vamos pegar a mediana do vetores:

1 2 3 (4) 5 6 7 1 2 3 (5) 8 9 9

O vetor em qual a mediana for menor deve ser aquele em que vamos pegar a parte da direita, o que a mediana for maior pegamos a da esquerda.

4 5 6 7 -> 4 (5) 6 7 -> 4 5 -> (4) 5 -> 4

1 2 3 5 -> 1 2 (3) 5 -> 3 5 -> 3 (5) -> 5

Na nossa função vamos ter dois vetores v1 e v2 com n elementos. Suponha que 3/2 = 1

Mediana(v1, v2, p1, q1, p2, q2)
1.    se q1-p1 = 0 
2.        retorna v1[p1]
3.    
4.    j1l <- p1+(q1-p1)/2
5.    j2l <- p2+(q2-p2)/2
6.    j1u <- p1+(q1-p1+1)/2
7.    j2u <- p2+(q2-p2+1)/2
8.    
9.    tmpv1 <- v1[j1l] + v1[j1u]
10.   tmpv2 <- v2[j2l] + v2[j2u]
11.    
12.   se tmpv1 > tmpv2
13.       retorna Mediana(v1, v2, p1, j1l, j2u, q2)
15.   senão
16.       retorna Mediana(v1, v2, j1u, q1, p2, j2l)

def Mediana(v1, v2, p1, q1, p2, q2)
    if q1-p1 == 0 
        return v1[p1]
    end
    
    j1l = p1+(q1-p1)/2
    j2l = p2+(q2-p2)/2
    j1u = p1+(q1-p1+1)/2
    j2u = p2+(q2-p2+1)/2

    tmpv1 = v1[j1l] + v1[j1u]
    tmpv2 = v2[j2l] + v2[j2u]
    
    if tmpv1 > tmpv2
        return Mediana(v1, v2, p1, j1l, j2u, q2)
    else
        return Mediana(v1, v2, j1u, q1, p2, j2l)
    end
end

size = 30
v1 = Array.new(size) { rand(10...50) }.sort!
v2 = Array.new(size) { rand(10...50) }.sort!

puts v1.join(" ")
puts v2.join(" ")
puts Mediana(v1, v2, 0, size-1, 0, size-1)
puts (v1+v2).sort[size-1, 2].join(" ")

Vamos provar que é $O(lg n)$.

$$T(n) = T(\lceil x/2 \rceil) + O(1)$$