search

PUC-IIC2283 / 2020-IIC2283-Pruebas

Repositorio del curso Diseño y Análisis de Algoritmos 2020. Foro de interrogaciones y examen en Issues.
1 stars 0 forks source link

I1 - P3 #6

Open aeperalta opened 4 years ago

aeperalta commented 4 years ago

Tengo la duda de si espera que (1) hagamos el llenado de la tabla y (2) retornar una de las listas de operaciones óptimas, o teniendo como entrada las dos palabras y la tabla, solo hacer (2)? Por lo que tengo entendido, (1) no se puede hacer en tiempo polinomial al tamaño de la entrada (|w_1| + |w_2|), mientras que (2) sí.

marceloarenassaavedra commented 4 years ago

El algoritmo solo recibe como entrada w_1 y w_2, debe retornar una secuencia óptima de operaciones que transforme w_1 en w_2, y debe funcionar en tiempo polinomial en el largo de la entrada (vale decir, |w_1| + |w_2|).

Saludos!

aeperalta commented 4 years ago

Gracias, estaba entendiendo medio mal una cosa. Saludos!