MO417 - Questão para a prova oral

Numero:

 Uma empresa de telefonia recebeu reclamações sobre má qualidade do sinal ou ausência do mesmo. Ao analisar a distribuição de suas torres e a cobertura das mesmas, foi observado a má distribuição das torres.
Em duas regiões a e b, hora as torres se sobrepunham a cobertura, hora elas não cobriam uma certa área.

Sendo os pontos em negritos a posição da torre, dado por tn(x,y), e a área sombreada a cobertura total das mesmas.Dada  uma função f(tn) que retorna um índice de cobertura da torre, essa empresa resolveu o problema através da disposição de pares de torres, cujos índices fossem os k-ésimos maiores e menores respectivamente do conjunto de torres. O que é correto afirmar sobre um melhor algoritmo, em custos temporal e de comparação, que retornaria simultaneamente o maior e menor elemento de um vetor, de tamanho n dos índices de cobertura.

a. Esse algoritmo teria como caso médio O(n) e pior caso O(n²)
b.Seria necessária uma ordenação por comparação, logo é certo que o melhor caso nunca seria menor que Θ(nlogn)
c. O algoritmo:
     for 1 to n do { if (menor(i) { menor =i} if(maior(i) {maior=i} }
    É o mais eficiente em custos temporal e de comparação.
d. É possível realizar em média menos que duas comparações por elemento desse vetor para obtermos os elementos cujo índice seja o maior e menor respectivamente.
e. N.D.A

Ideia original de: Otávio Augusto Araújo Silva

MO417 - Questão para a prova oral

Numero:

Seja o algoritmo a seguir uma implementação do Randomized-QuickSort, cujo pivô inicial de cada subproblema é definido aleatóriamente entre os elementos A[p, ..., r]

RANDOMIZED-PARTITION(A,p,  r)
1 i <- RANDOM(p, r)
2 trocarA[p] <-> A[i]
3 return PARTITION(A, p, r)


RANDOMIZED-QUICKSORT(A, p, r)
1 if p<r
2  then  q <- RANDOMIZED-PARTITION(A, p, r)
3          RANDOMIZED-QUICKSORT(A, p, q - 1)
4          RANDOMIZED-QUICKSORT(A, q + 1, r) 

Podemos afirmar que:

a.   Para a entra {2,1,1,1,1,1}, tanto Randomized-QuickSort e QuickSort obterão o mesmo número e tamanho dos subproblemas.
b.  O custo de dividir e conquistar no Randomized-QuickSort é menor que o custo para o QuickSort, supondo que a geração de número aleatório seja constante para qualquer entrada.
c.  O algoritmo Randomized-QuickSort amortiza o custo do pior caso do QuickSort, assim seu custo em ordem temporal é sempre menor ou igual ao custo do QuickSort para qualquer caso.
d.  Sabendo que a entrada contém elementos distintos em alguma ordenação, o Randomized-QuickSort terá menores chances de gerar subproblemas K e L, onde K é muito maior que L, em comparação ao QuickSort.
e. N.D.A

Ideia original de: Otávio Augusto Araújo Silva

MO417 - Questão para a prova oral

Numero:

Dado as seguintes recorrências:
T(n)=   3T(n/3) + n+1
T'(n)=  2T(n/2) + n-1
T''(n)= 4T(n/4 +1) + n/2

E supondo os algoritmos A e B do HeapSort. Sendo A o algoritmo usual e B uma alteração onde cada pai tem 3 filhos, nas subárvores  esquerda, abaixo, direita. Sabendo que tal algoritmo realiza uma comparação a mais no HeapIfy. Podemos afirmar que:

a. O custo de B é superior ao de A mesmo que coincidam com a mesma assintota.
b. B pode ser melhor descrito como a recorrência T(n)
c. Apenas T'(n) e T''(n) são limitadas assintoticamente por Θ(nlogn)
d. A alteração em B não resulta em nenhuma otimização, mesmo para um n suficientemente grande
e. N.D.A

Ideia original de: Otávio Augusto Araújo Silva

Sejam f(n) e g(n) duas funções convergentes em h(n) para algum n>1. Não podemos afirmar que:

a. o(f(n))=o(g(n)) caso o(h(n))=o(f(n)).
b. Se f(n)=O(n³) e h(n)=w(n³), é válido g(n)=Θ(n²).
c. Se h(n)=Ω(n²) não existe n tal que o(f(n))<O(n).
d. w(f(n))=O(g(n)) , então Ω(g(n))<O(f(n)) para todo n.
e. NDA