Tarea 5 de Análisis de Algoritmos
Trimestre 2013 Invierno
Entrega: 26 de marzo de 2013 en clase.
- [5+5 puntos] Suponga que tiene un conjunto de N puntos {x1,
x2,
..., xN} en una línea
recta y los desea cubrir con intervalos de
longitud 1. (a) Describa un algoritmo glotón que cubra los
puntos con tan pocos intervalos como sea posible. (b) Demuestre
que su
algoritmo funciona.
- [5+5 puntos] Suponga que tiene un conjunto de N puntos {x1,
x2,
..., xN} en una circunferencia
y los desea cubrir con arcos
de
longitud 1. (a) Describa un algoritmo glotón que cubra los
puntos con tan pocos arcos como sea posible. (b) Demuestre que
su
algoritmo funciona.
- [10 puntos] Muestre un ejemplo de una gráfica con costos
positivos en
sus aristas tales que al aplicar el algoritmo de Dijkstra el
árbol de caminos más cortos no
es un árbol abarcador de
costo mínimo.
- [10 puntos] Modifique el algoritmo de Dijkstra de la siguiente
manera: Al principio, todas las distancias al origen se
establecen en
infinito negativo. Después, en lugar de extraer la distancia
más corta se extrae la más larga. Finalmente, en la
actualización escoge la nueva distancia como la más
grande de las dos opciones. Demuestre (con un ejemplo) que este
algoritmo NO encuentra la longitud de los caminos más largos
desde el vértice inicial a todos los demás.