Final 1C/2010 (Algoritmos II)

De Cuba-Wiki
Saltar a: navegación, buscar
Back.png Volver a la página de la materia

Ejercicio 1[editar]

Sea S una secuencia de n claves enteras. No hacemos ninguna hipótesis sobre el rango de valores que cubren las claves, que puede ser arbitrariamente grande. Sin embargo, sabemos que las claves pueden tomar valores distintos. Por ejemplo, para n = 8 una secuencia con esas características podría ser < 349, 12, 12, 102, 349, 12, 102, 102 >.

  • a. Desarrollar un algoritmo para ordenar S en tiempo o(n log n) (o sea ESTRICTAMENTE menor que O(n log n)), explicarlo y analizar su complejidad.
  • b. Discutir si el resultado obtenido (a) contradice la cota inferior Ω(n log n)

Ejercicio 2[editar]

Considerar el TAD diccionario al que se agrega la operación precprec(D,k), que dado un diccionario D y una clave k devuelve la clave precedente a la precedente a k en D, o un valor especial si no existe.

  • a. Discutir la complejidad de implementación de precprec(D,k) en al menos 3 implementaciones eficientes de diccionario.
  • b. Describir el algoritmo de precprec(D,k) en la implementación de diccionarios con ABBs.

Ejercicio 3[editar]

Supongamos una secuencia s = < s1, s2, ..., sn > de n enteros distintos (positivos y negativos) en orden creciente. Queremos determinar si existe una posición i tal que s[i]=i. Por ejemplo, dada la secuenca s = {-4,-1,2,4,7}, i=4 es esa posición. Se pide:

  • a. Diseñar un algoritmo Divide & Conquer eficiente que resuelva el problema
  • b. Explicar por qué el algoritmo propuesto es correcto.

Ejercicio 4[editar]

Dada la siguiente especificación de un TAD..

  • a. Explicar en palabras las características principales del tipo.
  • b. Escribir la igualdad observacional.
  • c. El tipo tal como está especificado tiene un problema (podríamos decir que está incorrectamente especificado)) Indique cuál es y proponga una solución.

Ejercicio 5[editar]

Explique cual es la utilidad de las técnicas de eliminación de la recursión ¿Cuales son las principales ventajas de un algoritmo iterativo respecto a uno recursivo? ¿Es posible que al final del proceso obtengamos un código menos eficiente que el original? Ejemplifique.