Tarea 5 de Análisis de Algoritmos

Trimestre 2008 Invierno
Entrega: 10 de junio de 2008 a las 15:00.

1. Calcule la cantidad exacta T(n) de asignaciones que se hacen a elementos del arreglo A cuando se llama al algoritmo visto en clase binaria(n). Justifique su cálculo por inducción.
2. 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.
   
3. 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.
4. 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 otros n-k bits en 0. Demuestre que funciona.
5. Calcule el tiempo de ejecución T(n,k) de su algoritmo bin(n,k). ¿Es óptimo su algoritmo? ¿Porqué?