Final 20/07/18 (Algoritmos II)

Final tomado por Soulignac

Ejercicio 1

Implementar una cola de prioridad en la que guardo valores de tipo T con prioridad n natural y que tome: Insertar, eliminar, cambiar prioridad, eliminar tope O(lg n), tope en O(1).

Ejercicio 2

Me pasan una secuencia const, printearla ordenarda usando O(1) memoria.

Ejercicio 3

Tenes dos vectores S y T con numeros aleatoriamente elegidos entre 0 y 10^6. |S| = 10^4 y |T| = 10^5, T viene ordenado. Queremos hacer la interseccion de ambos. Probamos 3 formas:

a) Metes S en un conjunto S' sobre ABB balanceado y despues por cada uno de T, ves si esta en S'.

b) idem a pero con una tabla de hash con encadenamiento en vez de ABB balanceado.

c) Ordenas S (ponele que con quicksort, algo n*lg(n)) y ves la interseccion entre S y T con un algoritmo estilo merge.

Luego de las pruebas, sabemos que el a tardo el doble que el b y el b tardo 4 veces que el c. Explicar por que, y conjeturar que pasaria si |S| = 10^3 y si |S| = 10^5.

Ejercicio 4

Tengo que hacer una estructura que me mantenga ordenada una secuencia de datos aleatorios uniformes que me llegan, de forma practica, que estructura usaria? Y si en vez de forma aleatoria, puede haber un adversario, cambiaria de estructura?