PROBLEMA 1: Diseñe un algoritmo que permita encontrar los k elementos menores de un conjunto de manaño N, en tiempo N logK y memoria k. La lista de elementos debe estar ordenada de menor a mayor.

Solución:

Estructura:

Consideremos un heap de tamaño k.

Algoritmos:

1. Se leen los primeros k elementos del arreglo y se insertan en el heap.
2. Desde el k + 1­ésimo elemento se procede de la siguiente forma:
   1. Si el número leído es mayor que la raíz del heap, se desecha.
   2. Si el número leído es menor que la raíz del heap, entonces se saca un elemento del heap (en este caso el mayor) y se inserta el nuevo elemento.

Ahora consideramos que el heap es un arreglo tradicional y lo ordenamos.
Para esto se realiza el mismo procedimiento que en el algoritmo de ordenamiento Heapsort, o cualquier otro visto en clases que no ocupe otro arreglo adicional (Qsort, por ejemplo), una vez que se ha transformado en heap el arreglo a ordenar.

Análisis:

En el peor caso, por cada elemento leído se realiza una inserción y una extracción del heap, con costo O(log k) comparaciones cada una de ellas (el heap es de largo k), como son N elementos, en el peor caso se realizan N O(logk) comparaciones en la selecci'on de menores.
Más el procedimiento de ordenación que toma tiempo O(k log k) (hay k elementos en el arreglo de menores).

El procesamiento completo (búsqueda de menores y ordenamiento del arreglo de menores) toma NO(logk) + O(k log k) = O(N log k) comparaciones.

Seudo­código:

//Llenado inicial de myHeap
for (i=0..K­1) myHeap.insert(Temp[i])
//Ahora obtengo los elementos menores

for (i=K..N­1) {
  if(Temp[i] < myHeap.valueOfRoot()) {
    // el valor de Temp[i] es menor al valor de la raiz del heap
    myHeap.removeRoot();
    myHeap.insert(temp[i]);
    //en myHeap quedan los K menores hasta la iteracion i­esima
  }
}

//en myHeap estan los K elementos menores
//ahora considero a myHeap como un arreglo corriente, y lo ordeno
myHeap.Heapsort();
//en myHeap estan las K temperaturas menores, ordenadas, se pueden imprimir en
//pantalla, o retornarla, etc.
System.out.println(myHeap);

PROBLEMA 2: Se dice que una función de hashing h preserva el orden si para todo par de llaves x, y, se tiene que si x < y entonces h(x) es menor o igual a h(y).

1. Escriba un programa que utilice una tabla de hashing con encadenamiento para ordenar un arreglo de n elementos, suponiendo que la función de hashing preserva el orden. Antes de presentar el programa, describa su algoritmo en palabras
2. Si m es el tamaño de la tabla y alfa = n/m es el factor de carga, calcule en forma aproximada el tiempo total que demora el proceso de ordenación (suponga que la función distribuye los elementos uniformemente en la tabla). Comente la relación entre este tiempo y la cota inferior de orden nlogn vista en clases.

parte 1.

1. Como es una función de hashing creciente, y con distribución uniforme la vamos a utilizar para separar el conjunto inicial en m conjuntitos de tamaño alfa = n/m.
2. Ahora pegamos todas las subsecuencias, con eto obtendremos una lista semiordenada donde los elementos de una subsecuencia son mayores que los de la subsecuencia anterior, y menores que la siguiente
3. Ahora con una variación de burbuja se termina de ordenar el arreglo semi ordenado. Lo que sucede es que la burbuja se mueve a lo más m espacios en una subsecuencia, y cuando pasa a la otra subsecuencia mueve otro elemento, la burbuja termina cuando no hay desplazamientos.

El programa escribanlo ustedes

parte 2.

La solución propuesta cuesta:
N operaciones de Hash
m listas * (tamaño de la lista más larga) comparaciones de llaves

suponiendo que la operacion de Hash es O(1), y a comparación también es O(1) y la distribución es uniforme esto cuesta O(N). ¿Por qué?, tarea para la casa

PROBLEMA 3: Considere un arreglo desordenado de tamaño N. Considere además que hay elementos repetidos, siendo r la cantidad de repeticiones de un elemento. Diseñe un algoritmo que ordene los elementos en tiempo O(Nlogr)

Solución:

Estructura:

Un AVL, donde el nodo tiene cuatro campos:

1. Información de tipo real
2. Número de repeticiones
3. hijo derecho
4. hijo izquierdo

Algoritmos:

AVL a;
real datos;

// inserción de datos al árbol
for (i= 1..N) a.add(datos[i]);

// extraccón de datos del árbol
a.printInOrden();


// Método para agregar elementos
firma: a.add(float item)
cuerpo:
  AVL s;
  s = a.buscar(item);
  if (s == NULL) {
    inserción usual en AVL, con número de repeticiones = 1;
  }
  else {
    s.repeticiones++;
  }

// Método para recorrer en inorden
firma: a.printInOrden()
cuerpo:
  if (this == NULL) return;
  this.izq.printInOrden();
  for (i = 1..this.repeticiones) Sop(this.info + " ");
  this.der.printInOrden();