###### 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) ``` ```ruby 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) = T(n/2) + an $. Vamos provar que é $O(n)$. Note que $T(1) = 1$ BASE: $T(1) = 1 \leq c * 1 $ HIPÓTESE: $T(n/2) \leq cn/2 x$ $$ T(n) = T(n/2) + O(n) \leq c * n/2 + a * n \leq (c/2+a) n = c * n - n * c/2 + a * n$$ Só falta peovar que: $$ - nc/2 + a * n \leq 0 $$ $$ a * n \leq n * c/2 $$ $$ 2 * a \leq c $$ Como $a$ é uma contante que depende do particiona e da mediana e existe, logo existe $c$. ###### 5. (CLRS 8.3-2) Quais dos seguintes algoritmos de ordenação são estáveis: insertionsort, mergesort, heapsort, e quicksort. Descreva uma maneira simples de deixar qualquer algoritmo de ordenação estáavel. Quanto tempo e/ou espaçco adicional a sua estratégia usa? São estáveis os seguintes: insertionsort, mergesort. Uma maneira de deixar eles eles estáveis é mapear ele em um segundo vetor somando sua posição vezes um numero, por exemplo: A[1..n] = 5, 4, 2, 4, 6, 5, 4, 1 p = ((n+1) * max(A)) A = 5 + 1 * p, 4 + 2 * p, 2 + 3 * p, 4 + 4 * p, 6 + 5 * p, 5 + 6 * p, 4 + 7 * p, 1 + 8 * p Ordena o vetor e depois faz elemento % p. ###### 6. Qual a diferença de consumo de tempo entre uma busca binária em um vetor com n elementos e uma busca binária em um vetor com $n^2$ elementos? A busca binária consome tempo $O(lg \space n)$. Ou seja, $T(n) \leq c * lg \space n$. Queremos descobrir a proporção $\frac{c * lg \space n^2}{c * lg \space n} = lg ()$