Examen 3 de Análisis de Algoritmos

Trimestre 2012 Invierno
Entrega: 29 de marzo de 2012 a las 16:30 en mi oficina.

1. [10+10 puntos] Suponga que tiene un conjunto de N puntos {x₁, x₂, ..., x_N} en la 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.
   
2. [20 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.
   
3. [10+10+10+10 puntos] Suponga que tiene el árbol abarcador de costo mínimo T de una gráfica G. Para cada una de las siguientes cuatro modificaciones de los costos de las aristas diga cómo podría cambiar el árbol abarcador de costo mínimo: (a) se disminuye el costo de una arista que está en T, (b) se aumenta el costo de una arista que está en T, (c) se disminuye el costo de una arista que no está en T y (d) se aumenta el costo de una arista que no está en T.