Tarea 4 de Análisis de Algoritmos
Trimestre 2010 Invierno
Entrega: 8 de marzo de 2010 en clase.
- [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?
- [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?