Tarea 4 de Análisis de Algoritmos
Trimestre 2013 Invierno
Entrega: 5 de marzo de 2013 en clase.
- [5+10+5 puntos] Imagina que tienes un edificio de n
pisos y que 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 qué pasa. Sea E(k,t)
el número máximo n de pisos para el que se puede responder la
pregunta con k huevos y t intentos. (a) Demuestra que E(1,t) =
t. (b) Encuentra una recurrencia
para E(k,t). (c) ¿Qué tan rápido se puede calcular E(k,t) usando
un algoritmo de programación dinámica?
- [5+5 puntos] Supón que tienes n enteros (positivos o
negativos o ceros) en un arreglo lineal
A. Se desea encontrar dos índices i y j tales que la suma A[i] +
A[i+1] + ... + A[j-1] + A[j] sea tan grande como sea posible.
(a)
Diseña un algoritmo de programación dinámica para
resolver este problema. (b) ¿Qué tan rápido se
puede ejecutar tu algoritmo en términos de n?
- [10 puntos] Supón que tienes n enteros (positivos o
negativos o ceros) en un
arreglo circular A. Se
desea
encontrar dos índices i y j tales que la suma A[i]
+ A[i+1] + ... + A[j-1] + A[j] sea tan grande como sea posible.
(a)
Diseña un algoritmo de programación dinámica para
resolver este
problema. (b) ¿Qué tan rápido se puede ejecutar tu
algoritmo en
términos de n?