Computability and Complexity
Publisher: Wikibooks 2010
This book is intended as an introductory textbook in Computability Theory and Complexity Theory, with an emphasis on Formal Languages. Its target audience is Computer Science and Math students with some background in programming, data structures, and discrete math, such as a sophomore in a Computer Science program.
Home page url
Download or read it online for free here:
by Neil D. Jones - The MIT Press
The author builds a bridge between computability and complexity theory and other areas of computer science. Jones uses concepts familiar from programming languages to make computability and complexity more accessible to computer scientists.
by Oded Goldreich
Complexity theory is the study of the intrinsic complexity of computational tasks. The book is aimed at exposing the students to the basic results and research directions in the field. The focus was on concepts, complex technical proofs were avoided.
by Herbert S. Wilf - AK Peters, Ltd.
An introductory textbook on the design and analysis of algorithms. Recursive algorithms are illustrated by Quicksort, FFT, and fast matrix multiplications. Algorithms in number theory are discussed with some applications to public key encryption.
by Allen Downey - Green Tea Press
This book is about data structures and algorithms, intermediate programming in Python, complexity science and the philosophy of science. The book covers Graphs, Analysis of algorithms, Scale-free networks, Cellular Automata, Agent-based models, etc.