Examen 3 de Análisis de Algoritmos
Trimestre 2012 Otoño
Entrega: 18:00 del 22 de noviembre de 2012 en G206.
Nombre:
Matrícula:
Instrucciones: Escriba su nombre y matrícula en los
espacios provistos para ello. El valor máximo de este
examen es de 60 puntos y no se otorgarán medios puntos.
Cada pregunta de este examen tiene un valor de 12 puntos. No
olvide justificar todas sus respuestas. La calificación que
obtenga se promediará con la de los otros exámenes.
Pregunta 1 (7+5): Sea n ≥ 1 un entero y suponga que tiene un
vector a1, a2, ..., an
con n enteros. Se desea ordenar esos enteros en un segundo vector b1, b2, ..., bn
de modo que la suma s = |b1 – b2|
+ |b2 – b3| + ... + |bn-1 – bn|
sea tan pequeña como sea posible. (a) Diseñe un
algoritmo glotón para resolver este problema y (b) demuestre
que es correcto.
Pregunta 2 (6+6): Considere el siguiente algoritmo
glotón para el problema del circuito hamiltoniano: Se
comienza en el vertice 1, a cada paso se escoge una arista del
vertice actual a otro vertice que no haya sido visitado antes (a
menos que esa arista regrese al vertice 1). Demuestre con un ejemplo
que (a) aunque la gráfica tenga ciclos a veces este algoritmo
no encuentra ningún ciclo y (b) aunque la gráfica
tenga un ciclo hamiltoniano a veces este algoritmo no encuentra
ningún ciclo hamiltoniano.
Pregunta 3 (2+2+3+5): (a) Diseñe un algoritmo que
genere las 2n cadenas
binarias de n bits, (b) ejecute un ejemplo con n = 4, (c) demuestre
que funciona y (d) calcule el número exacto de operaciones de
bits que hace.
Pregunta 4 (3+6+3): Considere el siguiente algoritmo para
generar permutaciones de x[1], ..., x[n]:
genera1(n)
si n = 1 entonces procesa(x) y regresa
para c desde 1 hasta n
intercambia x[c] con x[n]
genera1(n-1)
intercambia x[c] con x[n]
regresa
(a) Muestre la ejecución del algoritmo con n = 4, (b)
demuestre que funciona, (c) ¿cuántos intercambios
realiza este algoritmo en función de n?
Pregunta 5 (3+6+3): Considere el siguiente algoritmo para
generar permutaciones de x[1], ..., x[n]:
genera2(n)
si n = 1 entonces procesa(x) y regresa
para c desde 1 hasta n
genera2(n-1)
si n es impar b = 1 y si no b = c
intercambia x[b] con x[n]
regresa
(a) Muestre la ejecución del algoritmo con n = 4, (b)
demuestre que funciona, (c) ¿cuántos intercambios
realiza este algoritmo en función de n?