Final 2/2C/2007 (Algoritmos II)

Plantilla:Back Esteban Feuerstein y Fernando Schapachnik

Ejercicio 1

Explicar las consecuencias en el desarrollo de un software si se tienen en la especificacion los siguientes errores:

• Funciones inconsistentes
• Funciones que violan la congruencia
• Funciones que cumplen con todo pero tienen nombres de una letra
• Etc.

Ejercicio 2

Se representa un diccionario con una estructura X y se quiere realizar el diseño repartiendo las tareas entre tres personas A, B y C de manera que:

• A tiene q hacer la interfaz
• B tiene que hacer algoritmo de insercion y borrado
• C tiene que hacer algoritmo de busqueda

¿Cuales son los elementos minimos que hay que darles?

• TAD Dicc
• TAD X
• Func Abs de Dicc
• Func Abs de X
• Interfaz modulo X
• Invariante de Rep Dicc
• Invariante de Rep. X
• Etc.

Ejercicio 3

Se tiene un algoritmo de sorting que realiza exactamente: $n*(n-1)/2$ comparaciones para todo input.

a) Dar la complejidad según O, θ, y Ω.

b) ¿Conoce algun algoritmo que haga exactamente esa cantidad de pasos? ¿y alguno que cumpla con $O(n^{3})$?

c) Habia que realizar un diagrama de Venn englobando distintas complejidades como O(1), θ (1), O(n), Ω(1), etc.

Ejercicio 4

Se tiene un arbol binario y se quiere verificar si esta balanceado como un AVL. Dar un algoritmo para resolver este problema y calcular su complejidad. ¿Podria el algoritmo mejorar la eficiencia de los algoritmos de un diccionario?