Order statistics

MO417 - QUESTÃO PARA A PROVA ORAL

Número:

Enunciado: Dadas as seguintes afirmações:

I - Para localizar o maior valor em uma lista desordenada são necessárias, no mínimo, n-1 comparações entre seus n elementos.
II - Para encontrar o segundo maior valor em uma lista com n elementos, são necessárias n + ⌈ lg n ⌉ - 1 comparações no pior caso.
III - Comparando-se aos pares, os n elementos de uma lista, até que sobre apenas o menor valor, gera um total mínimo de ⌊ n^{(1+1/lg n)}⁄ 2 ⌋ - 1 comparações.

Assinale a alternativa correta:

a. Apenas I está correta.
b. I e II estão corretas.
c. I e III estão corretas.
d. II e III estão corretas.
e. NDA

Ideia original de: Anderson Coelho Weller

Linear time sorting

MO417 - QUESTÃO PARA A PROVA ORAL

Número:

Enunciado: Supondo que, utilizamos o Radix-Sort para ordenar n-números inteiros, com o tamanho máximo de b-bits. Avalie as seguintes afirmações, sabendo que esse algoritmo ordena os números no tempo de Θ((b/r)(n+2^r)) para qualquer valor inteiro positivo r ≤ b:

I - Podemos ordenar esses n-números inteiros no tempo de O(n), estando eles no intervalo de 0 a nⁿ-1.
II - Podemos ordenar esses n-números inteiros no tempo de O(n), estando eles no intervalo de 0 a n³-1.
III - Para chegar a esse limite assintótico é necessário ordenar os d-digitos através de um método estável, como o Merge-Sort.

a. Apenas I está correta.
b. Apenas II está correta.
c. I e II estão corretas.
d. I, II e III estão corretas.
e. NDA

Ideia original de: Anderson Coelho Weller

Recurrences

MO417 - QUESTÃO PARA A PROVA ORAL

Número:

Enunciado: Dadas as seguintes recorrências, assinale a alternativa correta:

T₁(n) = 5T(n/6) + n²
T₂(n) = 5T(n/2) + n^{lg 5}
T₃(n) = 5T(n/2) + n²

a. T₁(n) possui uma ordem de crescimento maior do que T₂(n)
b. T₂(n) possui uma ordem de crescimento maior do que T₃(n)
c. T₃(n) = Θ(n^{lg 5} lg n)
d. T₁(n) = Θ(n^{log₆ 5})
e. NDA

Ideia original de: Anderson Coelho Weller

Growth of functions

MO417 - QUESTÃO PARA A PROVA ORAL

Número:

Enunciado: Dado um algoritmo com a mesma estrutura apresentada abaixo, cujo laço externo executa f(n) = 7n vezes um laço interno e este último executa g(n) = lg n vezes um bloco de complexidade h(n) = 10n². Qual é o "Limite assintótico superior" dele?

Repetir f(n) vezes
{
    Repetir g(n) vezes
    {
       Repetir h(n) vezes
    }
}

a. O( 10n² )
b. O( n³ )
c. O( n² )
d. O( n³ lg n )
e. NDA

Ideia original de: Anderson Coelho Weller