Ciencias de la Computación (plan 2013) 2015-2

Segundo Semestre, Estructuras de Datos

Evaluación

El curso se evaluará de la siguiente manera:

Evaluación teórica

Habrá tres exámenes parciales, cada uno de los cuales cubrirá aproximadamente la tercera parte del material visto en clase. En ningún examen parcial se les solicitará escribir código (a menos que se ofrezca como punto extra del examen), pero sí que lean y analicen código.

Los exámenes semanales son exámenes cortos (diez minutos) que se llevarán a cabo los miércoles al término de la clase, y donde se harán preguntas referentes a los conceptos vistos durante la semana. Una vez que todos los alumnos hayan entregado el examen, será resuelto ahí mismo por el profesor. La calificación más baja de todos los exámenes semanales no será contabilizada en el promedio de los mismos.

No hay exámenes de reposición ni examen final.

Evaluación práctica

Habrá dos proyectos, para realizarse de forma individual, y consistirán en implementar la solución a un problema específico, utilizando los conceptos y herramientas vistos durante el curso.

Las prácticas consistirán en implementar, en su totalidad o en parte, las clases y métodos correspondientes que se les dejen. Las prácticas también deberán realizarse de forma individual.

La calificación de las prácticas depende de las pruebas unitarias incluidas en cada una de ellas. Si la práctica que el alumno entregue pasa todas las pruebas unitarias, y además los algoritmos implementados cumplen los requerimientos de complejidad en tiempo y espacio, la calificación es 10.

Para alcanzar al menos el 5 de calificación, la práctica debe compilar correctamente y sin advertencias.

Temario

1. Introducción al curso
   • Introducción a estructuras de datos
   • Estructuras de datos en orientación a objetos
   • Listas y arreglos
   • Genéricos e iteradores
2. Pilas y colas
   • Pilas
   • Colas
   • Complejidades en tiempo y en espacio
3. Ordenamientos y búsquedas
   • Ordenamientos en arreglos
   • Ordenamientos en listas
   • Búsquedas en arreglos
   • Búsquedas en listas
   • Complejidades en tiempo y en espacio
4. Árboles binarios
   • Propiedades de árboles binarios
   • Árboles binarios completos
   • Recorriendo árboles binarios
   • BFS, DFS pre order, post order, e in order
   • Recorridos por niveles
   • Complejidades en tiempo y en espacio
5. Árboles binarios ordenados
   • Propiedades de árboles binarios ordenados
   • Agregar, eliminar y buscar elementos
   • Complejidad en tiempo y en espacio
   • Giros en árboles binarios ordenados
   • Complejidades en tiempo y en espacio
6. Árboles rojinegros
   • Propiedades de árboles rojinegros
   • Algoritmo de inserción
   • Algoritmo de eliminación
   • Complejidades en tiempo y en espacio
7. Árboles AVL
   • Propiedades de árboles AVL
   • Algoritmo de inserción
   • Algoritmo de eliminación
   • Complejidades en tiempo y en espacio
8. Gráficas
   • Propiedades de gráficas
   • Gráficas planas
   • Recorridos sobre gráficas
   • Complejidades en tiempo y en espacio
9. Montículos
   • Montículos mínimos
   • Creación de un montículo con n elementos
   • Minimizar un montículo
   • Reordenar un elemento
   • Complejidades en tiempo y en espacio
10. Algoritmo de Dijkstra
    • Gráficas con pesos en las aristas
    • Dijkstra
    • Complejidad en tiempo y en espacio
    • Aplicaciones
11. Diccionarios
    • Huellas digitales
    • Colisiones en huellas digitales
    • Diccionarios
    • Llaves y colisiones de llaves
    • Complejidades en tiempo y en espacio