Tarea 3 de Análisis de Algoritmos

Trimestre 2009 Otoño
Entrega: 23 de noviembre 2009 en clase.

1. [10 puntos] 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 _nC_r. 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(2ⁿ) y en Omega(2ⁿ/n).
2. [10 puntos] Diseñe y analice un algoritmo de divide y vencerás para encontrar la parte entera de la raíz cuadrada de un entero N de n bits utilizando O(n) sumas y desplazamientos.
3. [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).
4. [5+5 puntos] Diseñe dos algoritmos de programación dinámica que resuelvan el problema de la mochila y demuestre que sus algoritmos son correctos. (a) Que use espacio O(n). (b) Que use espacio O(s).