Tarea 2 de Análisis de Algoritmos

Trimestre 2007 Primavera
Entrega: 12 de junio de 2007 en clase.

1. 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.
2. Diseñe y analice un algoritmo tal que, dados un montículo ascendente (es decir, uno donde cada padre es menor que sus hijos) con N elementos almacenado en el arreglo A[1], ..., A[N] y un índice I (con 1 <= I <= N) borre el elemento A[I] del montículo en tiempo O(log n). Escriba un programa en C (gcc), C++ (g++), Pascal (fpc) o Java (gcj) llamado borrarZZ (donde ZZ es una clave de dos dígitos asignada por el profesor) basado en su algoritmo que reciba como acepte como entrada dos enteros N e I y un montículo ascendente A[1], ..., A[N] y escriba como salida un montículo ascendente B[1], ..., B[N-1] que corresponda con A al que se le ha borrado el elemento A[I]. Puede suponer que 1 <= I <= N <= 1000.
   
3. 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.