Final 1C/2006 (Algoritmos II)

Esteban Feuerstein y Ricardo Rodríguez

Forex useful info about <a href="http://www.bs-nes.gracom.de/user/view.php?id=1410&course=1">Euro dollar exchange rate</a> http://www.bs-nes.gracom.de/user/view.php?id=1410&course=1 [URL=http://www.bs-nes.gracom.de/user/view.php?id=1410&course=1]Euro dollar exchange rate[/URL]

Ejercicio 2

Sea la siguiente función de Quatrinacci:

f(1) = 1
f(2) = 3
f(3) = 5
f(n) = 3 f(n-1) + 2 f(n-2) - f(n-3)

a) Escribir la función recursiva.

b) Encuentre usando técnicas de generalización una función recursiva equivalente que sea lineal a la cola. Pruebe que son equivalentes.

c) Obtener el iterativo.

Ejercicio 3

Dado un conjunto de puntos de 1 recta ${x_{0},...,x_{n}}$ dar un algoritmo para determinar los 2 puntos mas cercanos que tenga complejidad $O(n^{2})$. Proponer un algoritmo D&C y estimar su complejidad. El algoritmo dado no puede ordenar el input y luego recorrer buscando la mínima distancia entre adyacentes. Hint: asumir dada una rutina que en tiempo lineal encuentra el elemento mediano de un conjunto. Si los puntos fueran en el plano y la distancia fuera la euclídea, cómo extendería el resultado anterior?

Ejercicio 4

Discutir la posibilidad de implementar cola de prioridades con arrays, ABBs, AVLs y Árboles B.