Final 1C/2011 (Algoritmos II)

Ejercicio 1

Verdadero o Falso, justifique o dé un contraejemplo:

• a. Si f es O(g) y g es Ω(f), f es Θ(g)?
• b. Si f es O(n), entonces para cualquier entrada f es Ω(n)
• c. Si f es Ω(n), entonces para cualquier entrada f es Θ(n)
• d.

Ejercicio 2

Sea S una secuencia de inserciones sobre un Arbol binario de Busqueda, donde S = { s1, s2, s3, s4, s5, s6, s7} donde s1 <= s2 <= s3 ... <= s7, describir las permutaciones de S que formen lo siguiente

• a. Un arbol de altura minima
• b. Un arbol de altura máxima

Ejercicio 3

Dada la siguiente especificación sobre una cena con participantes, encuentre los errores y corríjalos (axiomatice o describa como arreglar el error)

Tad Persona

generadores

nueva edad × dni → persona

observadores

. = . persona × persona → bool

Tad Cena

generadores

crear conj(personas) → cena

llega_invitado persona × plato x × cena → cena

observadores

invitados cena → conj(personas)

que_plato_trajo? persona p × cena c → plato { p ∊ invitados(c) }

suma_de_edades cena → nat

Tad Regalo es Nat

Ejercicio 4

Se quiere implementar un diccionario sobre una novedosa estructura x, se quiere dividir el trabajo entre 3 personas de la siguiente manera:

A) Escribe la interfaz B) Escribe algoritmos de inserción y borrado C) Escribe algoritmos de busqueda

Que le daria como minimo de la siguiente lista a cada uno como para que puedan hacer su trabajo, justificar y sea conciso.

TAD Dicc

TAD X

invariante de representacion de dicc sobre x

invariante de repr de x

funcion de abs de x

funcion de abs de diccionario sobre x

interfaz de x

Ejercicio 5

Se quiere implementar conjunto y diccionario cuyas operaciones tipicas sean en orden logaritmico (insertar, borrar, buscar o sus equivalentes). De los siguientes diseños, diga cual usaria y porque, si no le convence ninguna proponga una y justifique

• a. Dicc y Conjunto sobre AVL, AVL sobre punteros a nodos
• b. AVL sobre ABB, ABB sobre AB, AB sobre nodos, Dicc y Conj sobre AVL
• c.
• d.