If there is one thing I do a lot, it’s reading. We Chinese have a saying, “读万卷书不如行万里路”。 The literal translation being, “It is better to have travelled ten thousand miles than have read ten thousand scrolls. (It’s actually not ten thousand miles but ten thousand 里, ‘miles’ just sounds better) In short, it means that practical experience is more important than theoretical knowledge.

Not that I disagree with that, but one can still learn a lot from reading. To quote Isaac Newton,

“If I have seen further it is by standing on the shoulders of giants.”

There are a lot of giants we can learn from, along with wisdom from others’ life experience:

Competitive Programming 2

Authors: Steven Halim, Felix Halim

Website: https://sites.google.com/site/stevenhalim/

Genre: Algorithms, Competitive Programming

NOTE: There is a 3rd edition of the book available. I strongly recommend you to purchase the 3rd edition instead of the 2nd edition, as it contains more content than the 2nd edition, along with updates from the feedback of several batches of students in the CS3233 module at NUS.

This is one of the few technical books that I have read cover to cover, and certainly one of the most valuable books I own. It contains working C++ code of many computer algorithms commonly seen in programming contest problems, and covers some rather unconventional algorithms, data structures and problem solving methods that you probably will not encounter unless you have dabbled in competitive programming. And you must dabble quite seriously in it to attain the knowledge contained in this book, as both of the authors did.

This book is a very solid introduction to competitive programming, and will really stretch your mind especially if your daily programming work is not too algorithmic. To give a rough idea of what I mean by stretching your mind, here is a list of 10 of the algorithms / data structures covered, among the many:

  • Binary Indexed Tree
  • Convex Hull
  • Disjoint Set data structure
  • Dynamic Programming - various techniques
  • Fast Matrix Exponentiation
  • Maximum Flow
  • Minimum Spanning Tree
  • Sieve of Eratosthenes
  • Suffix Array
  • Tarjan’s Strongly Connected Components Algorithm

The above is just a short list of what you will be learning. Of course, you will have to do some of the recommended UVa Online Judge problems to get the most out of this book. Felix Halim, one of the authors of this book, has a site here (http://uhunt.felix-halim.net/) which will help you greatly should you choose to take up this quest.

Oh, and did I mention, I got this book for 20SGD (20 Singapore Dollars). Knowing how good it is, I will gladly purchase it even if it costs 70USD, which is the standard price of a Computer Science book.

As an update, the authors have kindly made the first edition of the book freely available. Go to the book site, and find the link under the “Selling Price (eBook)” row for the first edition, or click here to download it. If you like it, go purchase the 3rd edition and support the authors’ work!!!