Tarea 1 de Análisis de Algoritmos

Trimestre 2010 Invierno
Entrega: 25 de enero de 2010 en clase.

1. [5 puntos] Sea S(n) = 1*2+2*3+...+n*(n+1). Encuentra dos números a y b tales que S(n) = an³ + bn. 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, 2 o 3 cerillos. El segundo jugador puede quitar 2, 4 o 6 cerillos. El jugador que quita el último cerillo gana el juego. Demuestra por inducción que si N es par entonces el primer jugador siempre puede ganar el juego independientemente de lo que haga el segundo jugador.
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) = (n² - 2n)/2 y g(n) = 6n.
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?