This book is about this solid beautiful, and pervasive foundation of computer science. It introduces the fundamental notions, models, techniques, and results that form the basic paradigms of computing. It gives an introduction to the concepts and mathematics that computer scientists of our day use to model, to argue about, and to predict the behavior of algorithms and computation. The topics chosen here have shown remarkable persistence over the years and are very much in current use. The book realizes the following goals:
•To introduce to the students of computer science and mathematics the elegant and useful models and abstractions that have been created over the years for solving foundational problems about computation
•To help the students develop the ability to form abstract models of their own and to reason about them
•To strengthen the students' capability for carrying out formal and rigorous arguments about algorithms
•To equip the students with the knowledge of the computational procedures that have hunted our predecessors, so that they can identify similar problems and structures whenever they encounter one
•To make the essential elements of the theory of computation accessible to not-so-matured students having not much mathematical background in a way that is mathematically uncompromising
•To make the students realize that mathematical rigour in arguing about algorithms can be very attractive
•To keep in touch with the foundations as computer science has become a much more matured and established discipline