Tarea 1 de Análisis de Algoritmos

Trimestre 2012 Otoño
Entrega: 25 de septiembre de 2012 en clase.

1. [5 puntos] Demuestra por inducción que si n >= 1 entonces 1³ + 2³ + 3³ + ... + n³ = n²(n+1)²/4.
   
2. [5 puntos] Calcula 1³ + 3³ + 5³ + ... + (2n+1)³ y demuestra tu respuesta por inducción en n >= 0.
3. [5 puntos] Calcula 1/(1*3) + 1/(2*4) + 1/(3*5) + ... + 1/(n*(n+2)) y demuestra tu respuesta por inducción en 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.