Tarea 4 de Análisis de Algoritmos

Trimestre 2008 Invierno
Entrega: 16 de mayo de 2008 en clase.

1. 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.
   
2. 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.
   
3. Suponga que una gráfica conexa G = (V, E) tiene costos distintos en todas sus aristas. Demuestre que G tiene un único árbol abarcador de costo mínimo. Pista: ¿qué pasa cuando se le aplica el algoritmo de Prim o el algoritmo de Kruskal a esta gráfica?
   
4. Suponga que una gráfica conexa G = (V, E) tiene costos distintos en todas sus aristas excepto por dos que tienen el mismo costo. ¿Será cierto que G tiene un único árbol abarcador de costo mínimo? Dé una demostración de que es verdadero o un ejemplo que muestre que es falso.
5. Sea m >= 2 un entero. Suponga que se tienen n >= 1 tipos de monedas con valores 1, m, m², ..., m^n-1. Se desea completar una cantidad c >= 0 usando tan pocas de estas monedas como sea posible. Diseñe un algoritmo que resuelva este problema y demuestre que su algoritmo es correcto. Pista: ¿se podrían tener m o más monedas del mismo tipo en una solución óptima?
6. Opcional para puntos adicionales. Suponga que una gráfica conexa G = (V, E) tiene costos positivos y negativos en sus aristas. Se desea encontrar una subgráfica abarcadora conexa H = (V, F) de G (es decir, una donde F es un subconjunto de E) tal que la suma de los costos de sus aristas sea tan pequeña como sea posible. Diseñe un algoritmo que resuelva este problema y demuestre que su algoritmo es correcto. Pista: haga algunos ejemplos a mano hasta que se dé cuenta de lo que está pasando.