Final 06/12/19 (Algoritmos II)

Final tomado por Nicolás D'Ippolito. Duró 3 horas y se aprobaba con 2 ejercicios bien.

Ejercicio 1

Dado un vector S de N elementos obtenidos iterativamente eligiendo números al azar en el intervalo [0,K], se quiere eliminar los elementos repetidos, permitiéndose reordenar el arreglo. Se proponen tres alternativas.

• Pasar los elementos S a una tabla de hash con encadenamiento S' y copiar S' sobre S
• Hacer quicksort in-place y luego copiar los resultados a un arreglo usando dos indices para evitar copiar los repetidos
• Un algoritmo tipo counting sort que no tiene en cuenta la cantidad de veces que aparece cada elemento

Se testearon las tres soluciones descriptas para vectores de tamaño 200, 20000 y 200000 con K=50000. Pero se mezclaron los resultados con los resultados de otros experimentos y no se puede volver a ejecutar el programa. Decidir cual/es de las siguientes tablas representan los resultados del experimento. Luego dar un algoritmo razonable para otros valores de K.

N	200	20000	200000
hash	19.79	1364.02	6423.2
qsort	43.7	2798.46	14702.7
csort	307.61	328.13	397.43

N	200	20000	200000
hash	150.79	364.02	623.2
qsort	8.56	1253.46	14702.7
csort	307.61	328.13	397.43

N	200	20000	200000
hash	19.79	1364.02	6423.2
qsort	8.56	1253.46	14702.7
csort	149.47	328.13	397.43

N	200	20000	200000
hash	150.79	364.02	632.2
qsort	43.7	2798.46	14702.7
csort	149.47	328.13	397.43

Ejercicio 2

Implementar el algoritmo Floyd usando la técnica Divide & Conquer. Dado un árbol completo T, se debe retornar un árbol H con los mismos elementos que T, pero que cumpla el invariante heap. Se puede asumir que ya tiene implementados siftDown y siftUp con la complejidad adecuada. Dar la complejidad y justificar.

Ejercicio 3

En una implementación de un diccionario con hashing doble, explicar qué pasaría si una de las dos funciones devolviera siempre el mismo valor(explicar qué pasaría si fuera la primera función y qué pasaría si fuera la segunda).

Ejercicio 4

Dados las siguientes situaciones y fragmentos de TADs, indicar cual/es tienen errores y justificar.

• En un laboratorio se tiene un frasco aislado con hielo. Al someterlo al calor, el hielo se derrite a razón de $1dm^{3}$ por caloría. Cómo el frasco se encuentra aislado, esta es la única transformación posible.

 TAD frasco
   generadores:
   nuevoFrasco: tamaño -> frasco
 
   observadores:
   volumen_hielo: frasco -> nat
   volumen_agua: frasco -> nat
 
   operaciones:
   darCalor: frasco x nat -> frasco
   quitarHielo: frasco x nat -> frasco
   darAgua: frasco x nat -> frasco
 Fin TAD

• Se tiene bolita que se puede mover dándole impulsos. Estos impulsos se miden en kilos y, por cada impulso, la bolita de desplaza 2 unidades de distancia.

 TAD bolita
   [...]
   observadores:
   posicion: bolita -> nat
 
   operaciones:
   empujar: bolita x nat i x nat d -> bolita {d = 2i}
   [...]
 Fin TAD

• Se quiere implementar una pila con la función TOP() en el caso en el que la pila no esté vacía.

 TAD Pila
   observadores:
   top: pila -> <elem, bool>
 Fin TAD

• Ídem

 TAD Pila
   top: pila -> indicador
   hay_elem?: indicador -> bool
   elem: pila x indicador i -> elem {hay_elem?(i)}
 Fin TAD