Tarea 5 de Diseño de Algoritmos

Trimestre 2012 Otoño
Entrega: 31 de octubre de 2012 a las 22:00.

Observa que estos dos problemas son casi los mismos que los de la tarea 1, excepto que pueden involucrar valores de N mucho más grandes y cálculos módulo M. Para esto recuerda que las operaciones módulo M se pueden realizar indistintamente antes o después de otras operaciones, en particular (A+B) módulo M es igual a ((A módulo M) + (B módulo M)) módulo M y (A*B) módulo M es igual a ((A módulo M) * (B módulo M)) módulo M.

Problema 1 [5 puntos]: Los números de Catalán se definen de la siguiente manera: C[0] = 1 y C[N] = (4N-2) C[N-1] / (N+1). Escriba un programa que use memoización o programación dinámica llamado catampdZZ (donde ZZ es la clave de dos dígitos asignada por el profesor) que lea dos enteros N, M y que calcule el N-ésimo número de Catalán módulo M (es decir C[N] mod M). Por ejemplo si N = 5 y M = 4 entonces su programa debe calcular C[5] mod 4 = 42 mod 4 = 2. Puede suponer que 0 <= N <= 100000 y que 2 <= M <= 100000.

Ejemplo de entrada
 Ejemplo de salida
5 4
 2

Problema 2 [5 puntos]: Los números de Stirling se definen de la siguiente manera: S[0,0] = 1, S[N,0] = 0 y S[0,N] = 0 para toda N > 0 y S[N,K] = (N-1) S[N-1,K] + S[N-1,K-1] para toda N > 0 y K > 0. Escriba un programa que use memoización o programación dinámica llamado stirmpdZZ (donde ZZ es la clave de dos dígitos asignada por el profesor) que lea tres enteros N, K, M y que calcule el número de Stirling S[N,K] módulo M. Por ejemplo si N = 5, K = 3 y M = 6 entonces su programa debe calcular S[N,K] mod 6 = 35 mod 6 = 5. Puede suponer que 0 <= K <= N <= 1000 y que 2 <= M <= 1000.

Ejemplo de entrada
 Ejemplo de salida
5 3 6
 5

Notas: Sus 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.