Análisis de algoritmos
Primer examen parcial
Pregunta 1 (6 puntos): Use el
teorema general visto en clase para encontrar el orden de las
siguientes tres funciones recursivas (puede suponer que T(1) = 1). (a)
T(n) = 2T(n/3) + 5n. (b) T(n) = 4T(n/3) + n. (c) T(n) = 3T(n/3) + 6n.
También resuelvalas exáctamente (ya sin usar el teorema)
para el caso de que n es una potencia de 3.
Pregunta 2 (2 puntos): Si n es
una potencia de c > 1, encuentre la solución general a la
recurrencia T(1) = d y T(n) = a T(n/c) + b para n > 1. Demuestre
(por inducción) que su solución es correcta. Observe que
es posible que la solución general depende de la relación
entre los valores de a, b y c.
Pregunta 3 (2 puntos): Resuelva
exactamente la recursión T(2) = 1 y T(n) = T(piso(n/2)) +
T(techo(n/2)) + 2, donde piso(x) es el mayor entero <= x y techo(x)
es el menor entero >= x. Observe que esta es la recursión
exacta para la función minmax vista en clase en el caso de que n
no es necesariamente una potencia de 2.
Deben entregarlo el martes 24 de octubre en clase.