Tarea 5 de Análisis de Algoritmos

Trimestre 2012 Otoño
Entrega: 13 de noviembre de 2012 en clase.

1. [5+5 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. [10 puntos] Se tienen dos vectores de enteros positivos a = (a₁, a₂, ..., a_n) y b = (b₁, b₂, ..., b_n). Se desea permutar los elementos de b para obtener un tercer vector c = (c₁, c₂, ..., c_n) tal que el producto punto de a y c sea tan pequeño como sea posible. Recuerde que el producto punto de a y c está dado por a₁c₁ + a₂c₂ + ... + a_nc_n. Diseñe un algoritmo que encuentre el menor producto punto posible y demuestre que su algoritmo es correcto. Pista: haga algunos ejemplos a mano hasta que se dé cuenta de lo que está pasando.
3. [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.
4. [5+5 puntos] Suponga que tiene el árbol abarcador de costo mínimo T de una gráfica G. Para cada una de las siguientes dos 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.