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

Segundo Semestre, Estructuras de Datos

Temario

1. Introducción
2. Genéricos
   1. Tipos genéricos
   2. Borradura de tipos
   3. Acotamiento de tipos
   4. Empacamiento y desempacamiento
   5. Los genéricos en este libro
3. Iteradores
   1. El operador for-each
4. Colecciones
5. Listas
   1. Definición de listas
   2. Algoritmos para listas
   3. Iteradores para listas
6. Complejidad computacional
   1. La notación de O grandota
   2. Complejidades en tiempo y en espacio
7. Arreglos
   1. El polinomio de redireccionamiento
   2. Arreglos y genéricos
8. Pilas y colas
   1. Algoritmos de la clase abstracta
   2. Algoritmos para pilas
   3. Algoritmos para colas
   4. Pilas y colas en el resto del libro
9. Lambdas
   1. Lambdas y funciones de primera clase
   2. Clases internas anónimas
   3. Lambdas en Java con interfaces funcionales
10. Ordenamientos
    1. Ordenamientos en arreglos
       1. Algoritmo SelectionSort
       2. Algoritmo QuickSort
       3. Manteniendo arreglos ordenados
    2. Ordenamientos en listas
       1. Algoritmo MergeSort
       2. Manteniendo listas ordenadas
    3. La razón para ordenar colecciones
11. Búsquedas
    1. Búsquedas en arreglos
    2. Búsquedas en listas
12. Árboles binarios
    1. Definición de árboles binarios
    2. Propiedades de árboles binarios
    3. Implementación en Java
    4. Algoritmos para árboles binarios
    5. Aprovechando referencias no utilizadas
13. Árboles binarios completos
    1. Definición de árboles binarios completos
    2. Recorriendo árboles por amplitud
    3. 1. Acciones para vértices de árboles binarios
    4. Algoritmos para árboles binarios completos
14. Árboles binarios ordenados
    1. Definición de árboles binarios ordenados
    2. Recorriendo árboles por profundidad
       1. DFS pre-order
       2. DFS post-order
       3. DFS in-order
    3. Algoritmos para árboles binarios ordenados
    4. Complejidades en tiempo y en espacio
15. Árboles rojinegros
    1. Definición de árboles rojinegros
    2. Algoritmos de los árboles rojinegros
    3. 1. Algoritmo para agregrar
       2. Algoritmo para eliminar
16. Árboles AVL
    1. Definición de árboles AVL
    2. Algoritmos de los árboles AVL
    3. 1. Algoritmo de rebalanceo
17. Gráficas
    1. Definición de gráficas
    2. Propiedades de gráficas
    3. Implementación en Java
    4. Recorridos en gráficas
    5. 1. BFS en gráficas
       2. DFS en gráficas
    6. Algoritmos para gráficas
    7. Implementaciones alternativas de gráficas
18. Montículos mínimos
    1. Definición de montículos mínimos
    2. Acomodando hacia arriba y hacia abajo
    3. 1. Acomodando hacia arriba
       2. Acomodando hacia abajo
    4. Implementación en Java
    5. Algoritmos para montículos mínimos
    6. Algoritmo HeapSort
    7. Montículos de arreglos
19. Algoritmo de Dijkstra
    1. Definición de trayectoria de peso mínimo
    2. Implementación en Java
    3. Algoritmos para gráficas con pesos en las aristas
    4. Algoritmo de trayectoria mínima
    5. Algoritmo de Dijkstra
    6. Reconstruyendo trayectorias
    7. Pesos con matrices de adyacencias
20. Funciones de dispersión
    1. Colisiones en funciones de dispersión
    2. Implementación en Java
       1. Cascando huevos
    3. Función de dispersión XOR
    4. Función de dispersión Bob Jenkins
    5. Función de dispersión de Daniel J. Bernstein
    6. Funciones de dispersión para diccionarios
21. Diccionarios
    1. El arreglo del diccionario
    2. Implementación en Java
    3. Algoritmos para diccionarios
    4. Complejidades en tiempo y en espacio
    5. Implementaciones alternas de diccionarios
22. Conjuntos
    1. Implementación en Java
    2. Algoritmos para conjuntos
    3. Otros usos de conjuntos
23. Mejorando gráficas
    1. Modificaciones al código
24. Conclusiones

Modo presencial

El curso será presencial, a menos que como en marzo de 2020 nos obliguen las autoridades a cambiar la modalidad del curso dadas las condiciones de la pandemia.

Que el curso sea presencial en esta nueva realidad Covid tiene múltiples consecuencias: no se aceptarán alumnos oyentes bajo ninguna circunstancia, para cumplir los límites de aforo del salón que nos toque. Los que participemos estaremos tomando un riesgo calculado de que el estarnos transportando de nuestras casas a la universidad y conviviendo con compañeros en espacio cerrados conlleva la posiblidad de contagio del virus, por más que tratemos de mantener la sana distancia y demás protocolos de seguridad. Por lo tanto, si ustedes o alguna de las personas con las que viven están en situación de alto riesgo o están inmunocomprometidos, les recomendamos fuertemente que no inscriban el curso en este grupo. Existen razones para arriesgar una vida humana; llevar un curso no es una de ellas.

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 los examenes parciales no se les solicitará escribir código, 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, y donde se harán preguntas referentes a los conceptos vistos durante la semana. Una vez que todos los alumnos hayan entregado el examen, el profesor explicará las respuestas correctas a las preguntas del mismo.

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 demostrablemente incorrecto 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 (excepto excepciones y enumeraciones), 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 o proyecto, la calificación de la misma se dividirá entre el número de estudiantes que hayan copiado. Si el profesor detecta que un proyecto fue bajado de internet, la calificación será cero.

Las prácticas y proyectos estarán disponibles en el repositorio del curso. Ahí también encontrarán las instrucciones para entregarlos.

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

Renuncias y NPs

Por motivos de la actual pandemia, nadie sacará 5 durante el curso; cualquier estudiante que obtenga una calificación reprobatoria se le pondrá NP en las actas. De todas maneras, si por cualquier motivo deciden abandonar el curso, apreciaríamos que nos avisaran por correo electrónico.

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.