Tarea 1 de Análisis de Algoritmos

Trimestre 2012 Invierno
Entrega: 7 de febrero de 2012 en clase.

  1. [5 puntos] Sea T(n) = 1*2+2*3+3*4+...+n*(n+1). Encuentra cuatro números a, b, c y d tales que T(n) = an3 + bn2 + 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) = 50(n2 - 2n) y g(n) = 6n2.
    2. Sean f(n) = 2n + log n y g(n) = 3n1/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?