Tarea 3 de Análisis de Algoritmos

Trimestre 2011 Invierno
Entrega: 10 de marzo de 2011 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] Sea N un número entero de n bits. Diseña un algoritmo de divide y vencerás para calcular la parte entera de la raíz cuadrada de N usando O(n) sumas y corrimientos.
   
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.