Diferencia entre revisiones de «Final 01/03/18 (Algoritmos II)»
(Página creada con «== Ejercicio 1 == a)Explicar (en castellano) como seria la interfaz del diseño de un modulo de secuencia sobre lista enlazada que permita hacer quicksort de manera eficien...») |
Sin resumen de edición |
||
| Línea 1: | Línea 1: | ||
Final tomado por Soulignac | |||
== Ejercicio 1 == | == Ejercicio 1 == | ||
a)Explicar (en castellano) como seria la interfaz del diseño de un modulo de secuencia sobre lista enlazada que permita hacer quicksort de manera eficiente. | a)Explicar (en castellano) como seria la interfaz del diseño de un modulo de secuencia sobre lista enlazada que permita hacer quicksort de manera eficiente. | ||
| Línea 4: | Línea 5: | ||
b)implementar el algoritmo de quicksort para la secuencia diseñada | b)implementar el algoritmo de quicksort para la secuencia diseñada | ||
c)explicar (en castellano) ccomo se implementarian las funciones usadas en el punto anterior | c)explicar (en castellano) ccomo se implementarian las funciones usadas en el punto anterior | ||
== Ejercicio 2 == | |||
a)Describir el principio de hashing uniforme en una tabla cerrada con direccionamiento abierto | |||
b) Linear probing y Hashing doble cumplen con eso? | |||
== Ejercicio 3 == | |||
Explicar la definicion de complejidad amortizada y para cada caso calcular su complejidad(independientemente de la estructura | |||
a)recorrer la estructura de principio a fin | |||
b)reccorrer la estructura desde el final hasta el principio | |||
c)avanzar y retroceder n veces (queda apuntando al mismo valor en el q estaba) | |||
Considerar un ABB balancecado(avl, rb-tree, etc) calcular la complejidad nuevamente para cada caso y analizarlo | |||
== Ejercicio 3 == | |||
Explique que estructura usaria manteniendo ordenado un conjunto de numeros y que se pueda agregar y borrar de forma eficiente para cada caso: | |||
a)Que no tenga que pasar que te quedes momentaneamente esperando al programa | |||
b)Que la estructura(no los valores) ocupen el menor espacio posible | |||
c)se tiene un sistema de noticias y se espera que la noticia mas vista sea la que menos tarde en cargar | |||
Revisión del 11:47 2 mar 2018
Final tomado por Soulignac
Ejercicio 1
a)Explicar (en castellano) como seria la interfaz del diseño de un modulo de secuencia sobre lista enlazada que permita hacer quicksort de manera eficiente. (y dejar claro lo del aliasing) b)implementar el algoritmo de quicksort para la secuencia diseñada c)explicar (en castellano) ccomo se implementarian las funciones usadas en el punto anterior
Ejercicio 2
a)Describir el principio de hashing uniforme en una tabla cerrada con direccionamiento abierto b) Linear probing y Hashing doble cumplen con eso?
Ejercicio 3
Explicar la definicion de complejidad amortizada y para cada caso calcular su complejidad(independientemente de la estructura a)recorrer la estructura de principio a fin b)reccorrer la estructura desde el final hasta el principio c)avanzar y retroceder n veces (queda apuntando al mismo valor en el q estaba)
Considerar un ABB balancecado(avl, rb-tree, etc) calcular la complejidad nuevamente para cada caso y analizarlo
Ejercicio 3
Explique que estructura usaria manteniendo ordenado un conjunto de numeros y que se pueda agregar y borrar de forma eficiente para cada caso: a)Que no tenga que pasar que te quedes momentaneamente esperando al programa b)Que la estructura(no los valores) ocupen el menor espacio posible c)se tiene un sistema de noticias y se espera que la noticia mas vista sea la que menos tarde en cargar
