Final 11/08/21 (Algoritmos II)

    Se aprueba con 3 ejercicios bien 

Ejercicio 1

Escribir la especificación de un TAD que modele una catapulta medieval. En ella se carga de a una piedra por vez, se enrosca una soga para generar tensión en el mástil y al soltarse la soga la piedra sale disparada.

Ejercicio 2

En el contexto de un diseño/implementación de un tipo abstracto, ¿en qué razonamientos/justificaciones podría ser necesario recurrir al invariante de representación?

Ejercicio 3

Indique y justifique si son verdaderas o falsas las siguientes afirmaciones:

• a) El análisis “del potencial” y el “del banquero” son técnicas para demostrar la *complejidad promedio de una operación de una estructura de datos
• b) La complejidad del caso promedio de una operación es siempre es menor o igual a la complejidad del peor caso
• c) Las Skip lists son estructuras de datos que tienen un peor caso de inserción y búsqueda igual a los AVLs
• d) La operación de inserción en el métodos de acceso secuencial indexado tiene un peor caso O(log n)

Ejercicio 4

Supongamos que necesitamos implementar un “conector” que toma un “stream” de datos (secuencia que se lee de a un elemento por vez y que no tiene necesariamente fin) y genera un stream de salida, escribiendo de un dato por vez. El objetivo de este conector es que el stream de salida esté formado por los datos del stream de entrada pero que esté más ordenado que el de entrada (substrings ordenado más largos, en promedio). La memoria del conector es acotada y queremos tener una buena performance en términos de la esperanza del tamaño de los substrings ordenados en el stream de salida. ¿Qué estructura y algoritmos vistos en clase usaría? Justifique. Reflexione sobre cómo medir su complejidad.

Ejercicio 5

Se requiere un diccionario cuyas claves son enteros y sus significados, reales. A las operaciones habituales del TAD se agrega una que, dado un entero c y la indicación posicional n (también entero) sume todos los reales asociados a claves en el diccionario que estén en el rango $[c10^{n},c10^{n}+10^{n}-1]$. Por ejemplo, Sumar(D,23,2) suma los valores asociados a todas las claves c en el diccionario D tales que $2300\leq c\leq 2399$. Queremos que esta operación tenga un costo en el peor caso que dependa exclusivamente de la cantidad de enteros en el rango que están efectivamente en el diccionario y del tamaño de los enteros de interés. ¿Qué estructura de datos elegiría para implementar el diccionario? Justifique