Códigos de los algoritmos de la asignatura EDA, organizados por carpetas, con una explicación propia de cada uno: en qué consiste, cuál es su coste, cuándo usarlo y qué errores tiene la versión del PDF.
Hay dos fuentes:
eda-codis.pdf— Data Structures and Algorithms / Algorithms in C++, de Jordi Petit, Salvador Roura y Albert Atserias (Departament de Llenguatges i Sistemes Informàtics, UPC, 15 de febrer de 2017).Teoria/— las transparencias de teoría de la asignatura (Antoni Lozano, Q1 2026–27), que tienen códigos y ejemplos que no están en el PDF.
Los códigos de las dos fuentes se han transcrito fielmente. Lo que viene de
las transparencias va marcado como TEORIA, y lo que se ha añadido como
EXTRA.
| Carpeta | Contenido | Origen |
|---|---|---|
00-Comun/ |
eda.hh, graph.hh — macros y tipos que usan los demás |
Apéndice A.1 y sección 5.1 |
01-STL/ |
Ejemplos de uso de la STL (11 programas) | Capítulo 1 |
02-Ordenacion/ |
Selection, insertion, bubble, merge, quick, heap + counting, radix, quickselect | Capítulo 2 + Temas 1-2 + extras |
03-Busqueda/ |
Búsqueda lineal (+ recursiva), binaria (5 variantes), ternaria | Extra + Temas 1-2 |
04-Diccionarios/ |
Tabla, lista, hash, ABB, AVL + recorridos de árbol | Capítulo 3 + extra |
05-ColasPrioridad/ |
Heap recursivo e iterativo | Capítulo 4 |
06-Grafos/ |
DFS, BFS, topológico, Dijkstra, Prim (+ versión de teoría) + Union-Find, Kruskal, Bellman-Ford, Floyd-Warshall | Capítulo 5 + Tema 5 + extras |
07-Backtracking/ |
Fuerza bruta, cadenas con k unos, permutaciones, n reinas, cuadrados latinos, saltos de caballo, asignación, hamiltoniano, TSP, mochila, 3-coloración | Capítulo 6 + Tema 6 + extra |
08-ProgramacionDinamica/ |
Fibonacci, mochila DP, LCS | Extra + Tema 1 |
09-DivideYVenceras/ |
Exponenciación rápida, Torres de Hanoi, Karatsuba, Strassen, mediana de medianas | Tema 2 + extras |
Teoria/ |
Transparencias de teoría, Temas 1 a 7 (PDF) | — |
87 programas, cada uno con su main y compilable por separado.
PDF en Teoria/ |
Carpetas |
|---|---|
Tema1-AnalisisAlgoritmos.pdf |
costes de todo el repo; ejemplos en 02, 03 y 08 |
Tema2-DivideYVenceras.pdf |
09, y mergesort/quicksort en 02 |
Tema3-Diccionarios.pdf |
04 |
Tema4-ColasPrioridad.pdf |
05, y heapsort en 02 |
Tema5-Grafos.pdf |
06 |
Tema6-BusquedaExhaustiva.pdf |
07 |
Tema7-Complejidad.pdf |
sin código (P, NP, reducciones) |
Para encontrar rápido lo que se busca más a menudo:
| Busco… | Está en |
|---|---|
| Exponenciación rápida (xⁿ, xⁿ mod m) | 09-DivideYVenceras/ExponenciacionRapida/ |
| Mediana / k-ésimo elemento | 02-Ordenacion/QuickSelect/, 09-DivideYVenceras/MedianaDeMedianas/ |
| Generar todas las combinaciones / permutaciones | 07-Backtracking/CadenasConUnos/, 07-Backtracking/Permutaciones/ |
| Caminos mínimos | 06-Grafos/ (BFS, Dijkstra, Bellman-Ford, Floyd-Warshall) |
| Árbol de expansión mínimo | 06-Grafos/Prim/, 06-Grafos/Kruskal/ |
| Fibonacci (y por qué el recursivo es lento) | 08-ProgramacionDinamica/Fibonacci/ |
Cada algoritmo tiene su propia carpeta con:
- Los ficheros de código — uno por variante. Por ejemplo,
02-Ordenacion/Mergesort/contienemerge_sort_1.cc,merge_sort_2.ccymerge_sort_3_bottom_up.cc. - Un
README.mdcon la explicación: la idea, un diagrama, el análisis de coste, cuándo usarlo y los detalles de implementación.
Cada carpeta de capítulo tiene además un README.md con una tabla comparativa
de todos los algoritmos que contiene.
Todos los ficheros son programas completos e independientes, con un main de
demostración que lee de la entrada estándar.
g++ -std=c++17 02-Ordenacion/Mergesort/merge_sort_1.cc -o ms
echo "5 3 9 1 7 7 2 8 0 4" | ./ms
# 0 1 2 3 4 5 7 7 8 9make # compila los 87 programas en bin/
make list # lista los ejecutables
make clean # borra bin/Los ejecutables se llaman bin/<Carpeta>-<fichero>, por ejemplo
bin/Mergesort-merge_sort_1.
g++ con soporte de C++17 (vale cualquier versión moderna; con -std=c++11
también compila casi todo). Los capítulos 06 y 07 (y producto_matrices.cc de 09) usan 00-Comun/eda.hh, que
incluye <sys/resource.h> — es decir, funcionan en Linux/WSL y macOS, no en
Windows nativo.
| Algoritmo | Medio | Peor | Memoria | Estable |
|---|---|---|---|---|
| Selection | Θ(n²) | Θ(n²) | Θ(1) | No |
| Insertion | Θ(n²) | Θ(n²) | Θ(1) | Sí |
| Bubble | Θ(n²) | Θ(n²) | Θ(1) | Sí |
| Merge | Θ(n log n) | Θ(n log n) | Θ(n) | Sí |
| Quick | Θ(n log n) | Θ(n²) | Θ(log n) | No |
| Heap | Θ(n log n) | Θ(n log n) | Θ(1) | No |
| Counting | Θ(n+k) | Θ(n+k) | Θ(n+k) | Sí |
| Radix | Θ(d(n+b)) | Θ(d(n+b)) | Θ(n+b) | Sí |
| Estructura | Búsqueda | Inserción | Borrado | ¿Ordenado? |
|---|---|---|---|---|
| Tabla / lista desordenada | Θ(n) | Θ(n) | Θ(n) | No |
| Tabla de hash | Θ(1) medio | Θ(1) medio | Θ(1) medio | No |
| ABB | Θ(h) | Θ(h) | Θ(h) | Sí |
| AVL | Θ(log n) | Θ(log n) | Θ(log n) | Sí |
| Algoritmo | Recurrencia | Coste |
|---|---|---|
| Búsqueda binaria | T(n) = T(n/2) + Θ(1) | Θ(log n) |
| Exponenciación rápida | T(n) = T(n/2) + Θ(1) | Θ(log n) |
| Mergesort | T(n) = 2T(n/2) + Θ(n) | Θ(n log n) |
| Karatsuba | T(n) = 3T(n/2) + Θ(n) | Θ(n^1.585) |
| Strassen | T(n) = 7T(n/2) + Θ(n²) | Θ(n^2.81) |
| Mediana de medianas | C(n) = C(n/5) + C(3n/4) + Θ(n) | Θ(n) caso peor |
| Torres de Hanoi | T(n) = 2T(n−1) + 1 | Θ(2ⁿ) |
| Algoritmo | Coste | Para qué |
|---|---|---|
| DFS / BFS | Θ(|V|+|E|) | recorrido; BFS da caminos mínimos sin pesos |
| Ordenación topológica | Θ(|V|+|E|) | ordenar un DAG por dependencias |
| Dijkstra | Θ((|V|+|E|)·log|V|) | caminos mínimos, pesos ≥ 0 |
| Bellman-Ford | Θ(|V|·|E|) | caminos mínimos con pesos negativos |
| Floyd-Warshall | Θ(|V|³) | caminos mínimos entre todos los pares |
| Prim / Kruskal | Θ((|V|+|E|)·log|V|) / Θ(|E|·log|E|) | árbol de expansión mínimo |
| Union-Find | Θ(α(n)) ≈ Θ(1) | conjuntos disjuntos |
Cada fichero dice en su primera línea de dónde sale:
| Cabecera del fichero | Título del README | Origen |
|---|---|---|
// 2.9 --- … (número de sección) |
**PDF:** sección 2.9 |
eda-codis.pdf |
// TEORIA (Tema 2, transparencias) --- … |
· TEORIA |
transparencias de Teoria/ |
// EXTRA (no esta en el PDF) --- … |
· EXTRA |
añadido |
Los códigos del PDF y de las transparencias están transcritos tal cual (mismo
estilo, mismos nombres, incluso los nombres en catalán de las transparencias:
potencia, cerca_binaria, cadenes…), con los comentarios traducidos y
ampliados.
Códigos que están en las transparencias pero no en el PDF:
| Tema | Códigos | Dónde |
|---|---|---|
| 1 | Selection sort con el máximo | 02-Ordenacion/SelectionSort/ |
| 1 | Búsqueda lineal recursiva | 03-Busqueda/BusquedaLineal/ |
| 1, 2 | cerca_binaria recursiva |
03-Busqueda/BusquedaBinaria/ |
| 1 | Fibonacci recursivo | 08-ProgramacionDinamica/Fibonacci/ |
| 2 | Exponenciación rápida, Torres de Hanoi, producto de matrices | 09-DivideYVenceras/ |
| 2 | Quicksort con mediana de tres y con inserción por trozos | 02-Ordenacion/Quicksort/ |
| 5 | Prim que devuelve el coste (mst) |
06-Grafos/Prim/ |
| 6 | Cadenas binarias, primalidad por fuerza bruta, cadenas con k unos (3 versiones), permutaciones (2 versiones) | 07-Backtracking/ |
Los Temas 3 (diccionarios) y 4 (colas de prioridad) usan los mismos códigos que el PDF, y el Tema 7 (complejidad) no tiene código.
Algunos algoritmos de las transparencias aparecen solo como idea, sin
código. Esos se han implementado y van marcados como EXTRA, con un
apartado de Dato curioso en su README: Karatsuba, Strassen, mediana de
medianas, mergesort con cola y 3-coloración.
Todo lo añadido lleva la marca EXTRA (no esta en el PDF) en la cabecera del
fichero y · EXTRA en el título de su README:
- Capítulo 03 (salvo lo de teoría): búsqueda lineal, binaria (iterativa,
recursiva,
lower/upper_bound, sobre la respuesta) y ternaria. - Capítulo 08 (salvo lo de teoría): Fibonacci con programación dinámica, mochila por programación dinámica y LCS.
- Capítulo 09: exponenciación iterativa y modular, Karatsuba, Strassen, mediana de medianas.
- Ordenación: counting sort, radix sort, quickselect, mergesort con cola.
- Backtracking: 3-coloración.
- Diccionarios: recorridos de árbol binario.
- Grafos: Union-Find, Kruskal, Bellman-Ford, Floyd-Warshall, BFS con distancias.
| Dónde | Errata | Corrección |
|---|---|---|
| 4.1 Cola de prioridad | El constructor se llama CuaPrio() dentro de class PriorityQueue |
PriorityQueue() |
| 5.5 Dijkstra | Usa infinit (catalán) |
infinity (el nombre real en eda.hh) |
| 5.6 Prim | Q.push({0.0, {0, 0})); — paréntesis mal cerrados |
Q.push({0.0, {0, 0}}); |
| 2.1, 2.6 | Se llama a pos_min / merge antes de declararlas |
declaración previa añadida |
| 2.7, 2.11 | Usan ins_sort(v, l, r), que el PDF no lista |
implementada |
| 3.3 Tabla de hash | Usa hash(key) sin definirla |
método privado que delega en std::hash<Key> |
| 6.5 Saltos de caballo | El main escribe has_a_solution() (un 1) |
escribe el tablero con el recorrido |
| Dónde | Errata | Corrección |
|---|---|---|
| Tema 1, selection sort | ordena_seleccio acaba en }}}, una llave de más |
quitada |
| Tema 2, producto de matrices | for (i = 0; i < n; j++): incrementa j (bucle infinito) y falta el bucle en j |
tres bucles i, j, k |
| Tema 2, producto de matrices | a.numrows() (clase de Weiss) |
a.rows() (la matrix de eda.hh) |
| Tema 5, Prim | usa n sin declararla |
int n = g.size(); |
| Tema 6, cadenas con k unos | A.size() - k es unsigned: con k > n la poda falla |
int(A.size()) - k y comprobación en el main |
| Temas 2 y 6 | usan ordena_insercio(T, e, d) y escriu(A) sin listarlas |
implementadas |
Cada corrección está anotada en el fichero correspondiente y explicada en su README.
Los algoritmos no son islas; los READMEs cruzan referencias donde toca:
- El heap del capítulo 05 es lo que hace funcionar al heapsort (02) y a Dijkstra y Prim (06).
- El Union-Find (06) es lo que hace viable a Kruskal (06).
- La mochila aparece dos veces: Θ(2ⁿ) por backtracking (07) y Θ(n·C) por programación dinámica (08).
- El backtracking (07) es un DFS (06) sobre el árbol de soluciones.
- Los capítulos 04 y 05 implementan a mano lo que hay dentro de
map,unordered_mapypriority_queue(01). - Floyd-Warshall está en Grafos (06) pero es programación dinámica pura (08).
- Divide y vencerás (09) está repartido: mergesort y quicksort están en 02, la búsqueda binaria en 03. El README de 09 tiene la tabla con todos.
- Fibonacci sale tres veces: Θ(φⁿ) recursivo (Tema 1, en 08), Θ(n) con programación dinámica (08) y Θ(log n) con exponenciación rápida de matrices (idea en 09).
- Mediana: quickselect (02) es Θ(n) en media; la mediana de medianas (09) lo garantiza en el caso peor.
- La exponenciación modular (09) es la base de los tests de primalidad rápidos, frente al de fuerza bruta de 07.
- Códigos originales: Jordi Petit, Salvador Roura y Albert Atserias —
Data Structures and Algorithms / Algorithms in C++, Departament de
Llenguatges i Sistemes Informàtics, Universitat Politècnica de Catalunya
(15 de febrer de 2017). Fichero
eda-codis.pdf. - Transparencias de teoría (
Teoria/): Antoni Lozano, con ediciones de otros profesores — Estructures de Dades i Algorismes, FIB, Q1 2026–27. - Organización, explicaciones, correcciones y algoritmos extra: este repositorio, hecho con ayuda de Claude.
@martinmol2007