Final 2/2C/2009 (Algoritmos II) (2)
Plantilla:Back Fecha: 15/03/2010 (Los enunciados no son textuales 100%, salvo el 4 y el 5; si te acordas algun detalle que me olvide, por favor, agregalo) Para considerarse aprobado deben estar bien al menos 3 ejercicios.
Ejercicio 1
Daban una especificacion de un TAD, y debian marcarse y corregirse los errores, especificando porque eran errores.
Ejercicio 2
Dado dos array de numeros enteros A y B (pueden haber elementos repetidos), de tamaño n y m respectivamente, proponer algoritmos para calcular la interseccion de manera EFICIENTE si
- n = m
- n >> m, m es chico
- n >> m, m es grande
Ejercicio 3
Proponer una estructura de datos que permita implementar un diccionario de palabras de manera de que la busqueda de un termino especifico sea eficiente. Ademas, se debe poder buscar todas las palabras que tenga un cierto largo y un cierto prefijo en comun. Dar las complejidades de estas dos operaciones, y de la de carga del diccionario (dado un texto, cargar todas sus palabras)
Ejercicio 4
Dada la siguiente frase construida sobre el alfabeto {,N,O,S,T,R,M,L,C,Z}:
- NOSOTROS NO SOMOS COMO LOS OROZCOS
- Construir un código de Huffman para los caracteres de la frase (dar el árbol o la tabla de códigos).
- ¿Cuántos bits se ganan en la codificación de la frase con respecto a la utilización de un código de longitud fija?
- Discutir aspectos relacionados con la implementación del algoritmo de Huffman (¿qué estructuras de datos usaría para hacerlo en forma eficiente? ¿qué complejidad resultaría su algoritmo?).
Ejercicio 5
Responda justificando.
- ¿Tiene sentido programar una implementación del invariante de representación?
- ¿Y la función de abstracción?
- Dé dos ejemplos de relaciones entre invariante de representación y complejidad de los algoritmos.
