A marvelous algorithm collection!
Today I’d like to review “Programming Pearls” (2nd Edition) book. You may think it is seriously out of date, because it was published in 1999, and you will be wrong.
This book has a list of hand picked real problems solved by various developers at times when RAM was counted in kilobytes and megabytes and CPU frequency in megahertz rather than in gigahertz. These algorithms are still very important, because current computer systems are limited by memory access times rather than by CPU frequency. It means that in many cases you may gain a serious performance boost by getting these algorithms out of your grandfather’s trunk 🙂
This book can not replace any of well-known algorithm text books like “Algorithms (4th Edition)” or “Introduction to Algorithms”. It describes particular quite counter-intuitive applications of these algorithms for some problems. And the most important difference of this book from algorithm textbooks – it is easy and interesting to read, so you are unlikely to get asleep while reading this book late night 🙂
This book describes algorithms in the following areas:
- Numeric values sorting and searching, anagrams
- Data structures – right choice of a structure for a problem
- Program testing and verification
- Performance tuning principles
- Back of the envelope calculations (very useful for engineering interview – in Google, for example)
- Algorithm design techniques
- Code tuning
- Squeezing space
- Sorting
- Searching
- Heaps
- Algorithms on strings (this is just an overview, this is an in-depth book in this area: “Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology”)
Here are a few problems discussed in this book:
- How to sort up to 10 million unique non-negative integers, all of which are less than 10^{7} in 1.25M memory? What if we have only 1M (or less) memory available? What if our integers are not unique, but number of occurrences of each value is limited?
- Find all sets of anagrams in the given dictionary.
- You have a file with 4 billion 32-bit integers. Find an integer which is not in the file. How would you do it if you have an ample amount of RAM? What about case when you have only a few hundred bytes of RAM, but you are allowed to write temporary files?
- Given a vector of floating-point numbers, find a maximum sum in any contiguous subvector of the input. The author starts from a straightforward O(n^{3}) algorithm and goes down to O(n^{2}), O(n*logN) and finally O(n) algorithm.
- You have a sorted array of 1000 integers. How can you tune a binary search algorithm for this case?
- Given a very long sequence of bytes, how would you efficiently count a number of one (set) bits?
- How to compress 75,000 English words into 52K RAM in order to use them in a spellchecker program?
- How to generate the random text which looks like it was hand-written if you have several input texts to teach your program?