1. Given a sequential file that contains at most four billion 32-bit integers in random order, find a 32-bit integer that isn't in the file (and there must be at least one missing - why?). How would you solve this problem with ample quantities of main memory? How would you solve it if you could use several external "scratch" files but only a few hundred bytes of main memory?

  2. Rotate a one-dimensional vector of n elements left by i positions. For instance, with n=8 and i=3, the vector abcdefgh is rotated to defghabc. Simple code uses an n-element intermediate vector to do the job in n steps. Can you rotate the vector in time proportional to n using only a few dozen extra bytes of storage?

  3. Given a dictionary of English words, find all sets of anagrams. For instance, "pots", "stop" and "tops" are all anagrams of one another because each can be formed by permuting the letters of the others.