Tarea 2 de Análisis de Algoritmos

Trimestre 2012 Invierno
Entrega: 9 de febrero de 2012 en clase.

1. [5 puntos] En un montículo cada nodo es menor o igual que sus hijos. Demuestra por inducción en la altura del montículo que cada nodo es menor o igual que sus descendientes.
2. [10 puntos] Dibuja la construcción de un montículo al que se le insertan los elementos 89, 74, 63, 27, 69, 87, 54, 14, 34, 90 en ese orden.
3. [5 puntos] Resuelve exactamente la recurrencia T(1) = 1 y T(n) = 3 T(n-1) + n - 1 para toda n > 1.
4. [10 puntos] Resuelve exactamente la recurrencia T(1) = 1 y T(n) = 2n T(n-1) + n para toda n > 1.
5. [10 puntos] Resuelve exactamente la recurrencia T(1) = 1 y T(n) = 1 + T(1) + T(2) + ... + T(n-1) para toda n > 1.