Tarea 3 de Análisis de Algoritmos

Trimestre 2012 Otoño
Entrega: 18 de octubre de 2012 en clase.

1. [10 puntos] Sea T un arreglo de N enteros distintos ordenados de menor a mayor: T[1] < T[2] < ... < T[N]. Diseñe un algoritmo de divide y vencerás que decida si existe algún índice I tal que T[I] = I y que termine en O(log N) pasos. Para tu diseño, intenta usar las ideas del funcionamiento de búsqueda binaria.
2. [10 puntos] Suponga que se quiere diseñar una variante del algoritmo de Strassen basado en el hecho de que dos matrices de 3 por 3 se pueden multiplicar con m productos en lugar de los 27 usuales. ¿Qué tan pequeño debe ser m para que el algoritmo resultante fuera más rápido que el visto en clase? Justifica tu respuesta.
3. [10 puntos] Sean m y n dos enteros positivos y sean a y b dos vectores de enteros tales que a₁ < a₂ < ... < a_m y b₁ < b₂ < ... < b_n. Sea k un entero positivo <= m+n. Diseñe un algoritmo de divide y vencerás que encuentre el k-ésimo elemento más pequeño de la unión de los elementos de los dos vectores que haga O(log(max(m,n))) comparaciones.
4. [10 puntos] Suponga que tiene un arreglo a[1], a[2], ..., a[n] con n enteros distintos. Se sabe que el arreglo es unimodal, es decir, existe un entero p entre 1 y n tal que los enteros en el arreglo crecen hasta llegar a a[p] y a partir de allí decrecen hasta llegar a a[n]. Diseñe un algoritmo de divide y vencerás que encuentre el valor de p con tan pocas comparaciones entre elementos como sea posible. Demuestre que su algoritmo es correcto y calcule el número de comparaciones que hace en el peor caso.