Diferencia entre revisiones de «Final 20/07/18 (Algoritmos II)»
(Página creada con «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, ca...») |
|||
| Línea 5: | Línea 5: | ||
== Ejercicio 2 == | == Ejercicio 2 == | ||
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 == | == Ejercicio 3 == | ||
Revisión actual - 20:48 1 ago 2019
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
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
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?
