I would like to try the book question a little bit differently. My goal is to know what the community thinks are the quintessential computer science textbooks.

<beginsadstory>I lost all of my computer science and math books from college in Hurricane Katrina in 2005. I greatly miss having my familiar tomes to refer to when topics and problems come up, so I am looking to rebuild my library.<endsadstory>

What are your recommendations for the best examples of academic caliber books for the field of computer science and its associated mathematics? I am looking for books on subjects like computational theory, programming languages, compilers, operating systems, algorithms and so on. Don't limit your suggestions to your textbooks only. If there is a book you have read that covers computer science or a related math in a formal way, but is not strictly a textbook, I would be love to hear about them as well.

Finally, for the sake of creating a good reference for all of us, may I suggest posting one book per answer so they can be rated individually.