Tarea 1 de Análisis de Algoritmos

Trimestre 2009 Otoño
Entrega: 19 de octubre 2009 en clase.

1. [5 puntos] Demuestre por inducción que 1 + 3 + 5 + ... + (2n-1) = n² para toda n >= 1.
2. [5 puntos] Demuestre por inducción que 3ⁿ < n! para toda n >= 7.
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) = 1000n y g(n) = 2n.
2. f(n) = 1000n y g(n) = n².
3. f(n) = 3n²+2n+1 y g(n) = n²+2n+3.
4. f(n) = cos(n) y g(n) = 1.
5. f(n) = sqrt(n) y g(n) = ln(n).