Tarea 4 de Análisis de Algoritmos

Trimestre 2010 Otoño
Entrega: 11 de noviembre de 2010 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] 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] Imagina que tienes 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 tiras 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. Tu objetivo es encontrar el valor de r y la única operación que puedes hacer es tirar un huevo de algún piso y ver que pasa. Se desea tirar tan pocos huevos como sea posible. Sea H(k,n) el número mínimo de veces que se necesita tirar un huevo para responder la pregunta. (a) Demuestra que H(1,n) = n. (b) Encuentra una recurrencia para H(k,n). (c) ¿Qué tan rápido se puede calcular H(k,n) usando un algoritmo de programación dinámica?