12 febrero 2009

The Algorithm Design Manual

Estoy leyendo estos días el libro The Algorithm Design Manual, 2nd Edition de Steven Skiena
(Web del libro). Es la edición del 2008 y la verdad es que me está gustando bastante. Requiere algo de conocimiento de las estructuras de datos básicas aunque aquí se hace un resumen.

El libro consta de dos partes, la primera tiene explicaciones sobre temas básicos de algorítmica y estructuras: grafos, árboles, ordenación, programación dinámica, heurísticas, etc.

La segunda parte es un compendio de tipos de problemas y es la parte más interesante. Están los problemas organizados por tipos: ordenación, geometría, numéricos, grafos, etc. Dentro de cada sección están los problemas más conocidos como la mochila o la envoltura convexa de puntos y cómo resolverlos. Se supone que prácticamente cualquier problema de programación que te encuentres en la vida real es una variante de alguno de estos problemas por lo que el libro es una buena guía.

Este compendio debería estar en el Programming Challenges de Skiena y Revilla. Después de leer la mitad de The Algorithm Design Manual ya no me parece tan útil el Programming Challenges. El PC tiene un montón de problemas pero te tienes que apañar tú para resolverlos, casino dan ni pistas sobre la solución.

Lo ideal sería tener los 2 pero el TADM es mucho más caro (y gordo) que el PC. Ahora mismo para alguien que quiera participar en competiciones de programación le recomendaría el TADM antes que el PC, aunque supongo que lo ideal será leer los dos.

Como fallo del TADM diría que en la primera parte no tiene capítulo específico de geometría pero luego en el compendio el capítulo de geometría es el que más problemas tiene.