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 = 1
2.        tmp <- [v1[p1], v1[q1], v2[p2], v2[q2]]
3.        tmp <- ordena tmp
2.        retorna tmp[3]
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, j1u, j2l, q2)
15.   senão
16.       retorna Mediana(v1, v2, j1l, q1, p2, j2u)

def Mediana(v1, v2, p1, q1, p2, q2)
    if q1-p1 == 1
        return (v1[p1,2] + v2[p2,2]).sort[1 , 2].join(" ")
    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, j1u, j2l, q2)
    else
        return Mediana(v1, v2, j1l, q1, p2, j2u)
    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)
sorted = (v1+v2).sort
puts [sorted[(2*size - 1) / 2], sorted[(2*size) / 2]].join(" ")

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

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

Vamos supor que $x$ é potencia de 2, ou seja, $x = 2^i$

$$T(x) = T(2^i/2^i) + i$$ $$T(x) = T(1) + i$$ $$T(x) = 1 + lg \space x$$

Vamos provar por indução:

BASE: $x = 1, T(1) = 1$ e $1 + lg \space 1 = 1$

HIPÓTESE: $T(x/2) = 1 + lg \space x/2 = lg \space x$

$$T(x) = T(x/2) + 1 = (pela HI) = lg \space x + 1 $$

Que é o que queríamos provar.

4. Para esta questão, vamos dizer que a mediana de um vetor A[p..r] com número inteiros é o valor que ficaria na posição A[b(p + r)/2c] depois que o vetor A[p..r] fosse ordenado. Dado um algoritmo linear “caixa-preta” que devolve a mediana de um vetor, descreva um algoritmo simples, linear, que, dado um vetor A[p..r] de inteiros distintos e um inteiro k, devolve o k-ésimo mínimo do vetor. (O k-ésimo mínimo de um vetor de inteiros distintos é o elemento que estaria na k-ésima posição do vetor se ele fosse ordenado).

Kesimo(A, p, r, k)
    m <- mediana(A, p, r)
    part <- particiona_com_elemento(A, p, r, m)
    se p > k
        retorna Kesimo(A, p, part, k)
    senao se p < k
        retorna Kesimo(A, part, r, k)
    retorna A[part]

Note, o particiona é $O(n)$, assim como a mediana. Portanto o tempo de consumo desse algorítmo será $T(n) = T(n/2) + O(n)$. Vamos provar que é $O(n)$. Note que $T(1) = 1$

BASE: $T(1) = 1 \leq c * 1 $