Tarea 6 y Examen 3 de Análisis de Algoritmos
Trimestre 2010 Otoño
Entrega: 9 de diciembre de 2010 a las 18:00.
Cada uno de los siguientes problemas vale un máximo de 10
puntos. No use más de una página para
contestar cada problema. Entregue su tarea y examen engrapados en mi
oficina (H-264) a más tardar el 9 de diciembre de 2010 a las
18:00.
- [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.
- [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.
- [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.
- [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.