Book of Programming Challenges

My suggestion for a book of programming challenges is "Programming Challenges: The Programming Contest Training Manual" by Steven S Skiena and Miguel A. Revilla.

Book of Programming Challenges

Title: Programming Challenges: The Programming Contest Training Manual, 2003rd Edition

Authors: Steven S Skiena, Miguel A. Revilla

Series: Texts in Computer Science

Publisher: Springer

Pages: 748

This book is part of the Springer's series "Texts in Computer Science".

The series includes a total of 83 titles of high-quality books intended for all students in the sphere of computer science. Because the series is targeted at students, the books are very well structured just like a good textbook. They offer a stable foundation with theory and include examples and exercises to demonstrate and apply the knowledge presented inside.

The book of Programming Challenges is no exception. Although originally it is meant to prepare you for a programming competition - it is not just a compilation of challenges.

Non-competitors can benefit greatly because studying the problems will make you better in your algorithmic thinking and coding skills. The techniques will prepare you for many of those tricky problems from the job interviews.

The material is organized in 14 chapters. Each chapter teaches the theory necessary to solve the problems. They cover:

  1. Getting Started - 8 "basic" problems
  2. Data structures (stack, queue, dictionary, priority queue, set)
  3. Strings (representation, patterns, string manipulations)
  4. Sorting
  5. Arithmetic and Algebra (high-precision integers, real numbers, manipulating polynomials, logarithms)
  6. Combinatorics (counting techniques, recurrence relations, binomial coefficients, recursion and induction)
  7. Number Theory (Prime numbers, divisibility, Modular arithmetic, Congruences)
  8. Backtracking (constructing subsets and permutations, pruning search)
  9. Graph Traversal (graphs, breadth-first, depth-first, topological sorting)
  10. Graph Algorithms (graph theory, shortest paths, network flows etc.)
  11. Dynamic Programming
  12. Grids (Rectilinear, triangular and hexagonal grids)
  13. Geometry (lines, circles, triangles and trigonometry)
  14. Computational Geometry (Line segments and intersection, polygons, angle computations, triangulation)

In these 14 chapters, you will face more than a 100 challenges that have already been used in international programming contests.

Note that the book of programming challenges does not give you the the solutions. To check your solutions, you can use the "robot judge" - an online tool, that supports C, C++, Pascal, Java. It will actually give you grades, so you know if your solution can be improved (of course it can be better :-)).

The book is also not meant to teach you a programming language. Still it will give you some directions for some of the standard libraries in C++ and Java.

Other books from the same author (Steven S Skiena) in the same series are: