Diferencia entre revisiones de «Final 05/03/24 (Algoritmos II)»
De Cuba-Wiki
(Página creada con « == Ejercicio 1 == (AED2) eran tres items sobre arreglar operaciones tipo tad == Ejercicio 2 == Describir o demostrar la inexistencia de alguna estructura sobre colas de prioridad con las siguientes operaciones: a. Agregar elemento en O(1) y sacar mínimo elem en O(n) b. Agregar elemento en O(n) y sacar minimo elem en O(1) c. Agregar elemento y sacar mínimo en O(log n) d. Agregar elemento y sacar mínimo en O(log log n) La descripción tiene que incl…») |
|||
| Línea 12: | Línea 12: | ||
== Ejercicio 3 == | == Ejercicio 3 == | ||
a. Explicar con palabras cual es el invariante que hace un ABB un AVL | a. Explicar con palabras cual es el invariante que hace un ABB un AVL | ||
b. Dar un algoritmo en tiempo lineal que verifique que un ABB sea un AVL | b. Dar un algoritmo en tiempo lineal que verifique que un ABB sea un AVL | ||
c. Dar un ejemplo de borrado de un elemento en AVL que requiera mas de 1 rotacion | c. Dar un ejemplo de borrado de un elemento en AVL que requiera mas de 1 rotacion | ||
Revisión del 15:00 4 abr 2024
Ejercicio 1
(AED2) eran tres items sobre arreglar operaciones tipo tad
Ejercicio 2
Describir o demostrar la inexistencia de alguna estructura sobre colas de prioridad con las siguientes operaciones:
a. Agregar elemento en O(1) y sacar mínimo elem en O(n) b. Agregar elemento en O(n) y sacar minimo elem en O(1) c. Agregar elemento y sacar mínimo en O(log n) d. Agregar elemento y sacar mínimo en O(log log n)
La descripción tiene que incluir el invariante de representación y la función abstracción.
Ejercicio 3
a. Explicar con palabras cual es el invariante que hace un ABB un AVL b. Dar un algoritmo en tiempo lineal que verifique que un ABB sea un AVL c. Dar un ejemplo de borrado de un elemento en AVL que requiera mas de 1 rotacion
Ejercicio 4
Cómo haciamos para determinar la cota inferior para todos los algoritmo de ordenamiento que no tenga ninguna hipotesis extra sobre el arreglo de entrada?
Ejercicio 5
En un caso hipotetico en donde un programador se equivoca en la implementacion del hashing doble haciendo que una función siempre sea constante. Explicar que pasaria en el caso de que la primera funcion sea cte y que pasaria si la segunda funcion sea cte
