Tarea 6 de Diseño de Algoritmos

Trimestre 2010 Primavera
Entrega: 28 de junio de 2010 a las 22:00.

Problema 1: 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.

Ejemplo de entrada
 Ejemplo de salida
SEPTIEMBRE
TRIMESTRE 		TIMRE

Problema 2: Algunas personas piensan que los perros que ladran mucho muerden poco. Para demostrar lo contrario se quiere analizar una colección de perros y escoger tantos de ellos en una secuencia en la que tanto el número de ladridos como el número de mordidas vayan en orden creciente. Sea P un entero positivo que denota al número de perros en la colección, L[1], L[2], ..., L[P] un vector de enteros positivos indicando el número de ladridos de cada uno de los P perros y M[1], M[2], ..., M[P] el número de mordidas de cada uno de los P perros. Diseñe un algoritmo de programación dinámica que encuentre la máxima longitud S de la secuencia con las propiedades pedidas. En otras palabras, si los L perros escogidos son los perros I1, I2, ..., IS entonces M[I1] < M[I2] < ... < M[IS] y L[I1] < L[I2] < ... < L[IS]. Por ejemplo, si P = 4, L = (3, 1, 4, 2) y M = (2, 7, 1, 8) entonces S = 2 ya que se puede escoger a los perros 2 y 4 con M[2] < M[4] y L[2] < L[4]. Escriba un programa llamado muerdeZZ (donde ZZ es una clave de dos dígitos asignada por el profesor) basado en su algoritmo que acepte como entrada un número entero P, seguido de un renglón con P números enteros L[1], L[2], ..., L[P] separados por espacios y seguido de un renglón con otros P números enteros M[1], M[2], ..., M[P] y que escriba como salida la máxima longitud S de la secuencia con las propiedades pedidas. Puede suponer que todos los números involucrados son enteros del 1 al 10,000.

Ejemplo de entrada Ejemplo de salida
4
3 1 4 2
2 7 1 8 		2

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.