MO417 - Questão para a prova oral

Número: 032

Enunciado:
Com relação ao problema de encontrar uma subsequencia comum de comprimento máximo entre duas sequencias X e Y de tamanho m é INCORRETO afirmar que:

1. O melhor tempo assintótico para este algoritmo é Θ(n³)
2. Existem 2^m subsequencias de X
3. Este problema pode ser resolvido recursivamente
4. Este problema pode ser resolvido com programação dinâmica
5. NDA

Autor(a): Rodolfo Ipolito Meneguette