Pergunta da semana do dia 26/03 - 1ª questão

MO417 - QUESTÃO PARA A PROVA ORAL

Número: 

Enunciado: Sobre o algoritmo da PESQUISA-BINÁRIA-ITERATIVA:

BINARY-SEARCH(A, x)

1  if x < A[1] then
2     return 0
3  if x ≥ A[n] then
4     return n
5  // aqui A[1] ≤ x < A[n]
6  start ← 1
7  end ← n
8  // invariante: A[start] ≤ x < A[end]
9  while start + 1 < end do
10    middle ← (start + end)/2
11    if A[middle] ≤ x then
12       start ← middle
13    else
14       end ← middle
15 return start

é correto afirmar que a comparação da linha 11 é executada pelo menos :

a) ⌊lg n⌋  vezes
b) ⌊n/2⌋ vezes
c) ⌈(n+1)/2⌉ vezes
d) lg n +1  vezes
e) NDA



Ideia original de: Lucas Miguel de Carvalho

Pergunta da semana do dia 26/03 - 2ª questão

MO417 - QUESTÃO PARA A PROVA ORAL

Número: 

Enunciado: Sobre as afirmações 

I. O Insertion Sort em uma implementação estável utiliza, além do vetor original, um espaço de armazenamento = Θ(1).

II. Os algoritmos de ordenação em tempo linear se diferenciam dos algoritmos de ordenação convencionais (O(nlg(n)) por precisarem de uma característica específica de entrada.

III. O pior caso do Quicksort ocorre quando a entrada já está ordenada, sendo o tempo de execução O(n lg n).

Podemos afirmar que:

a) Todas são verdadeiras.
b) I e II são verdadeiras.
c) I e III  são verdadeiras.
d) II e III são verdadeiras.
e) NDA


Ideia original de: Lucas Miguel de Carvalho

Pergunta das aulas de 18/03 e 20/03

MO417 - Questao para a prova oral

Numero:

Enunciado: Sobre algoritmos de ordenação, assinale a alternativa que contém o algoritmo que seja local, estável e com tempo de execução no pior caso de pelo menos Ω( nlgn) :

a) Mergesort
b) Quicksort
c) Bucket Sort
d) Counting Sort
e) NDA.

Ideia original de: Lucas Miguel de Carvalho

Pergunta das aulas 11/03 e 13/03

MO417 - Questao para a prova oral

Numero:

Enunciado: Dada as seguintes afirmações

I. Se produz um heap máximo a partir de um vetor de tamanho n não ordenado em O(n).

II. A função f(n)=1/(2^n) não satisfaz condição de regularidade do teorema mestre a.f(n/b)<=c.f(n), para um c<1.

III. O tempo de execução de um algoritmo A é descrito pela recorrência T(n) = 7T(n/2) + n²,
um outro algoritmo A' tem um tempo de execução descrito pela recorrência T'(n) = aT'(n/4) + n²
O maior valor inteiro de a para que A' seja assintoticamente mais rápido que A é 49.

assinale a alternativa correta:

a) Apenas a afirmação I é verdadeira.
b) As afirmações I e II são verdadeiras.
c) Apenas a afirmação II é verdadeira.
d) As afirmações II e III são verdadeiras.
e) NDA.

Ideia original de: Lucas Miguel de Carvalho

Questão da semana referente as aulas do dia 04/03 e 06/03.

Dada as seguintes afirmações

I. O pior caso de tempo de funcionamento e tempo de execução esperado são iguais dentro de fatores constantes para qualquer algoritmo randomizado.

II. Para toda função f(n) positiva, temos que f(n) + o( f(n) ) = Θ( f(n) ).

III. Sobre crescimento de funções, podemos dizer que

assinale a alternativa correta:

a) Apenas a afirmação I é verdadeira.

b) As afirmações I e II são verdadeiras.

c) Apenas a afirmação II é verdadeira.

d) As afirmações II e III são verdadeiras.

e) NDA.