MAC0338/lista5.md

1. Mostre que lg (n!) ≥ (n/4) lg n para n ≥ 4 sem usar a formula de Stirling.

Vamos utilzar que $$2 lg \space (n!) \geq (n/2) lg \space n$$ e lebrem que $$ 2 lg \space (n!) = lg \space (n!^2) = lg \space(\prod_{i=0}^{n-1} (n-i) \cdot (i+1)) $$ $$ (n-i) \cdot (i+1) = ni+n-i^2-i$$

Se realizarmos primeira derivada dessa função em $i$ e igualarmos a 0, vamos obter que $n-2i-1 = 0$. Resolvendo essa equaçao e sabendo que a parábola da equação de segundo grau é voltada para baixo, descobrimos que o ponto máximo dessa equação é em $i = \frac{n-1}{2}$. Veja que $i \in [0, n-1]$, calculando o valor da equação nos tremos chegamos a $n$ em ambos o caso. Portanto como o máximo está entre os extremos e nelas o valor é $n$, podemos concluir que,

$$ (n-i) \cdot (i+1) \geq n $$

Usando isso,

$$ 2 \cdot lg \space (n!) \geq 2 \cdot lg \space (\prod_{i=0}^{n-1} n) = 2 \cdot lg \space (n^n) = 2 \cdot n \cdot lg \space (n)$$

$$ lg \space (n!) \geq n \cdot lg \space (n)$$

Se dividirmos a parte da direita dessa inequação por 4 ela continua sendo válida e chegamos onde queríamos.

2. (CLRS 8.1-3) Mostre que não há algoritmo de ordenação baseado em comparações cujo consumo de tempo é linear para pelo menos metade das n! permutações de 1 a n. O que acontece se trocarmos “metade” por uma fração de 1/n? O que acontece se trocarmos “metade” por uma fração de $\frac{1}{2^n}$?

Tenho $n!/2$ folhas na nossa árvore de decisão (note que é uma árvore binária), portanto não pode ter mais que $2^h$ folhas ($h$ é a altura da árvore e é ainda desconhecido). Portanto $$\frac{n!}{2} \leq 2^h$$ Aplicando o $lg$ em anbos os lados, $$h \geq lg \space (n!) - 1$$ E sabendo que $$ lg \space (n!) \geq n \cdot lg \space (n)$$ (pelo exercíco anterior), $$h \geq lg \space (n!) - 1 \geq n \cdot lg \space (n) - 1$$ Ou seja, o número mínimo de comparações será $h$ e como $h$ é limitado inferiormente por $n \cdot lg \space (n) - 1$, temos que o algorítimo irá realizar no mínimo $\Omega(n \cdot lg \space (n))$ comparações.

Vamos proceder da mesma forma para $\frac{n!}{n}$ comparações. $$\frac{n!}{n} \leq 2^h$$ $$h \geq lg \space (n!) - lg \space n$$ $$h \geq lg \space (n!) - lg \space n \geq n \cdot lg \space (n) - lg \space n = \Omega(n \cdot lg \space (n))$$

E o mesmo para $\frac{n!}{2^n}$, $$\frac{n!}{2^n} \leq 2^h$$ $$h \geq lg \space (n!) - n$$ $$h \geq lg \space (n!) - n \geq n \cdot lg \space (n) - n = \Omega(n \cdot lg \space (n))$$

3. (CLRS 8.2-4) Descreva um algoritmo que, dados n inteiros no intervalo de 1 a k, preprocesse sua entrada e então responda em O(1) qualquer consulta sobre quantos dos n inteiros dados caem em um intervalo [a..b]. O preprocessamento efetuado pelo seu algoritmo deve consumir tempo O(n + k).

$A$ é o vetor com os $n$ elementos.

Processa(A, n k)
    B[1..k] <- 0
    para i igual a 1 até n
        B[A[n]] <- B[A[n]] + 1
    para i igual a 2 até k
        B[i] <- B[i] + B[i-1]

A linha 2 e 3 consome tempo proporcional a n e a 4 e 5 proporcional a k, portanto o tempo de execução será $O(kn)$.

Descobre(a, b, B)
    return B[b]-B[a]

4. (CLRS 8.4-1) Simule a execução do BUCKETSORT com o vetor $A[1..10] = <0.79, 0.13, 0.16, 0.64, 0.39, 0.20, 0.89, 0.53, 0.71, 0.42>$.

B[1..10] = [[], [], [], [], [], [], [], [], [], []]

Para cada elemento de A vamos fazer \$\lceil\$ nA \$\rceil\$, vamos, na simulação guardar um A'
A'[1..0] = [7.9, 1.3, 1.6, 6.4, 3.9, 2.0, 8.9, 5.3, 7.1, 4.2]
A'[1..0] = [8.0, 2.0, 2.0, 7.0, 4.0, 2.0, 9.0, 6.0, 8.0, 5.0]

Inserimos A[i] em B[A'[i]]

B[1..10] = [[], [0.13, 0.16, 0.20], [], [0.39], [0.42], [0.53], [0.64], [0.79, 0.71], [0.89], []]

Ordenamos cada lista de B.

B[1..10] = [[], [0.13, 0.16, 0.20], [], [0.39], [0.42], [0.53], [0.64], [0.71, 0.79], [0.89], []]

Concatenamos as listas

B[1..10] = [0.13, 0.16, 0.20, 0.39, 0.42, 0.53, 0.64, 0.71, 0.79, 0.89]

5. (CLRS 8.4-2) Qual é o consumo de tempo de pior caso para o BUCKETSORT? Que simples ajuste do algoritmo melhora o seu pior caso para O(n lg n) e mantém o seu consumo esperado de tempo linear.

O pior caso no BUCKETSORT é quando todos os elementos da lista cairem na mesma sub-lista do vetor B. Nesse caso o nosso algorítimo vai levar tempo proporcional ao método de ordenação que utilizamos para ordenar essas sub-listas. No livro, ele escolhe o InsertionSort que posui pior caso $nˆ2$, se trocarmos por qualquer algorítmo de tempo máximo $O(n lg \space n)$, teremos o pior caso como $O(n lg \space n)$. Vamos averiguar se preserva o caso médio, $n_i$ será o número de elementos médio no sub vetor

$$E[T(n)] = E[\Theta (n) + \sum_{i = 1}^{n} O(n_i lg \space n_i)]$$ $$E[T(n)] = \Theta (n) + \sum_{i = 1}^{n} O(E[n_i lg \space n_i]) = \Theta (n) + O(n lg \space n)$$

6. (CLRS 28.2-5) Quão rápido você consegue multiplicar uma matriz kn × n por uma n × kn usando o algoritmo de Strassen como uma subrotina? Responda a mesma questão com a ordem das matrizes de entrada invertida.

Vamos supor que quermos multilicar $A_{kn*n}$ por $B_{n*Kn}$, note que vamos obter uma matriz $C$ de dimenções $kn*kn$. Vamos dividir $A$ em $k$ matrizes de dimenões $n*n$, sendo assim teremos $A=\begin{bmatrix} A_1 \\ A_2 \\ ... \\ A_n \end{bmatrix}$. O mesmo Vale para $B=\begin{bmatrix} B_1 & B_2 & ... & B_n \end{bmatrix}$ Veja que $C = \begin{bmatrix} A_1 \cdot B_1 & A_1 \cdot B_2 & ... & A_1 \cdot B_n \\ A_2 \cdot B_1 & A_2 \cdot B_2 & ... & A_2 \cdot B_n \\ ... & & & ... \\ A_n \cdot B_1 & A_n \cdot B_2 & ... & A_n \cdot B_n \end{bmatrix} $. Fazendo dessa maneiro o tempo esperado da multiplicação será $\Theta(k^2 \cdot n^{lg \space 7})$, pois termos $k^2$ multiplicações de matrizes de dimensões $n*n$ e o algoritmo de Strassen leva tempo proporcionar a $\Theta(n^{lg \space 7})$.

Invertendo a ordem e fazendo $B \cdot A$, vamos obter um $C$ de dimensões $n*n$. Veja que para esse caso $D = \begin{bmatrix} A_1 \cdot B_1 \\ A_2 \cdot B_2 \\ ... \\ A_n \cdot B_n \end{bmatrix} = \begin{bmatrix} D_1 \\ D_2 \\ ... \\ D_n \end{bmatrix}$ e $C = D_1 +D_2 + ... +D_n$, portanto para esse caso o tempo será $\Theta(k \cdot n^{lg \space 7})$.

7. No Select-BFPRT, os elementos do vetor são divididos em grupos de 5. O algoritmo continua linear se dividirmos os elementos em grupos de 7? E em grupos de 3? Justifique sua resposta.

Veja que nessa imagem há no máximo $\lceil \frac{n}{7} \rceil$ pontos em cada linha. Há $\lceil \frac{1}{2} \lceil \frac{n}{7} \rceil \rceil$ colunas a direita da mediana, incluindo ela, note que há duas dessas colunas em que o número de pontos é menor. Portanto há $5(\lceil \frac{1}{2} \lceil \frac{n}{7} \rceil \rceil-2)$ pontos menores que a mediana. Note que:

$5(\lceil \frac{1}{2} \lceil \frac{n}{7} \rceil \rceil-2) \geq \frac{5n}{14} - 10$

Ou seja na prónima interação vamos calcular um número maior que $\frac{5n}{14} - 10$ no melhor caso e um número menor que $n-\frac{5n}{14} - 10$ no pior caso. Vamos assumir que vamos sempre pegar o pior caso para poder calcular o pior caso. Note também que en todos os casos vou ter que calcular a medina das medianas, que vai consumir tempo $T(\lceil \frac{n}{7} \rceil)$. Dessa maneira o tempo total será:

$$T(n) = T(\lceil \frac{n}{7} \rceil) + T(\frac{9n}{14} + 10) + O(n)$$

Queremos provar que o algorítmo continua linear, ou seja, $T(n) \leq cn$, utilizando essa hipótese:

$$T(n) \leq c\lceil \frac{n}{7} \rceil + c\frac{9n}{14} + 10c + an$$ $$T(n) \leq c\lceil \frac{n}{7} \rceil + c\frac{9n}{14} + 10c + an$$ $$T(n) \leq c\frac{n}{7} + c + c\frac{9n}{14} + 10c + an$$ $$T(n) \leq \frac{11n}{14}c + 11c + an$$

Veja que:

$$\frac{11n}{14}c + 11c + an = cn + (\frac{-3nc}{14} + 11c + an) $$

Basta provar que:

$$\frac{-3nc}{14} + 11c + an \leq 0$$ $$-3nc + 154c \leq -14an $$ $$3nc - 154c \leq 14an $$ $$c \leq \frac{14an}{3n-154} $$

Note que a partir de n = 100 a fração será sempre menor do que 9, portanto existe o $c \geq 9a$ vai satisfazer a equação anterior e vai permitir que a nossa hipótese seja verdadeira.

8. Considere a seguinte variante do Particione-BFPRT, que chamaremos de Particione-D. Em vez de acionar o Select-BFPRT para calcular a mediana das medianas, ela aciona recursivamente o próprio Particione-D, para calcular uma “mediana aproximada” do vetor das medianas. Suponha que o Particione-D rearranja o vetor A[p..d] e devolve um índice q tal que A[p..q−1] ≤ A[q] < A[q+1..d] e max{k, n−k} ≤ 9n/10, onde n = d−p+1 e k = q−p+1. Analise o consumo de tempo da variante do Select-BFPRT que chama o Particione-D em vez do Particione-BFPRT.

Para facilitar a visualização desse exercício vamos escrever o código Select-BFPRT novamente:

Select-BFPRT(A, p, r, i)
    se p = r
        devolve p
    q <- Particione-D(A, p, r)
    k <- q-p+1
    se k = i
        devolve k
    senão se k > i
        devolve Select-BFPRT(A, p, q-1, i)
    senão
        devolve Select-BFPRT(A, q+1, r, i-k)
        

Particione-D(A, p, r)
    para j <- p, p+5, p+10 ... p+5*(n+1)/5-1
        ordena_5_elementos
    para j <- 1 até (n+1)/5-1 #numero de elementos medianos
        A[p - 1 + j] <-->  A[p + 5*j -3] #colocar as medianas no inicio
    [p - 1 + ceil(n/5)]  <-->  A[ floor((p + 5 * floor(n/5) + r)/2) ]  // meio do último intervalo...
    
    k <-- Particione-D(A, p, p+ceil(n/5), floor( (ceil(n/5) + 1)/2 ))
    A[k] <--> A[r] # manda a mediana para o final
    
    devolve particiona(A, p, r)

A primeira parte é verificar o consumo de tempo do Particione-D. Note que $r-p+1 = n$.

$$ T(n) \leq O(n) + T(n/5)$$

Vamos analizar essa recursão, note que colocamos $\leq$ , pois as linhas 3 e 5 do Particione-D podem consumir tempo menor do que as linhas 2 e 4. Então vamos supor que:

$$T(n) = O(n) + T(n/5) = an + T(n/5) = an + an \frac{1}{5} T(n (\frac{1}{5})^2) $$

$$= an \sum_{j=1}{i} (\frac{1}{5})^{j-1} + T(n (\frac{1}{5})^i) = an \cdot \frac{(\frac{1}{5})^i-1}{\frac{1}{5}-1} + T(n (\frac{1}{5})^i)$$

Suponha que $n= 5^i$. Utilizamos esse recurso para descobrir o comportamento da função. Descoberto o comportamento dela vamos provar que esse comportamento está certo (ou errado). Assumindo isso:

$$T(n) = a \cdot \frac{1-n}{\frac{1}{5}-1} + 1 = a \cdot \frac{5-5n}{1-5}+1 = \frac{-5a+5na+4}{4}$$

Veja que belo, uma função $\Theta(n)$. Agora vamos verificar se a recurção original é realmente $\Theta(n)$, para isso vamos usar indução. Veja que o caso BASE é trivial. Lembre que estamos assumindo (nossa hipótese) $T(n) = \frac{-5a+5na+4}{4}$.

$$ T(n) = a n + T(n/5)$$

Pela hipótese:

$$ T(n) = a n + T(n/5) = an + \frac{-5a+n+4}{4} = \frac{4an-5a+n+4}{4} = \frac{4an-5a+na+4}{4}= \frac{-5a+5na+4}{4}$$

Que é o que queríamos provar. Agora que sabemos que o Particione-D é $\Theta(n)$, temos que provar o mesmo para o Select-BFPRT. Note que o tempo consumido por essa função será:

$$T(n) \leq O(n) + T(max(k, n−k)) \leq O(n) + T(9n/10)$$

Podemos proceder da mesma maneira que na parte anterior, mas vamos fazer diferente. Sabemos que queremos provar que $T(n)$ é $O(n)$, ou seja $T(n) < cn$ (isso será nossa hipótese de indução).

...

10

A) Olha os dois vetores e pega o maior em cada um deles, se o outro vetor tiver acabado compara com 0.