Tarea 2 de Análisis de Algoritmos

Trimestre 2009 Otoño
Entrega: 9 de noviembre 2009 en clase.

1. [15 puntos] Resuelva exactamente cada una de las siguientes funciones recursivas y demuestre que su respuesta es correcta: (a) T(1) = 1 y T(n) = 2T(n-1) + n - 1 para toda n >= 2, (b) T(1) = 1 y T(n) = 1 + T(1) + T(2) + ... + T(n-1) para toda n >= 2, (c) T(1) = 1 y T(n) = T(piso(n/2)) + T(techo(n/2)) + n - 1 para toda n >= 2, donde piso(x) es el mayor entero que es a lo sumo x.
2. [5 puntos] Sea n una potencia de c > 1. Suponga que T(n) <= T(n/c) + an para n >= c y que T(1) = b. Demuestre que T(n) <= kn^d para algunas constantes k y d. Diga explícitamente cuáles valores de k y d son los más pequeños que funcionan.
3. [10 puntos] Sean c y k dos constantes enteras positivas. Demuestre que la solución a la recurrencia T(n) = 0 para 0 <= n < c y T(n) = 2T(n-c) + k para n >= c es de la forma T(n) = O(dⁿ) para alguna constante d.
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.