Final 26/02/24 (Algoritmos II)

Ejercicio 1

AED: Qué dificultades hay para computar la WP de un ciclo. ¿Como se soluciona en la práctica?

AyED2: ¿Por qué decimos que el algoritmo de Karatsuba para multiplicar enteros es más eficente en peor caso de tiempo que el algoritmo tradicional?

Ejercicio 2

Como puedo sintetizar la postcondición para implementación de un método de un TADs con una representación dada. Brinde un ejemplo (puede ser esquemático)

Ejercicio 3

¿Qué papel juegan los árboles de Fibonacci para justificar la altura máxima de los AVLs?

Ejercicio 4

En un diccionario implementado sobre AVL, cómo implementeria la función Valor*(c: clave) -> valor que dada una clave nos devuelve el dato asociado, en caso de existir la clave en el diccionario ó, si no existe, el valor asociado a la menor clave existente en el diccionario que es mas grande que la clave c (y algun valor especial en el caso de no existir claves más grandes) ¿Qué complejad de peor caso tendría? Justifique correctitud y complejidad con palabras

Ejercicio 5

Tenemos un array de objetos, cada uno de los cuales tiene un atributo información y otro campo color, que puede ser "celeste", "azul" o "negro". Debemos ordenar los elementos en modo tal que todos los celestes queden delante de los azules y estos a su vez queden delante de los negros. Proponer un algoritmo lineal que los ordene cumpliendo ese criterio. No hay restricciones para cómo quedan ordenados los elementos según el valor del campo infomacion. Por restricciones de memoria el algoritmo propuesto puede utilizar solarmente O(1) espacio adicional al requerido para el array de entrada (o sea no puede utiliza arrays auxiliares)