Tarea 7 de Análisis y Diseño de Algoritmos

Trimestre 2013 Otoño
Entrega: 18 de octubre de 2013 a las 22:00.

Problema 1: Sea N un entero positivo y sea A un vector de N enteros positivos. Se desea saber si existe algún subconjunto de los elementos del vector tal que sumen exactamente un entero S. Diseña un algoritmo de programación dinámica para resolver este problema. Escribe un programa llamado exactaZZ (donde ZZ es una clave de dos dígitos asignada por el profesor) que implemente tu algoritmo. La entrada a tu programa será un entero N (con 1 <= N <= 100), un entero S (con 0 <= S <= 100,000) y un vector A (con 1 <= A[I] <= 1000) y la salida de tu programa será un entero M (con 0 <= M <= 100) y un vector B con M componentes (con B[1] < B[2] < ... < B[M]) tal que S = A[B[1]] + A[B[2]] + ... + A[B[M]]. Puedes suponer que en los casos de prueba siempre habrá al menos una solución y basta que des una de ellas.

Problema 2: Sean S y T dos cadenas de caracteres. Decimos que la cadena C es una subsecuencia común de S y T si los caracteres de C aparecen en ese mismo orden tanto en S como en T. Por ejemplo si S = "SEPTIEMBRE" y T = "TRIMESTRE" entonces C = "TIME" es una subsecuencia común de S y T ("sepTIeMbrE" y "TrIMEstre"), pero no es la más larga de todas las subsecuencia comunes. Diseña un algoritmo de programación dinámica para encontrar una subsecuencia común de S y T tan larga como sea posible. Escribe un programa llamado scomunZZ (donde ZZ es una clave de dos dígitos asignada por el profesor) que implemente tu algoritmo. La entrada a tu programa serán dos cadenas S y T (mayúsculas, sin acentos, cada una en un renglón separado, 100 caracteres como máximo) y la salida de tu programa será una subsecuencia común de S y T tan larga como sea posible. Puedes suponer que S y T siempre tendrán al menos un caracter en común.

Notas: Tus programas no deben leer ni escribir nada adicional a lo que se indica en el enunciado. El tiempo de ejecución de sus algoritmos será considerado como parte de la evaluación.