Tarea 3 de Análisis de Algoritmos

Trimestre 2012 Primavera
Entrega: 12 de junio de 2012 en clase.

1. [10 puntos] Sea T un arreglo de N enteros distintos ordenados de menor a mayor: T[1] < T[2] < ... < T[N]. Diseña un algoritmo de divide y vencerás que decida si existe algún índice I tal que T[I] = I y que termine en O(log N) pasos. Para tu diseño, intenta usar las ideas del funcionamiento de búsqueda binaria.
2. [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. Para tu diseño, intenta usar las ideas del funcionamiento de búsqueda binaria.
   
3. [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.
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.