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

Trimestre 2017 Invierno

Entrega: 31 de enero de 2017 en clase.

1. Demuestra que f(n) = n está en O(2ⁿ).
2. Demuestra que f(n) = 9999n+635 está en O(2ⁿ).
3. Demuestra que f(n) = 2ⁿ está en O(n!).
4. 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.
5. 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.
6. Resuelve exactamente la recurrencia T(1) = 1 y, para toda n ≥ 2, T(n) = 1 + ∑_i=1^n-1 (T(i) + T(n-i)).
7. 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)
   
8. 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))
   
9. Analiza el algoritmo iterativo de exponenciación de la pregunta 7. ¿Cuántas veces se hace la multiplicación x := x*y en el peor de los casos?
10. Analiza el algoritmo recursivo de exponenciación de la pregunta 8. ¿Cuántas veces se hace la multiplicación power(y²,z/2)*y en el peor de los casos?