Final 01/02/23 (Algoritmos II)
Ejercicio 1
Problemas de axiomatizar otras operaciones sobre generadores. Dar un ejemplo de una operación que rompa la congruencia y otro que no.
Ejercicio 2
Explicar el invariante de un árbol binario. Explicar por qué queremos árboles balanceados y consecuencia en sus algoritmos dar ejemplos de árboles balanceados y no balanceados.
Ejercicio 3
Era de tablas de hash. Explicar que función/característica tiene que cumplir la función de hash. Por qué no es bueno tener como clave de una tabla hash un objeto mutable como una lista. Sean a , b enteros b no negativo X = a ^ b
Ejercicio 4
Dar la estructura de divide and conquer en un array. Cómo obtener complejidad logarítmica en un algoritmo. Que modificación hay que hacer a búsqueda binaria para que de lineal.
Ejercicio 5
SelectionSort, insertionSort, mergeSort, heapSort y quickSort. A cuáles puedo cortar meter elementos nuevos y seguir. Cuáles son aptos sin modificaciones con modificaciones y no aptos.