Final 05/03/24 (Algoritmos II)

Ejercicio 1

(AED2): eran tres items sobre arreglar operaciones tipo tad

(AYED): Weakest Precondition e Invariante

  a. Como se computa la weakest precondition de un ciclo?
  b. Por que es necesario introducir el invariante de ciclo para algunos casos?
  c. Por que es necesario que la tripla de hoare {I&B} S {I} sea valida?
  d. De un ejemplo donde se puede probar {I&B} S {I} pero no {I} S {I}

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