Tarea 2 de Análisis de Algoritmos

Trimestre 2013 Invierno
Entrega: 4 de febrero de 2013 en el H288 de 15:00 a 17:00

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.