Tarea 2 de Análisis de Algoritmos

Trimestre 2008 Otoño
Entrega: 6 de noviembre de 2008 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] Demuestre por inducción que un montículo con n vértices tiene exactamente techo(n/2) hojas, donde techo(x) es el menor entero que es al menos x.
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 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.