Tarea 3 de Análisis de Algoritmos

Trimestre 2010 Otoño
Entrega: 4 de noviembre de 2010 en clase.

1. [10 puntos] Supón que se quiere diseñar una variante del algoritmo de multiplicación de enteros largos visto en clase en donde cada entero de n bits se divide en tres partes, por ejemplo x = a2^2n/3 + b2^n/3 + c, y = d2^2n/3 + e2^n/3 + f. En este caso z = xy = ad2^4n/3 + (ae+bd)2^3n/3 + (af+be+cd)2^2n/3 + (bf+ec)2^n/3 + cf, es decir, parece que se necesitan hacer 9 multiplicaciones de n/3 bits para calcular 5 coeficientes. (a) Plantea y resuelve la ecuación recurrente del tiempo de ejecución para este algoritmo. (b) ¿Cuántas multiplicaciones de n/3 bits se necesitaría hacer para calcular los 5 coeficientes de modo que el algoritmo resultante fuera más rápido que el visto en clase? Justifica tu respuesta.
2. [10 puntos] Supón 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] 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.
4. [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ña 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.