Tarea 1 de Análisis de Algoritmos

Trimestre 2010 Otoño
Entrega: 7 de octubre de 2010 en clase.

1. [5 puntos] Sea S(n) = 0*1+1*2+2*3+...+(n-1)*n. Encuentra cuatro números a, b, c y d tales que S(n) = an³ + bn² + cn + d. Demuestra tu respuesta por inducción en n.
   
2. [5 puntos] Considera el siguiente juego de dos jugadores: Hay N cerillos en una mesa. El primer jugador puede quitar 1 o 3 cerillos. El segundo jugador puede quitar 1 o 2 cerillos. El jugador que quita el último cerillo gana el juego. ¿Para cuáles valores de N el primer jugador puede ganar el juego independientemente de lo que haga el segundo jugador? Justifica tu respuesta por inducción en N.
   
3. [5+5 puntos] Para cada pareja de funciones f y g ¿será cierto que f(n) es O(g(n)) o g(n) es O(f(n))? Demuestra tu respuesta por inducción en n.
1. Sean f(n) = 3(n² + 2n) y g(n) = 60n.
2. Sean f(n) = n² + log n y g(n) = n^3/2.
4. [10 puntos] Demuestra que el siguiente algoritmo iterativo para incrementar un entero es correcto:
   
   incrementa(y)
   

   x = 0
   c = 1
   d = 1
   mientras (y > 0) o (c > 0)
   

   a = y MOD 2
   si a XOR c entonces x = x+d
   c = a AND c
   d = 2d
   y = y/2
   

   regresa (x)
   
   Las funciones AND, XOR y MOD son las operaciones de "y de bits", "o exclusiva de bits" y módulo, respectivamente. Observa que la línea del XOR parece contener una trampa. ¿Cómo se puede hacer esta operación sin sumar?
   
5. [10 puntos] Demuestra que el siguiente algoritmo recursivo para incrementar un entero es correcto:
   
   incrementa(y)
   

   si y = 0 regresa 1
   si no entonces
   

   si y MOD 2 = 1 entonces regresa (2 * incrementa(y/2))
   si no regresa(y+1)
   
   Observa que la última línea parece contener una trampa. ¿Cómo se puede hacer esta operación sin sumar?