Ciencias de la Computación (plan 2013) 2017-1

Segundo Semestre, Estructuras de Datos

NO SE ACEPTARÁN ALUMNOS INSCRITOS EN EXTRAORDINARIO LARGO

Temario

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

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á tres 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 en su mayoría 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 será, en principio, 10. Si un estudiante consigue escribir código erróneo que pase todas las pruebas unitarias de una práctica, y le avisa al profesor antes de la fecha de entrega, el estudiante obtendrá un punto extra en esa práctica. Además de pasar las pruebas unitarias, los algoritmos implementados deben satisfacer las complejidades en tiempo y en espacio vistos en clase.

Para alcanzar al menos el 5 de calificación, la práctica debe compilar correctamente y sin advertencias. No está permitido bajo ninguna circunstancia utilizar clases del paquete java.util, ni agregar variables de clase (ni públicas ni privadas) a ninguna clase vista durante el curso. Tampoco está permitido agregar métodos públicos; pero métodos privados están permitidos, y de hecho se les sugiere que los utilicen.

Si el ayudante o profesor detectan que han copiado en alguna práctica, la calificación de la misma se dividirá entre el número de estudiantes que hayan copiado.

La fecha límite de entrega de prácticas y proyectos es inamovible.

Renuncias y NPs

Para alumnos inscritos, la única forma en que se les pondrá NP en actas es si solicitan renunciar al curso mediante un correo electrónico dirigido al profesor, a más tardar en la octava semana de clases. Si no mandan un correo electrónico a más tardar en la octava semana, un alumno inscrito tendrá en actas la calificación que obtenga en el curso, no importa cuál sea ésta, y no importa si deja o no de asistir a clases, entregar prácticas y proyectos, y/o realizar exámenes.

No se guardan calificaciones para próximos semestres ni para exámenes extraordinarios. Mucho menos se “pasan” o “reciben” calificaciones a o de otros profesores.

NO SE ACEPTARÁN ALUMNOS INSCRITOS EN EXTRAORDINARIO LARGO