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

Segundo Semestre, Estructuras de Datos

Repositorio del curso

Estructuras de Datos, grupo 7040, semestre 2022-1.

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

Metodología de trabajo en línea

Comenzando el primer día de clases (20 de septiembre) tendremos una sesión vía videoconferencia utilizando Google Meet para abrir el curso. La invitación a la videoconferencia requiere el correo institucional de la Facultad de Ciencias (@ciencias.unam.mx); si no es la dirección de correo que tienen registrada en la Facultad, por favor envíen un correo electrónico al profesor para que se les invite a la videoconferencia. Después nos seguiremos reuniendo vía videoconferencia una hora a la semana. No es obligatorio asistir en tiempo real a las videoconferencias, y todas estarán disponibles después en YouTube para consultarlas.

Aunque sí se cubrirán los temas correspondientes del curso durante las videoconferencias, las mismas están pensadas principalmente para plantear dudas: todo el curso (excepto un par de subtemas muy específicos) está cubierto en el libro de texto, y se espera que los estudiantes avancen por sí mismos lo más posible, dada la contingencia.

Además del libro de texto, en el canal de YouTube del profesor están los videos de los temas publicados durante la pandemia. Dependiendo del número de dudas y desempeño del grupo, el profesor (y ocasionalmente los ayudantes) podrán publicar nuevos videos en YouTube con los temas que los estudiantes consideren necesitan más desarrollo.

Durante el horario de la clase (fuera de la hora semanal de videoconferencia), ayudantía y laboratorio se tendrán sesiones de chat síncronas, donde podrán hacer preguntas en tiempo real. Durante todo el semestre estarán disponibles el profesor y los ayudantes vía correo electrónico, pero a veces tardarán en responder unas horas (o días, si preguntan algo el viernes a las ocho de la noche).

Exceptuando los videos, nada del curso necesitará que tengan una buena conexión a internet o mucho ancho de banda, aunque todo será más fácil si sí lo tienen. Para los videos, si lo necesitan les recomendamos que utilicen una herramienta como youtube-dl para bajar los videos en los horarios que les convenga, y si así lo consideran necesario, en una resolución media o baja.

Por motivos de la contingencia, será necesario que traten de avanzar lo más posible por ustedes mismos durante el semestre, utilizando el material que se pondrá a su disposición. Además de los videos, está el libro de texto digital, repositorios de código y otros recursos en línea; y también estarán disponibles todo el semestre el profesor y los ayudantes a través de correo electrónico. Pero lo más importante será el esfuerzo que ustedes puedan dar durante esta modalidad de trabajo en línea.

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 se les solicitará escribir código, pero recuerden que los exámenes serán en línea, por lo que podrán usar un editor de texto y el compilador de Java para verificar que sus respuestas sean correctas.

Los exámenes semanales son exámenes cortos (diez minutos) que se llevarán a cabo los viernes, y donde se harán preguntas referentes a los conceptos vistos durante la semana. Después del viernes, el examen será resuelto por el profesor. La calificación más baja de todos los exámenes semanales no será contabilizada en el promedio de los mismos.

Los exámenes semanales y parciales se realizarán a través de TCExam); las credenciales para ingresar al mismo se les proporcionarán más adelante.

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 (excepto excepciones y enumeraciones), ni agregar variables de clase (ni públicas ni privadas), 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.