Edición de «Final 06/12/19 (Algoritmos II)»

Final tomado por Nicolás D'Ippolito. Duró 3 horas y se apruebaba 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.
{| class="wikitable"
|-
! 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
|}

{| class="wikitable"
|-
! 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
|}

{| class="wikitable"
|-
! 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
|}

{| class="wikitable"
|-
! 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 <math>1dm^3</math> 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'''