- Calculus can be taught rigorously with infinitesimals, following the path traveled by its original developers, unlike the approach using limits and deltas and epsilons.
- Cuckoo hashing gives hash tables with O(1) worst-case lookups and are also space-efficient.
- Bob Jenkin's hash functions for hash tables are better than those many commonly encountered in textbooks.
- Perfect hashes give optimal performance when the keys come from a small set that can be preprocessed beforehand.
- Crit-bit trees perform similarly to hash tables but have some advantages. My favourites: good worst-case running time and lexicographical operations. Apparently they can be used to sort strings faster than quicksort or radix sort.
- AA trees remove the pain from implementing balanced binary trees.

Take a map of the USA, and consider the following problems:

- Suppose you want to visit every state capitol exactly once, traveling on highways. Which route is shortest? Which route is longest? What is the mean and standard deviation of all the routes?
- Weight the states by any means, for example, by reading their two-letter code as a number in base 36. Then find a set of states such that no two members of the set are adjacent, and the total weight is maximized.
- There are several ways to colour the map with four colours such that no two adjacent states have the same colour. How do we pick one of these colourings at random (uniformly)?

- How many ways can you tile a chessboard using 1x1, 2x1 and 3x1 rectangles? What if we also have pieces that look like 2x2 boxes with one tile missing?
- List all 5-letter words that remain words after replacing a 'b' with 'o'.

Learning about BDDs reminded me of learning about PĆ³lya theory, another simple yet powerful technique which transforms the seemingly impossible into child's play.

## 1 comment:

This is a fantastic post! I wonder what you think of Hopscotch hashing, which came out in 2008 and claims some advantages over Cuckoo hashing. Right now I'm really curious how Hopscotch performs in different contexts vs. crit-bit tries and their relatives...

Post a Comment