final algo2

alguien rindió el final de algo2 ayer? que tomaron? como les fue? saben si se puede conseguir el final que tomaron ayer?

Yo lo rendí, como gil me olvidé de pedir el examen. Igual me acuerdo los problemas.

El primero te decía que tenés un arreglo S de \(n\) números enteros, del \(0\) al \(m-1\) todos. Te dan un arreglo \(B\) de \(m\) elementos que en su \(i\)-ésima posición, tiene #\(\{x \in S \mid x \le i\}\). Te pedían encontrar un algoritmo que, usando \(B\), ordene \(S\) en \(O(n)\).
La respuesta para esto es pensar en counting sort. El algoritmo sería algo así como...

int i;
int res[n];
for(i = 0; i < n; i++) {
    res[--B[S[i]]] = S[i];
}

Luego te hacía la obvia pregunta de si esto contradice la cota inferior de \(\Omega(n log n)\), y la respuesta es no, porque counting sort no es un algoritmo de comparación, y requiere hipótesis adicionales acerca de la entrada (que está acotada).
Luego te preguntaba si este algoritmo era estable, y en caso de no serlo, como lo modificarías para que lo sea. Esta implementación no lo es - es exactamente anti-estable, entonces podés invertir cada bloque de elementos iguales para que sea estable. Otra forma sería creando B para que la desigualdad fuera estricta, y llenándolo de atrás para adelante.

El segundo problema te pedía que hables de precprec, la misma función que había en parciales anteriores. Discutí como harías para implementar la operación \(precprec(D, k)\) que, dado un diccionario \(D\) y una clave \(k\) (cuyo tipo de datos tiene definido \(<_\alpha\)) darme el predecesor del predecesor de \(k\) en \(D\). Esto lo tenías que discutir en 3 implementaciones eficientes de un diccionario (yo elegí Skip List, AVL, y Splay Trees), e implementar en un ABB. Implementar en un ABB no es tan trivial, si el nodo no tiene hijo izquierdo.

El tercero era el clásico de que tenés una secuencia \(S\) (con acceso random en \(O(1)\)) de enteros, positivos y negativos, todos distintos, en orden creciente. Vos querés saber si existe un \(i\) tal que \(S[i] = i\). Clásica búsqueda binaria, corre en \(O(log n)\) tiempo, pues sabés que si \(S[j] > j\), entonces \(\forall\ k > j, S[k] > k\).

El cuarto era "por qué está bueno eliminar la recursión? Puede terminar mas lento el programa final?"

El quinto era un TAD con varios errores (rompía congruencia de la ig. obs., una o.o. estaba mal axiomatizada, cosas así). Tenías que decir qué errores eran, y como harías para solucionarlos.

al parecer no era el peoooooor final del mundo.
gracias

Sorprende como ha bajado el nivel de exigencia en los finales de esta materia...

A mi me la re pusieron (5) 😄 ,igual era más que nada porque el enunciado estaba redactado como el upite y no entendí (creo que varia gente tmp) lo que realmente pedían.
Igual era ARMAR un TAD, no corregirlo y lo que tenías que cumplir para armarlo era un quilombo padre, entre otras cosas.

En fin...Mejor para las futuras generaciones,éxitos!

Curiosidad: Me enteré que hay un apunte que hice yo para este final que anda dando vueltas por exactas,ya ni me acuerdo cuando ni como lo hice xD