Diferencia entre revisiones de «Final 06/12/19 (Algoritmos II)»

De Cuba-Wiki
Sin resumen de edición
Sin resumen de edición
Línea 51: Línea 51:
|}
|}
== Ejercicio 2 ==
== 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.
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 ==
== 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).
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).

Revisión del 23:44 6 dic 2019

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 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: fasco -> nat
   volumen_agua: fasco -> nat
 
   operaciones:
   darCalor: frasco x nat -> frasco
   quitarHielo: fasco 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