Tarea 1 de Análisis de Algoritmos

Trimestre 2008 Otoño
Entrega: 21 de octubre 2008 en clase.

1. [5 puntos] Demuestre por inducción que 1*1 + 2*2 + 3*3 + ... + n*n = n(n+1)(2n+1)/6 para toda n >= 1.
2. [5 puntos] Demuestre por inducción que n³ <= 2ⁿ⁺² para toda n >= 4.
3. [10 puntos] Demuestre que el siguiente algoritmo para calcular y^z es correcto:
   
   x := 1
   mientras z > 0 haz
   
   si z es impar entonces x := xy
   z := z/2 (parte entera)
   y := y²
   
   regresa x
   
4. [5 puntos] Suponga que en el algoritmo anterior z tiene n bits. Calcule el número máximo M(n) de multiplicaciones que realiza el algoritmo. Observe que hay un máximo de dos multiplicaciones en el cuerpo del ciclo.
   
5. [15 puntos] Para cada una de las siguientes parejas de funciones decida si f(n) es O(g(n)) o no. Diga qué es lo correcto y demuéstrelo:
1. f(n) = n, g(n) = 3n.
2. f(n) = 2n², g(n) = n³.
3. f(n) = 3n², g(n) = n + log₂ n.
4. f(n) = n + log₂ n, g(n) = n.
5. f(n) = n + log₂ n, g(n) = log₂ n.