Tarea 2 de Análisis de Algoritmos

Trimestre 2010 Otoño
Entrega: 21 de octubre de 2010 en clase.

1. [5 puntos] En un montículo cada nodo es menor que sus hijos. Demuestra por inducción en la altura del montículo que cada nodo es menor que sus descendientes.
2. [10 puntos] Dibuja la construcción de un montículo al que se le insertan los elementos 63, 40, 25, 64, 70, 35, 67, 34, 56, 73 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) = n T(n-1) + n - 1 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.