Tarea 1 de Análisis de Algoritmos

Trimestre 2012 Primavera
Entrega: 24 de mayo de 2012 en clase.

1. [5 puntos] Demuestra por inducción que si n >= 1 entonces 1² + 2² + 3² + ... + n² = n(n+1)(2n+1)/6.
   
2. [5 puntos] Demuestra por inducción que si n >= 0 entonces 1² + 3² + 5² + ... + (2n+1)² = (n+1)(2n+1)(2n+3)/3.
3. [5 puntos] Demuestra por inducción que si n >= 1 entonces 1/(1*2) + 1/(2*3) + 1/(3*4) + ... + 1/(n*(n+1)) = n/(n+1).
4. [5 puntos] Demuestra que el siguiente algoritmo para intercambiar dos números x, y es correcto:
   
   intercambia(x, y)
   
   1. x := x+y
   2. y := x-y
   3. x := x-y
5. [10 puntos] Demuestra que el siguiente algoritmo iterativo para calcular la exponenciación y^z es correcto:
   
   potencia(y, z)
   

   1. x := 1
   2. mientras z > 0
   1. x := x*y
   2. z := z-1
   3. regresa x
6. [10 puntos] Demuestra que el siguiente algoritmo recursivo para calcular la exponenciación y^z es correcto:
   
   potencia(y, z)
   

   1. si z = 0 entonces regresa 1
   2. si z es impar entonces regresa potencia(y², z/2)*y
   3. en caso contrario regresa potencia(y², z/2)
   Debes suponer que la división z/2 regresa sólo la parte entera de la división.