Hot answers tagged

11 votes
Accepted

Theory of computation introductory curriculum

Introduction to the Theory of Computation by Michael Sipser is a relatively recent entry into this field. It was the required book for a class my friend was taking, and I asked him for the PDF so I ...
user avatar
  • 2,190
11 votes
Accepted

Computation Complexity books for a mathematician

Michael Sipser's text book Introduction to the Theory of Computation is a classic introduction to computation theory, and gives an introduction to complexity theory in the end. I don't know how to ...
user avatar
  • 13.3k
8 votes

Theory of computation introductory curriculum

For someone just getting started in Computer Science I would recommend Douglas Hofstadter, Gödel, Escher, Bach: an Eternal Golden Braid, Basic Books, 1979. It is a philosophy book discussing ...
user avatar
8 votes

Book containing many important CS papers

If I had to bet, I'd say: Great Papers in Computer Science Author: Laplante, Phillip A. Publisher: West Publishing Co. (this one or an older edition). Contents Algorithms and Data Structures 1.1 ...
user avatar
  • 1,927
8 votes

Computation Complexity books for a mathematician

You might want to consider Computational Complexity: A Modern Approach by Arora and Barak. Roughly speaking, its early chapters overlap with later chapters in Sipser, and it has more material on ...
user avatar
  • 686
7 votes

Introductory book on Logic and Computation

My answer could be late for this question, but I hope it will be helpful for other people looking for similar information. I had taken a course about Mathematical Logic at National University of ...
user avatar
  • 221
7 votes

Good mathematical book on algorithms

I think the book you describe has a name. It is in seven volumes, only three and half of which have been published. It is called The Art of Computer Programming, (TAOCP) and is written by Donald ...
user avatar
  • 19.1k
7 votes
Accepted

Good introduction to Turing's work and complexity theory?

Some popular books are Computational Complexity by Papadimitriou and Introduction to the Theory of Computation by Sipser. If you are very ambitious, you can also try Computational Complexity: A Modern ...
user avatar
6 votes

What are common formal techniques for proving functional code correct?

You can start with Software Foundations by Benjamin C. Pierce et al. Topics include basic concepts of logic, computer-assisted theorem proving, the Coq proof assistant, functional programming, ...
user avatar
  • 3,419
6 votes

Good book on the history of programming languages?

There is an infrequently held conference series called History Of Programming Languages (HOPL). It was held in 1979, 1993, and 2007, the fourth installment is scheduled for middle of June, 2020. The ...
user avatar
5 votes

Is Horowitz and Sahni's data structure book outdated?

Yes. I strongly recommend Pat Morin's more modern textbook Open Data Structures, available for free in several dialects at http://opendatastructures.org/.
user avatar
  • 8,563
5 votes

What are common formal techniques for proving functional code correct?

It turns out that an excellent source of proof techniques and examples for proving things about pure functional languages is proof assistants which usually include as part of their specification ...
user avatar
  • 7,744
5 votes
Accepted

What are common formal techniques for proving functional code correct?

One of the de facto methods for proving results in functional programming is via Richard Bird's group. In particular, you ask for an in-depth or at least more comprehensive approach to equational ...
user avatar
5 votes
Accepted

Rigorous Books on Algorithms

Note: please edit this answer and add to it, do not create new answers Rigorous books: The Art of Computer Programming by Knuth A Discipline of Programming by Dijkstra Introduction to Algorithms ...
5 votes
Accepted

Textbook for understanding formal grammars

Probably the most-used textbook today is: Hopcroft, Motwani, & Ullman, Introduction to Automata Theory, Languages, and Computation (3rd edition). A couple of other common ones are: Sipser, ...
user avatar
  • 18.9k
5 votes

What should I read to understand semantics of programming languages?

There are many depending on where you want to start and what exactly you want. Usually textbook start with giving semantics to the While or ...
user avatar
  • 619
4 votes

What are common formal techniques for proving functional code correct?

I suggest to use program logics. They deal much better with effects than typing systems. There are numerous program logics for functional languages. This becomes interesting with effects. See e.g. ...
user avatar
4 votes

books on algorithms for beginners in Ruby or Python or C. Not too math heavy

To be honest, it doesn't really matter what languages you use to learn an algorithm (it's only the syntax that changes, the logic is the same). However, if you want a Python specific one check out: ...
user avatar
4 votes
Accepted

Introductory book on Logic and Computation

I suggest one of the book I recently bought: Pavel Pudlak: Logical Foundations of Mathematics and Computational Complexity - A Gentle Introduction; Springer Monographs in Mathematics; 2013 I had not ...
user avatar
  • 12.2k
4 votes
Accepted

Which textbook can I use after a high school CS course?

Personally, I recommend either Algorithms by Dasgupta, Papadimitriou, and Vazirani, or The Algorithm Design Manual by Skiena. The Algorithm Design Manual is super-practical and full of excellent ...
user avatar
  • 141k
4 votes

Introductory Book on Pseudo-Random Number Generation

The book Random numbers and computers by Ronald T. Kneusel, recently published by Springer, contains pseudorandom number generation algorithms, evaluation techniques, and code examples in C and Python....
user avatar
  • 3,162
4 votes
Accepted

What textbooks includes explanations of advanced data structures found commonly in competitive programming?

Here are two books written especially for competitive programming: "Guide to Competitive Programming", Antti Laaksonen: The book is based on the book "Competitive Programmer's Handbook" by the same ...
user avatar
  • 1,336
4 votes

Book recommendations on the analysis of randomized algorithms

Randomized Algorithms by Motwani, Rajeev, and Raghavan contains a lot of excellent material on the design and analysis of algorithms. They show many proofs of correctness for different randomized ...
user avatar
  • 141k
3 votes

Which textbook can I use after a high school CS course?

Cormen et al (CLRS) is aimed towards (undergrad) university students so it may be hard to follow with your current level of mathematics. So, if it has to be one of the two, Skiena may be the more ...
user avatar
  • 70.9k
3 votes

How to enhance my skills as a programmer

You don't need books. You need to write lots of programs. Since you are interested in cryptography, you should practice writing programs that involve mathematics. A good way to do so is to join ...
user avatar
  • 28.2k
3 votes

What should I read before tackling Michael Huth's Logic in Computer Science: Modelling and Reasoning about Systems?

From the Preface of the 2nd Edition: The book requires that students know the basics of elementary arithmetic and naive set theoretic concepts and notation. The core material of Chapter 1 (...
user avatar
  • 1,483
3 votes
Accepted

Textbooks about non-RE languages for undergraduate students

Despite its name, Soare's book Recursively enumerable sets and degrees has lots of information about this. In particular, it covers in pretty good detail the arithmetical hierarchy. (Incidentally, ...
user avatar
3 votes

Book recommendations on the analysis of randomized algorithms

I do not know if it meets your needs but MIT's OCW site has free lecture notes from a class on the subject here: https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-856j-...
user avatar
3 votes
Accepted

Are there any differences between the various editions of The Art of Computer Programming?

They are not the same. The 1985 edition that I have includes RSA for example which wasn’t there earlier. Not sure about newer version.
user avatar
  • 25.2k

Only top scored, non community-wiki answers of a minimum length are eligible