Tarea 6 de Análisis de Algoritmos

Trimestre 2012 Otoño
Entrega: 18:00 del 22 de noviembre de 2012 en G206.

1. [10+10 puntos] Considera el siguiente algoritmo iterativo que genera cadenas binarias de N bits en el arreglo C[1], ..., C[N], usando dos posiciones adicionales C[0] y C[N+1]:
   Para i de 0 a N+1
      C[i] = 0
   mientras C[n+1] = 0
      procesa(C)
      incrementa(C)
   donde además incrementa(C) está dada por:
   i = 1
   mientras C[i-1] = 0
      complementa el bit C[i]
      i = i+1
   (a) Demuestra que procesa(C) se llama exactamente una vez con cada cadena de N bits. (b) Demuestra que la cantidad de veces que se complementa algún bit es exactamente igual a 2^N+1 - N - 2.
   
2. [10+10 puntos] Considera el siguiente algoritmo recursivo que genera cadenas binarias de N bits en el arreglo C[1], ..., C[N]:
   genera(N)
      si N = 0 entonces procesa(C)
      en caso contrario
         genera(N-1)
         complementa el bit C[N]
         genera(N-1)
   (a) Demuestra que procesa(C) se llama exactamente una vez con cada cadena de N bits. (b) Demuestra que la cantidad de veces que se complementa algún bit es exactamente igual a 2^N - 1.