MO417 - Questão para a prova oral

Número:

Enunciado: Dado o seguinte algoritmo para fazer a busca do i-ésimo menor elemento:

RANDOMIZED-SELECT(A, p, r, i)
1  if p == r
2       return A[p]
3       q = RANDOMIZED-PARTITION(A, p, r)
4  k = q - p + 1
5  if i == k  // the pivot value is the answer
6       return A[q]
7  elseif i < k
8       return RANDOMIZED-SELECT(A, p, q - 1, i)
9  else return RANDOMIZED-SELECT(A, q + 1, r, i - k)

Se T(n) representa o tempo de execução do algoritmo RANDOMIZED-SELECT e S(n) representa o tempo de execução do algoritmo RANDOMIZED-SELECT trocando a linha 3 por uma partiçao que não seja aleatória, qual das seguintes afirmações é correta:

A) No pior caso T(n) = Θ(n) e  S(n) = Θ(n)
B) No pior caso T(n) = Θ(n²) e  S(n) = Θ(n²)
C) No caso médio T(n) = O(n) e  S(n) = O(n)
D) No caso médio T(n) = Θ(n²) e  S(n) = Θ(n²)
E) NDA

Ideia original de: John Edgar Vargas Muñoz

MO417 - Questão para a prova oral

Número:

Enunciado:

Dado o seguinte algoritmo do Bucket Sort:

1 let B[0..n-1] be new array
2 n = length [A]
3 For i = 0 to n-1
4     make B[i] an empty list
5 For i = 1 to n
6     Insert A[i] into list B[floor(nA[i])]
7 For i = 0 to n-1
8     Sort list B[i] with Insertion sort
9 Concatenate the lists B[0], B[1], . . B[n-1] together in order.

Se mudamos a linha 8 e fazemos a ordenação com quicksort quais serão os tempos de execução no caso médio e no pior caso respectivamente:

a) Θ(n) e O(nlgn)
b) Θ(n) e O(n²)
c) Θ(n lg n) e O(n lg n)
d) Θ(n lg n) e O(n²)
e) NDA




Ideia original de: John Edgar Vargas Muñoz

MO417 - Questão para a prova oral

Número:

Enunciado: Se T(n)=9T(n/3)+n², T(0) = T(1) = 1, qual das seguentes afirmações não é correta.

a) T(n) = O(n³)
b) T(n) = Θ(n² log n)
c) T(n) = Ω(n³)
d) T(n) = Ω(n²)
e) NDA


Ideia original de: John Edgar Vargas Muñoz

Questão da primeira semana:

Quais das seguintes afirmações são corretas?

I. RAM(Random-access machine) só trabalha com números inteiros

II. lg(n!) = O(nlgn)

III. insertion sort tem tempo de execução Θ(n^2)

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

Local de postagem das questões da disciplina de Complexidade de Algoritmos I - MO417