Tarea 3 de Análisis de Algoritmos

Trimestre 2008 Otoño
Entrega: 27 de noviembre de 2008 en clase.

1. [10 puntos] Diseñe un algoritmo de programación dinámica que calcule el coeficiente combinatorio _nC_r en tiempo O(nr) y que use espacio O(r). Demuestre que su algoritmo es correcto.
2. [10 puntos] Resuelva exactamente la ecuación recurrente T(0) = c y T(n) = 3T(n-1)+d (la cual aparece en el análisis del algoritmo de divide y vencerás para el problema de multiplicación encadenada de matrices).
3. [10 puntos] Se tienen dos vectores de enteros positivos a = (a₁, a₂, ..., a_n) y b = (b₁, b₂, ..., b_n). Se desea permutar los elementos de b para obtener un tercer vector c = (c₁, c₂, ..., c_n) tal que el producto punto de a y c sea tan pequeño como sea posible. Recuerde que el producto punto de a y c está dado por a₁c₁ + a₂c₂ + ... + a_nc_n. Diseñe un algoritmo que encuentre el menor producto punto posible y demuestre que su algoritmo es correcto. Pista: haga algunos ejemplos a mano hasta que se dé cuenta de lo que está pasando.