What Books Should Everyone Read? [Timeline]



This question has the same spirit of what papers should everyone read and what videos should everybody watch. It asks for remarkable books in different areas of theoretical computer science.

The books can be math-oriented, yet you may find it great for a computer scientist.
Examples:


Probability
Inequalities
Logic
Graph Theory
Combinatorics
Design &amp; Analysis of Algorithm
Theory of Computation / Computational Complexity Theory


Please devote each answer to books of the same subject (e.g. books on combinatorics).

Note: The title might be misleading. Here's a clarification: Let X and Y be two fields in computer science. There are books that everyone 


in field X should read.
in field Y should read.
in both fields should read.


This question seeks all 3 cases. In other words, it is NOT specific to the latter case.

Edit: As suggested by Dai Le, please highlight the reason(s) you like the book as well.



Related topics:


References for TCS proof techniques
Books on automata theory for self-study
Books for probability
Favorite popular math book
Beginner's guide to derandomization
References on circuit lower bounds
Survey article on the theory of recursive functions
Books on Programming Language Semantics
What are the recent TCS books whose drafts are available online
Books on probability
Computational Complexity:

If you are looking for recent complexity textbooks. The following two are must have.


Computational Complexity: A Modern Approach by Sanjeev Arora and Boaz Barak (Textbook homepage)
Computational Complexity: A Conceptual Perspective by Oded Goldreich (Textbook homepage)


The majority of the content between these two books is comparable. However, some key differences exist: Goldreich devotes more space to exploring the conceptual and philosophical basis of complexity theory, whereas Arora/Barak covers a wider selection of topics, including concrete models of complexity, quantum computation, and circuit lower bounds that are mostly absent from the former.

Another option, an older but timeless textbook in complexity is:


Computational Complexity by Christos Papadimitriou


Papadimitriou's book is notable for chapters covering first-order logic as well as the classes SNP, MaxSNP$_0$, and APX (the theoretical foundations of hardness of approximation), which are missing from the more modern texts.

Another (comparatively) old, but quite notable classic is:


Introduction to the Theory of Computation by Michael Sipser


This is one of the few/first textbooks that explicitly includes "Proof Idea:" between "Theorem:" and "Proof:", and is one of the best-written mathematical textbooks on any topic. On the other hand, it is only an intro to complexity, devoting only one 50-page chapter to "advanced topics" (including approximation, probabilistic algorithms, IP=PSPACE, and crypto). As a first book on complexity, or as an example of truly excellent writing, this book is great.


The Nature of Computation by Cristopher Moore and Stephan Mertens


Scott Aaronson writes that this book has "the fun of a popular book with the intellectual heft of a textbook." It tells stories and gives lots of entertaining examples and references (Game of Life, and lots of other examples for Turing-complete machines).
It doesn't go too deep into complexity theory but has great breadth. Especially of note are its connections to statistical physics.