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

Fecha de entrega: 7 de noviembre de 2006 en clase

1. [3 puntos] Demuestre que el siguiente fragmento de programa escrito en C para calcular el cociente q y el residuo r de la división de dos números naturales y entre z es correcto. Pista: Demuestre que a cada paso del segundo ciclo se cumplen los invariantes r_j < w_j y q_j*w_j + r_j = y₀.
   
   int q, r, w, y, z;
   r = y;
   q = 0;
   w = z;
   while (w <= y)
     w = 2*w;
   while (w > z) {
     q = 2*q;
     w = w/2; /* esta es la division de enteros, pero se puede hacer con un desplazamiento >> de bits */
     if (w <= r) {
       r = r-w;
       q = q+1;
     }
   }
   
2. [3 puntos] Diseñe un algoritmo no recursivo para encontrar el máximo y el mínimo de los elementos de un vector con n componentes (puede suponer que n es par) que haga exactamente 3n/2-2 comparaciones. Demuestre que su algoritmo hace ese número de comparaciones. Pista: Divida las n componentes en n/2 parejas y luego...
3. [4 puntos] Diseñe un algoritmo que use la técnica de divide y vencerás para encontrar el máximo y el mínimo de los elementos de un vector con n componentes que haga exactamente techo(3n/2)-2 comparaciones para cualquier valor de n. Demuestre que su algoritmo hace ese número de comparaciones. Pista: El algoritmo visto en clase hace más comparaciones que las pedidas. Una forma de resolver este problema es separando las n componentes en ciertos conjuntos disjuntos (el punto crucial es descubrir cómo llevar a cabo esta descomposición) y luego ejecutar el algoritmo recursivo visto en clase en los subconjuntos.