Edición de «Final 10/3/2011 (Algoritmos II)»
De Cuba-Wiki
Puedes deshacer la edición. Antes de deshacer la edición, comprueba la siguiente comparación para verificar que realmente es lo que quieres hacer, y entonces publica los cambios para así efectuar la reversión.
Revisión actual | Tu texto | ||
Línea 1: | Línea 1: | ||
Si habías aprobado la parte práctica y los TPs, tenías que hacer solo los ejercicios 1 a 5. Los ejercicios 6 y 7 eran para la gente que rendía "final libre" (o sea, que habían aprobado los TPs pero desaprobado un parcial. | |||
Si habías aprobado la parte práctica y los TPs, tenías que hacer solo los ejercicios 1 a 5. Los ejercicios 6 y 7 eran para la gente que rendía "final libre" (o sea, que habían aprobado los TPs pero desaprobado un parcial | |||
=Ejercicio 1= | =Ejercicio 1= | ||
Línea 53: | Línea 51: | ||
=Ejercicio 3= | =Ejercicio 3= | ||
Suponer que tenemos un arreglo bidimensional A de m filas y n columnas. Suponemis que cada fila está ordenada en forma creciente. Describir un algoritmo que junta todos los elementos de A en un array de nm elementos en tiempo total | Suponer que tenemos un arreglo bidimensional A de m filas y n columnas. Suponemis que cada fila está ordenada en forma creciente. Describir un algoritmo que junta todos los elementos de A en un array de nm elementos en tiempo total O(nmlogm). (Sugerencia: ustilizar un heap como estructura auxiliar). | ||
=Ejercicio 4= | =Ejercicio 4= | ||
Línea 65: | Línea 63: | ||
=Ejercicio 6= | =Ejercicio 6= | ||
Demostrar las siguientes propiedades, donde f y g son funciones de N en R+. | Demostrar las siguientes propiedades, donde f y g son funciones de N en R+. | ||
* | * f pertenece O(g) sii O(f) incluido O(g) | ||
* | * f(n) = Tita(g(n)) implica g(n) = tita(f(n)) | ||
* | * max(f(n),g(n)) = tita(f(n) + g(n)) | ||
=Ejercicio 7= | =Ejercicio 7= | ||
Línea 75: | Línea 73: | ||
* AVL sobre ABB sobre AB sobre punteros, conjunto sobre AVL, diccionario sobre AVL | * AVL sobre ABB sobre AB sobre punteros, conjunto sobre AVL, diccionario sobre AVL | ||
* Conjunto sobre AVL, diccionario sobre tabla de hashing abierta con conjuntos en las celdas | * Conjunto sobre AVL, diccionario sobre tabla de hashing abierta con conjuntos en las celdas | ||