Tarea 4 de Análisis de Algoritmos

Trimestre 2012 Otoño
Entrega: 25 de octubre de 2012 en clase.

1. [5+5 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. (a) Demuestre que el máximo de T(n,0), T(n,1), ..., T(n,n) es T(n,n/2). (b) Demuestre que T(n,n/2) está en O(2ⁿ) y en Omega(2ⁿ/n).
2. [10 puntos] Resuelva exactamente (por ejemplo, por sustitución repetida) 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. [5+10+5 puntos] Imagine que tiene k huevos y un edificio de n pisos. Existe un piso r tal que si tiras un huevo desde el piso r se rompe, pero si lo tira desde más abajo entonces no se rompe. Es posible que r tome el valor 1 (en cuyo caso el huevo siempre se rompe) o el valor n+1 en cuyo caso el huevo nunca se rompe. Su objetivo es encontrar el valor de r y la única operación que puede hacer es tirar un huevo de algún piso y ver qué pasa. Sea H(k,t) el número máximo n de pisos para el cual se puede responder la pregunta usando t intentos o menos. (a) Demuestre que H(1,1) = 1. (b) Encuentre una recurrencia para H(k,t). (c) ¿Qué tan rápido se puede calcular H(k,t) usando un algoritmo de programación dinámica?