Tarea 2 de Análisis y Diseño de Algoritmos

Trimestre 2018 Primavera

Entrega: 25 de mayo de 2018 en clase.

1. Demuestra que f(n) = 9999n+635 está en O(2ⁿ).
2. Demuestra que f(n) = 2ⁿ está en O(n!).
3. Resuelve exactamente la recurrencia T(1) = 4 y, para toda n ≥ 2 que sea una potencia de 2, T(n) = 2T(n/2) + 3n + 2.
4. Resuelve exactamente la recurrencia T(1) = 2 y, para toda n ≥ 3 que sea una potencia de 3, T(n) = 4T(n/3) + 3n - 5.
5. Demuestra que el siguiente algoritmo iterativo de exponenciación es correcto, es decir, debe regresar y^z:
   power(y,z)
     x := 1
     while (z > 0) do
       if (z es impar) then x := x*y
       z := z/2
       y := y²
     return (x)
   
6. Demuestra que el siguiente algoritmo recursivo de exponenciación es correcto, es decir, debe regresar y^z:
   power(y,z)
     if (z = 0) return (1)
     if (z es impar) then return (power(y²,z/2)*y)
     else return (power(y²,z/2))
   
7. Analiza el algoritmo iterativo de exponenciación de la pregunta 5. ¿Cuántas veces se hace la multiplicación x := x*y en el peor de los casos?
8. Analiza el algoritmo recursivo de exponenciación de la pregunta 6. ¿Cuántas veces se hace la multiplicación power(y²,z/2)*y en el peor de los casos?