Final 01/03/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 B-tree (no confundir con arbol binario, es otra estructura). 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.