Tarea 6 de Análisis de Algoritmos

Trimestre 2012 Primavera
Entrega: 10 de julio de 2012 en clase.

1. [5+5 puntos] Suponga que tiene un conjunto de N puntos {x₁, x₂, ..., x_N} 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.
2. [5+5 puntos] Suponga que tiene un conjunto de N puntos {x₁, x₂, ..., x_N} 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.
3. [5+5 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. (a) Diseñe un algoritmo que encuentre el menor producto punto posible. (b) Demuestre que su algoritmo es correcto. Pista: haga algunos ejemplos a mano hasta que se dé cuenta de lo que está pasando.
4. [5+5 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 grande como sea posible. Recuerde que el producto punto de a y c está dado por a₁c₁ + a₂c₂ + ... + a_nc_n. (a) Diseñe un algoritmo que encuentre el mayor producto punto posible. (b) Demuestre que su algoritmo es correcto. Pista: haga algunos ejemplos a mano hasta que se dé cuenta de lo que está pasando.