Tarea 3 de Análisis de Algoritmos

Trimestre 2008 Invierno
Entrega: 2 de mayo de 2008 en clase.

  1. En el análisis del tiempo de ejecución del algoritmo que calcula los coeficientes combinatorios demostramos que T(n,r) es exactamente igual a nCr. Es fácil ver que el máximo de T(n,0), T(n,1), ..., T(n,n) es T(n,n/2). Demuestre que T(n,n/2) está en O(2n) y en Omega(2n/n).
  2. Diseñe un algoritmo de programación dinámica que calcule el coeficiente combinatorio nCr en tiempo O(nr) y que use espacio O(r). Demuestre que su algoritmo es correcto.
  3. Diseñe dos algoritmos de programación dinámica que resuelvan el problema de la mochila y demuestre que sus algoritmos son correctos:
    1. Que use espacio O(n).
    2. Que use espacio O(s).
  4. En el análisis del problema de multiplicación encadenada de matrices demuestre que X(n) = 2n-2Cn-1/n.
  5. 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).