Tarea 3 de Análisis de Algoritmos

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

1. Diseñe y analice un algoritmo de divide y vencerás para encontrar la parte entera de la raíz cuadrada de un entero N de n bits utilizando O(n) sumas y desplazamientos.
   
2. Sean a y b dos reales positivos tales que a+b=1. Demuestre que si quicksort parte su lista de entrada de tamaño n en dos listas de tamaños an y bn usando n comparaciones entonces el tiempo de ejecución de quicksort es O(n log n). Nota: Si a = b = 1/2 entonces tenemos el análisis que hicimos en clase y si a = 1/3 y b = 2/3 entonces esta es la pregunta del examen.
   
3. Diseñe y analice un algoritmo de divide y vencerás para el problema de las torres de Hanoi con 4 agujas que haga tan pocos movimientos como le sea posible. Nota: existe un algoritmo de divide y vencerás que hace O(n 2^sqrt(2n)) movimientos para mover n discos de una aguja a otra.