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 ...
- 15k
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 ...
- 696
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 ...
- 1,997
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 ...
- 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 ...
- 19.4k
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, ...
- 3,469
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 ...
- 5,821
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 ...
- 659
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, ...
- 21.3k
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 ...
- 7,979
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 ...
- 884
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 ...
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....
- 3,252
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 ...
- 12.4k
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. ...
- 8,308
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 ...
- 1,570
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 ...
D.W.♦
- 154k
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 (...
- 1,483
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 ...
- 29.9k
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, ...
- 2,674
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-...
- 141
3
votes
Accepted
Is there a book with 100 reductions?
The classical reference on NP-completeness is Garey and Johnson's Computers and Intractability, which contains a compendium of over 300 NP-complete problems, with links to papers proving their NP-...
- 274k
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.
- 27.8k
2
votes
Introductory book on Logic and Computation
I like Tom Stuart's book "Understanding computation" with respect to modeling computation. He offers a nice progressive overview of models for computation. If I recall correctly:
- deterministic ...
- 121
2
votes
A good introductory book on cryptography
I'd recommend "Understanding Cryptography", Christof Paar & Jan Pelzl, if you are self teaching some cryptography. Why? Since it can be really hard to just follow a textbook by yourself, professor ...
- 1,483
2
votes
Accepted
How are HOGs calculated?
First, let's talk about what a histogram of directions is. You can think of the image as a 2D discrete function of x and y: I(x,y). You can take partial derivatives of this function: Ix and Iy. So at ...
- 568
2
votes
Accepted
Introductory Book on Pseudo-Random Number Generation
This isn't a book, and it's not a complete introduction, but Melissa O'Neill's tech report, PCG: A Family of Simple Fast Space-Efficient Statistically Good Algorithms for Random Number Generation, ...
- 21.3k
2
votes
Textbooks about non-RE languages for undergraduate students
Any book on computability will cover the subject.
In any case, if a language is not recursively enumerable, it means no Turing machine (or program in any language, for that matter) is able to ...
- 13.9k
2
votes
Accepted
How to enhance my skills as a programmer
Cryptopals challenges
I would really suggest going over the practical exercises on http://cryptopals.com/ which will (hopefully) illustrate practical known weaknesses of existing cryptosystems and ...
- 426
Only top scored, non community-wiki answers of a minimum length are eligible