Final 20/07/18 (Algoritmos II)

De Cuba-Wiki
Saltar a: navegación, buscar

Final tomado por Soulignac

Ejercicio 1[editar]

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[editar]

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


Ejercicio 3[editar]

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[editar]

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?