Final 20/07/18 (Algoritmos II)
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]
Se tiene una secuencia const (su contenido no puede ser alterado). Poponer un algoritmo que la muestre en orden (asc o desc). El algoritmo debe tener complejidad espacial constante ( O(1) )
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?
