Tarea 3 de Análisis de Algoritmos

Trimestre 2013 Invierno
Entrega: 21 de febrero de 2013 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] Suponga que tiene dos bases de datos con n enteros cada una (2n enteros en total, todos distintos) y que quiere encontrar el p-ésimo entero más pequeño en ellas. Puede acceder a las bases de datos a través de consultas del tipo dato(b,k) donde b es 1 o 2 (dependiendo de la base de datos) y 1 <= k <= n a las cuales la base de datos b regresa el k-ésimo entero más pequeño que contiene. Diseñe un algoritmo de divide y vencerás que encuentre el valor buscado usando tan pocas consultas a la base de datos como sea posible. Demuestre que su algoritmo es correcto y calcule el número de consultas que hace en el peor caso.