Tarea 6 de Análisis de Algoritmos

Trimestre 2010 Invierno
Entrega: 31 de marzo de 2010 en el examen.

1. [5+5 puntos] (a) Diseña un algoritmo que genere todas las cadenas binarias de n bits en el orden del código gray. (b) ¿Cuántos cambios de bits hace tu algoritmo? Justifica tu respuesta.
   
2. [5+5 puntos] (a) Diseña un algoritmo que genere todas las cadenas ternarias de n dígitos (0, 1, 2) que minimice el número de cambios de dígitos. (b) ¿Cuántos cambios de dígitos hace tu algoritmo? Justifica tu respuesta.
3. [5+5 puntos] (a) Diseña un algoritmo que genere todas las permutaciones de {1, 2, ..., n} que minimice el número de asignaciones. (b) ¿Cuántas asignaciones hace tu algoritmo? Justifica tu respuesta.
4. [5+5 puntos] (a) Diseña un algoritmo que genere todas las combinaciones de k elementos tomados de {1, 2, ..., n} que minimice el número de asignaciones. (b) ¿Cuántas asignaciones hace tu algoritmo? Justifica tu respuesta.