Análisis de algoritmos

Segundo examen parcial

Pregunta 1 (4 puntos): Considere el siguiente algoritmo de divide y vencerás para multiplicar dos números y, z de n bits (con n una potencia de 3):
  1. Si y, z constan de sólo 1 bit entonces simplemente calcule yz. En caso contrario:
  2. Divida y en tres partes a, b, c cada una con n/3 bits.
  3. Divida z en tres partes d, e, f cada una con n/3 bits.
  4. Calcule recursivamente r1 = ad, r2 = (a+b)(d+e), r3 = be, r4 = (a+c)(d+f), r5 = cf, r6 = (b+c)(e+f).
  5. Calcule x = r124n/3 + (r2-r1-r3)2n + (r3+r4-r1-r5)22n/3 + (r6-r3-r5)2n/3 + r5.
(a) Demuestre que x = yz. (b) Demuestre que este algoritmo usa aproximadamente O(n1.63) operaciones de bits.

Pregunta 2 (3 puntos): El algoritmo de Strassen (estudiado en Diseño de Algoritmos) está basado en el hecho de que dos matrices de 2x2 se pueden multiplicar haciendo solo 7 multiplicaciones en lugar de las 8 usuales y corre en tiempo aproximadamente O(n2.81). Suponga que se quiere diseñar una variante del algoritmo de Strassen basada en el hecho de que dos matrices de 3x3 se pueden multiplicar haciendo solo m multiplicaciones en lugar de las 27 usuales. ¿Qué tan pequeña debe de ser m para que el algoritmo resultante sea más rápido que el algoritmo de Strassen? Observe que usted no tiene porque diseñar el algoritmo.

Pregunta 3 (3 puntos): Cuando estudiamos el algoritmo de programación dinámica para calcular árboles binarios de búsqueda óptimos definimos las cantidades p(i) para 1 <= i <= n, q(i) para 0 <= i <= n y w(i,j) = suma[p(h) con i+1 <= h <= j] + suma[q(h) con i <= h <= j] para 0 <= i <= j <= n. Durante el análisis supusimos que las cantidades w(i,j) ya estaban de alguna forma calculadas, pero esto simplemente no es así. Diseñe y analice un algoritmo de programación dinámica para calcular todas las w(i,j). La evaluación de esta pregunta dependerá del tiempo de ejecución de su algoritmo, de la cantidad de memoria que necesite y del orden en el que se generen los valores de w(i,j), el cual debe ser el orden en el que se necesitan para el algoritmo estudiado en clase.

Deben entregarlo el jueves 16 de noviembre en clase.