Data Structure Practice for Collegiate Programming Contests and Education

Manual de entrenamiento práctico publicado por CRC Press en 2016, escrito por Yonghui Wu (entrenador de equipos finalistas mundiales de ICPC en la Universidad de Fudan) y Jiande Wang (entrenador de la Olimpiada de Informática en China). La obra está orientada a la preparación intensiva de estudiantes universitarios, competidores de programación competitiva (ICPC, IOI, Codeforces) y docentes que buscan afianzar las estructuras de datos clásicas mediante la resolución sistemática de problemas de certámenes reales. Requiere un nivel intermedio de programación en C++, soltura con la recursión y comprensión elemental de la complejidad temporal y espacial en notación asintótica.

El libro utiliza el lenguaje C++ y componentes clave de la biblioteca estándar (STL: vector, queue, stack, priority_queue, set, map, list) a lo largo de 14 capítulos divididos en 4 secciones experimentales: destrezas básicas de programación (cálculo directo, simulación y recursión simple); listas lineales (vectores, listas enlazadas secuenciales, pilas, colas, listas indexadas generalizadas y ordenamiento); estructuras de árbol (árboles binarios, árboles de búsqueda, montículos binarios, árboles de Huffman y árboles de segmentos); y estructuras de grafos (matrices y listas de adyacencia, recorridos en anchura BFS y profundidad DFS, árboles de recubrimiento mínimo mediante Prim y Kruskal, caminos más cortos con Dijkstra, Bellman-Ford y Floyd-Warshall, y grafos bipartitos con flujo en redes y algoritmos de emparejamiento). En conjunto, desglosa más de 200 problemas extraídos de eliminatorias y finales de ACM-ICPC desde 1990.

Su enfoque está volcado por completo a la práctica de ejercicios de concurso: no construye proyectos de software de gran escala, sino que para cada problema presenta el enunciado del reto, analiza el modelo subyacente, aporta pistas de diseño y ofrece la solución completa en C++, enlazando los identificadores de problemas en jueces en línea como POJ, UVa y ZOJ para su comprobación. Su mayor fortaleza reside en enseñar a elegir la estructura de datos precisa para evitar errores de límite de tiempo o memoria bajo restricciones estrictas de concurso. Deja de lado patrones de diseño de software empresarial, desarrollo guiado por pruebas (TDD) y bases de datos. Es un texto sumamente útil para quienes se preparan para torneos competitivos o entrevistas técnicas de empresas tecnológicas de primer nivel.