Tarea 2 de Análisis de Algoritmos

Trimestre 2008 Invierno
Entrega: 28 de abril de 2008 en clase.

1. 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.
2. Sea n una potencia de c > 1. Suponga que T(n) <= b T(n/c) + an para n >= c, que T(1) = e y que b > c. Demuestre que T(n) <= kn^d - fn para d = log_c(b) y algunas constantes k y f. Diga explícitamente cuáles valores de k y f son los más pequeños que funcionan.
3. 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. 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.
5. 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.