MO417 - Questão para a prova oral

Número:

Enunciado: Analise as proposições sobre o algoritmo RANDOMIZED-SELECT e assinale a alternativa que possuir somente proposições corretas.

I - Por ser um algoritmo aleatório, não há entrada específica que represente um cenário de pior caso.
II - No pior caso, o RANDOMIZED-SELECT tem tempo de execução O(n), pois é um algoritmo linear.
III - O algoritmo é linear porque faz suposições sobre a entrada.
IV - Resolve o problema de seleção sem ordenação.

    (a) I, II e IV.

    (b) I, II e III.

    (c) I, III e IV.

    (d) II, III e IV.

    (e) N.D.A

Idéia original de: Kim Pontes Braga

MO417 - Questão para a prova oral

Número:

Enunciado: Marque a alternativa INCORRETA sobre o Counting sort:

    (a) É um algoritmo estável.

    (b) Não é um algoritmo que realiza comparações entre os números a ordenar.

    (c) Ordena os valores in place.

    (d) Seu tempo de execução é O(n).

    (e) NDA

Idéia original de: Kim Pontes Braga

MO417 - Questão para a prova oral

Número:

Enunciado: De acordo com o código abaixo, qual é a correta representação da função de comportamento do algoritmo no pior caso? (Obs: O algoritmo foi construído de acordo com as convenções explicadas no capítulo 2.)

for a=1 to n
    for b=1 to n
        for c=1 to n
            //Trecho de código qualquer
    for m=1 to n
        for n=1 to n
            for p=1 to n
                //Trecho de código qualquer

    (a) O(n³)
    (b) Θ(n³)
    (c) O(n4)
    (d) Θ(n4)
    (e) NDA

Idéia original de: Kim Pontes Braga.

Bem-Vindos!

Este blog foi criado exclusivamente para a disciplina de Complexidade de Algoritmos.

Aqui serão postadas algumas questões feitas por mim ao longo do semestre.

Enjoy it.