Final 2C/2013 (Algoritmos II)

NOTA: no es el enunciado textual, pero se acerca bastante. Tal vez en el ejercicio 2 se me hayan perdidio detalles que ayuden a resolverlo.

Final tomado en la 2da. fecha del 2C/2013.

Ejercicio 1

Definir los elementos que componen el diseño de un TAD. Justificar cómo usarías esos elementos para verificar la correctitud de una implementación respecto de su especificación.

Ejercicio 2

Tenías un array implementado sobre lista enlazada, pero se supone que podías usar la interfaz con las operaciones de arreglo, como si tuvieras un módulo vector. Te pedían que explicaras cuán aplicables son todos los métodos de sorting sobre ese arreglo, análisis de complejidad, qué cambiarías de la implementación para mejorar la complejidad.

Ejercicio 3

Explicar la técnica de divide&conquer, relación con la ecuación de recurrencia y el teorema maestro.

Ejercicio 4

Explicar detalladamente la igualdad observacional, relación con la operación dameUno de conjunto y su axiomatización. Dar axiomatizaciones alternativas de esta operación y explicar sus consecuencias y dificultades.

Ejercicio 5

a) Mostrar los contenidos de una tabla de hash de tamaño 5, con concatenación, luego de insertar las claves "D", "E", "M", "O", "C", "R", "A", "T", "I", "C", "U", "S", usando como función de hash h(k) = 11*k mod M, donde k es el valor correspondiente a la k-ésima posición de cada letra en el alfabeto (ej: para A, k=1) y M es el tamaño de la tabla (5 en este caso).

b) Hacer lo mismo usando hashing abierto y una tabla de tamaño 13.