car

MO417 - Questão para a prova oral
Número:

Enunciado: Qual das seguintes afirmações são verdadeiras e quais são falsas.

1. O abordagem "top-down with memoization" e o abordagem "bottom-up method" geralmente produzem algoritmos com o mesmo tempo assintótico de execução.
2. O passo 4: "construir uma solução ótima a partir da informação calculada", pode ser omitido em qualquer caso.
3. O algoritmo "LCS-length" tem uma versão memorizada que executa-se em tempo O(m*n).
4. Todos os problemas que são resolvidos com algoritmos recursivos, são também resolvidos usando programação dinâmica.

Escolha a alternativa correcta.

a) 1-V, 2-V, 3-F, 4-F
b) 1-V, 2-F, 3-V, 4-F
c) 1-F, 2-V, 3-V, 4-F
d) 1-F, 2-F, 3-V, 4-V
e) NDA.

Ideia original de: Carlos Eduardo Alfaro Morales