Final 06/12/19 (Algoritmos II)

De Cuba-Wiki
Revisión del 23:12 30 ene 2020 de 157.92.27.254 (discusión) (→‎Ejercicio 4: cambio fasco por frasco (se comieron la r))
(difs.) ← Revisión anterior | Revisión actual (difs.) | Revisión siguiente → (difs.)

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: 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