Bentley’s book “Programming Pearls” consists of a bunch of columns that present elegant solutions to random programming problems. At the end of each column is a handful of exercises.
It is my goal to write my own solutions to all of these exercises. There are some folks kicking around the lab that I can discuss problems with, which is cool, but I’d like to have implementations for all of them as well. I’ll be posting those here.
You may wonder where I’m finding the time to do this. I find that when I get to work, my brain is a bit fuzzy (where the degree of fuzziness is heavily dependent on what sort of diet I’m on at the time in question). I have thus proposed to attempt these exercises for the first 30-45 minutes of my work day to get my brain warmed up. This is so that any stupid clumsy mistakes I make will be in exercises that I’m doing for fun, instead of work that I’m actually doing for a living 
Also, it’ll give me a chance to muck around in all the various languages that I like to hack in, which is fun.
Comments are always appreciated! Ideally I’ll get continuous feedback on these so that I can iteratively improve them.
Column 1: Sorting a disk file of 10 million 7-digit integers in roughly 1 megabyte of space.
- Exercise 1: Implementing generic sort using sorted sets
- Exercise 2: Implementing a bit vector
- Exercise 3: Comparing standard library sort to bit-vector sort.
- Exercise 4: Generating k integers less than n without duplicates.
- Exercise 5: Sorting 10 000 000 unique integers in strictly less than 1 megabyte of space.
- Exercise 6: Sorting lists of integers that have at most 10 duplicates of each number using little space.
- Exercise 7: Trying to break the sorting program.
- Exercise 8: Adding more toll codes.
- Exercise 9: Lazy initialization of sparse arrays.
- Exercise 10: Indexing an orders database by phone number.
- Exercise 11: Moving paper documents over 25 miles of busy California terrain.
- Exercise 12: Writing in outer space.
Column 2: Aha! Algorithms.
- Exercises A-C: Finding missing integers, rotating arrays, and grouping anagrams.
- Exercise 1: Finding all anagrams of a given word in two different circumstances.
- Exercise 2: Finding a duplicate integer in an overstuffed file.
Comments (0)