Tarea 2 de Análisis de Algoritmos

Trimestre 2011 Invierno
Entrega: 3 de marzo de 2011 en clase.

1. [5 puntos] En un montículo cada nodo es mayor o igual que sus hijos. Demuestra por inducción en la altura del montículo que cada nodo es mayor o igual que sus descendientes.
2. [10 puntos] Dibuja la construcción de un montículo al que se le insertan los elementos 10, 2, 9, 16, 8, 6, 1, 3, 12, 5 en ese orden.
3. [5 puntos] Resuelve exactamente la recurrencia T(1) = 1 y T(n) = 2 T(n-1) + n - 1 para toda n > 1.
4. [10 puntos] Resuelve exactamente la recurrencia T(1) = 1 y T(n) = n T(n-1) + n para toda n > 1.
5. [10 puntos] Escribe un programa llamado recurrNN tal que lea cinco enteros positivos a, b, c, d y k y que encuentre el valor exacto de T(c^k) donde T(1) = d y T(n) = a T(n/c) + bn para toda n > 1. Usa el tipo unsigned long long int para todos los cálculos que hagas.