Estructuras de Datos
Calendario
Cada semana: una sesión de teoría (2 h) y un laboratorio (2 h). Los temas marcados con ✂️ pueden pasar a lectura autónoma si se pierden clases.
De C a C++ y costosSecuencias y ordenamientoDiccionariosPrioridades y grafos
- 01
De C a C++
De C a C++ y costos- Teoría
- Presentación · De C a C++: referencias, clases, std::string, std::vector y pruebas
- Laboratorio
- Portar un módulo de C a C++
- 02
Ownership y templates
De C a C++ y costos- Teoría
- Ownership y RAII · Templates · Tipo abstracto e implementación, con la pila como ejemplo
- Laboratorio
- Una pila genérica sin fugas
- 03
Análisis asintótico y medición
De C a C++ y costos- Teoría
- Análisis asintótico · Medir tiempos
- Laboratorio
- Predecir el crecimiento y medirlo
- 04
Arreglos dinámicos
Secuencias y ordenamiento- Teoría
- Arreglos dinámicos y costo amortizado · Colas sobre un buffer circular
- Laboratorio
- Un Vector propio
Práctica 1ApuntesDiapositivasCódigo - 05
Listas enlazadas y deques
Secuencias y ordenamiento- Teoría
- Listas enlazadas e iteradores · Deques
- Laboratorio
- Un deque con dos representaciones
- 06
Ordenamiento y búsqueda binaria
Secuencias y ordenamiento- Teoría
- Ordenamiento: mergesort y quicksort · Búsqueda binaria
- Laboratorio
- Autocompletado
- 07
Tablas hash
Diccionarios- Teoría
- Tablas hash: funciones hash y encadenamiento
- Laboratorio
- La tabla de variables, ahora como tabla hash
Práctica 2ApuntesDiapositivasCódigo - 08
- 09
Direccionamiento abierto
Diccionarios- Teoría
- Direccionamiento abierto: linear probing y tombstones · Swiss Tables y el dict de CPython
- Laboratorio
- Corrector ortográfico: comparar diseños
- 10
Árboles binarios de búsqueda
Diccionarios- Teoría
- Árboles binarios de búsqueda: recorridos y mapas ordenados
- Laboratorio
- Un mapa ordenado, probado contra std::map
- 11
Árboles AVL
Diccionarios- Teoría
- Árboles AVL: rotaciones y altura
- Laboratorio
- Balancear el mapa con AVL
Práctica 3ApuntesDiapositivasCódigo - 12
- Teoría
- Árboles rojinegros: de los árboles 2-3-4 a la inserción · B-trees como idea · Eliminación
- Laboratorio
- Inserción rojinegra · AVL, rojinegro y std::map, medidos
- 13
Heaps y colas de prioridad
Prioridades y grafos- Teoría
- Heaps y colas de prioridad · Heapsort
- Laboratorio
- Compresión de Huffman
- 14
Grafos y union-find
Prioridades y grafos- Teoría
- Grafos: representación, BFS y DFS · Union-find
- Laboratorio
- Generar y resolver laberintos
Práctica 4ApuntesDiapositivasCódigo - 15
- Teoría
- Dijkstra con un heap · Tries · Filtros de Bloom · Repaso
- Laboratorio
- Rutas sobre un mapa real
- 16