MO417 - QUESTÃO PARA A PROVA ORAL

Número:

Enunciado: Sobre a seleção de um elemento em uma sequência, escolha a alternativa incorreta:
a. A seleção de um elemento, quando aleatorizado, ocorre em tempo esperado O(n).
b. A seleção randomizada possui tempo O(n²) no pior caso.
c. O problema da seleção tem tempo teórico O(n) no pior caso.
d. O processo de escolha do pivô, sendo baseado no do quicksort randômico, também ocorre em tempo O(n).
e. NDA

Ideia original de: Jorge Augusto Hongo

MO417 - Questão para a prova oral

Número:

Enunciado: Para o quicksort, considere a seguinte escolha do pivô:

  1  i = random (p,r)       // p = primeiro elemento, r = último elemento
  2  para j = i+1 até r
  3       se A[i] = A[j]
  4            i = j
  5  troque A[i] com A[r]

Qual das seguintes afirmações sobre a implementação é correta?

a. ela aumenta a ordem de grandeza do melhor caso
b. ela aumenta a ordem de grandeza do pior caso
c. ela torna o quicksort-randomizado estável
d. ela dificulta a ocorrência do pior caso
e. NDA

Idéia original de: Jorge Augusto Hongo

MO417 - Questão para a prova oral

Número:

Enunciado: Qual das seguintes recorrências não pode ser resolvida pelo teorema mestre?

a. T(n) = 2T(n/3) + n lg n
b. T(n) = 3T(n/3) + 1/n
c. T(n) = 0,5T(n/2) + n
d. T(n) = T(n/2) + sqrt(n)
e. NDA

Idéia original de: Jorge Augusto Hongo

Questão (growth of functions)

MO417 - QUESTÃO PARA A PROVA ORAL

Número:

Enunciado: Assinale a alternativa correta:
a. O(g(n)) ∩ Ω(g(n)) = ∅
b. f(n) = o(g(n)) se e somente se g(n) = ω(f(n))
c. f(n) = O(g(n)) se e somente se g(n) = ω(f(n))
d. lg*n = ω(lg n)
e. NDA

Ideia original de: Jorge Augusto Hongo

Bem vindo ao meu blog!

As postagens terão perguntas sobre complexidade de algoritmos, conforme as regras definidas na disciplina MO417, ministrada na Unicamp; não espere as respostas aqui, caso você queira a solução, converse comigo com a sua resolução pronta.

Boa leitura e bons estudos!