Tarea 4 de Análisis de Algoritmos

Trimestre 2009 Otoño
Entrega: 9 de diciembre de 2009 en el examen.

1. [10 puntos] Demuestre por inducción que el siguiente algoritmo procesa todas las cadenas binarias de n bits:
   
   procedimiento genera(n)
   si n = 0 entonces procesa(B)
   si no {genera(n-1); complementa(B[n]); genera(n-1)}
   
   donde complementa quiere decir cambiar un 0 por un 1 o viceversa.
2. [5 puntos] Calcule la cantidad exacta T(n) de asignaciones que se hacen a elementos del arreglo B cuando se llama al algoritmo genera(n). Justifique su cálculo por inducción.
3. [10 puntos] Diseñe un algoritmo bin(n,k) de búsqueda con retroceso que procese todas las cadenas binarias de n bits que tengan exactamente k bits en 1 y los demás bits en 0. Demuestre que funciona.
4. [5 puntos] Calcule el tiempo de ejecución T(n,k) de su algoritmo bin(n,k). ¿Es óptimo su algoritmo? ¿Porqué?