There are three books that I believe that every self-taught computer scientist should read. These are books that I often recommend to smart junior developers that learned their knowledge by doing instead of schooling. These are books that will close the gap for people that fall into the category of "or equivalent experience" on a job posting.
The first book is the venerable C Programming Language book. This book was written by Brian Kernighan (an original Unix hacker) and Dennis Ritchie (the creator of C) and because of that, it is affectionately known as the K&R book.
The K&R book is invaluable for self-taught computer scientists for a number of reasons. Firstly, C is arguably the Latin of modern programming languages. C++, ObjectiveC, Java, Perl, Ruby and Python all have their roots in C.
Second, the K&R book is written by the designer of the language. I read it early in my career and found it very easy to read despite being a manual for a programming language.
This book provides a comprehensive look at all aspects of the C language; from basic statement structure to pointers and elementary data structures. The topics discussed in this book will provide you with a good foundation of programming that is often missed when you learn to program to get the job done.
Mastering Algorithms in C
Where the K&R book leaves off, the Mastering Algorithms in C book picks up. In this book you will learn the about Big-O notation, analysis of algorithm, recursion and fundamental data structures.
The beauty of this book is that it demonstrates these topics a practical way that appeals to the self-taught computer scientist. Instead of discussing these topics in only abstract terms, the author walks you through the implementation of algorithms and data structures in C.
With this book you will be introduced to five fundamental data structures in computer science and their application: Linked Lists, Sets, Hash Tables, Trees, and Graphs.
Once you have a solid grasp of these structures you will be able to model solutions in those terms without having to reinvent the wheel. Do you need to model the relationships between people? That's a graph. Do you need to model a hierarchy of sections on a website? That's a tree.
The Little Schemer
After you have a grasp of basic data structures, it is time to visit the book that had a significant impact on the way I solve harder problems. This modest, but potent book is The Little Schemer. In the world of computer books it's nearly a pamphlet at 195 pages, but just like its language of choice, Scheme, it is concise and powerful.
This book is a step-by-step guide on how to think like a computer scientist. A step-by-step guide may sound dry and boring but this book is surprisingly full of humor. I believe the authors took a page from Douglas Adams and Monty Python when they wrote this book.
The beauty about this book is not just its humor. The beauty is in its compounding process of teaching hard problems by starting with a simple idea and then building on that idea to lead you step-by-step onto more complex, abstract algorithms.
Before you know it, you will be done with this book, thinking like a computer scientist and all the while having a lot of fun in the process.
Update: The Hacker News discussion about this article provides a number of alternative books to my list.