Tarea 4 de Análisis de Algoritmos (2006 Otoño)

Fecha de entrega: 5 de noviembre de 2006 en clase

1. [4 puntos] Analice el siguiente algoritmo recursivo permuta(n) para generar permutaciones de a[1], ..., a[n]. En particular, demuestre que funciona y calcule el número de intercambios hechos:
   (a) Si n = 1 procesa(a) y regresa.
   (b) Para c desde 1 hasta n has:
   (b1) permuta(n-1).
   (b2) Si n es par intercambia a[c] con a[n] y si no intercambia a[1] con a[n].
   
2. [3 puntos] Suponga que tiene un grupo con 2n estudiantes y que los quiere acomodar en n parejas. ¿De cuántas formas distintas D(n) se puede hacer esto? Por ejemplo, si n=2 entonces los cuatro estudiantes 1, 2, 3, 4 se pueden acomodar de las siguientes tres formas: (12, 34), (13, 24) y (14, 23).
   
3. [3 puntos] Diseñe y analice un algoritmo para encontrar todas las posibles formas de acomodar a los 2n estudiantes en n parejas que corra en tiempo O(D(n)).