Skip to main content
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 ...
Pål GD's user avatar
  • 16.7k
10 votes

Resources for studying the mathematical foundations of machine learning, for someone from a math/physics background

Your assumptions may be a little bit off. Deep learning is largely an engineering field, and it is a young and rapidly moving one. Most "why" questions don't have very good answers. To ...
D.W.'s user avatar
  • 161k
9 votes
Accepted

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 ...
manlio's user avatar
  • 2,062
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 ...
Mars's user avatar
  • 716
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, ...
Anton Trunov's user avatar
  • 3,479
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 ...
Jörg W Mittag's user avatar
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 ...
Apoorv's user avatar
  • 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, ...
Pseudonym's user avatar
  • 22.2k
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 ...
cody's user avatar
  • 8,233
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 ...
Musa Al-hassy's 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 ...
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. ...
Martin Berger's 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 ...
Vor's user avatar
  • 12.6k
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....
Vincenzo's user avatar
  • 3,317
4 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-...
Bobby Durrett's user avatar
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.'s user avatar
  • 161k
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 ...
Jakube's user avatar
  • 1,585
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 (...
Aristu's 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, ...
Noah Schweber's user avatar
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 ...
Andrej Bauer's user avatar
  • 30.9k
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-...
Yuval Filmus's 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.
gnasher729's user avatar
  • 30.5k
3 votes

Resources for studying the mathematical foundations of machine learning, for someone from a math/physics background

I was in an ML talk recently, where the speaker talked about how theory of ML has completely failed to explain much of anything that we do in practice. Take, as one simple example, stochastic gradient ...
darwinflinches's user avatar
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 ...
tvo's user avatar
  • 121
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, ...
Pseudonym's user avatar
  • 22.2k
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 ...
Aristu's user avatar
  • 1,483
2 votes

What are the basics of CS i should know,before I start my journey into machine learning

Computer science is a very broad subject area, and many of its sub-disciplines have little or no overlap with others. For example, knowing the basics of operating systems design, compiler design or ...
gandalf61's user avatar
  • 1,589
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 ...
vonbrand's user avatar
  • 14.1k
2 votes

Computation Complexity books for a mathematician

I can recommend the book Computational Complexity Theory, edited by Steven Rudich and Avi Wigderson, which is based on a graduate summer school by the IAS/Park city mathematics institute, with ...
Discrete lizard's user avatar
  • 8,303
2 votes
Accepted

How to implement random sampling with continuous variables?

One standard approach is to use inverse transform sampling: if $F$ is the cdf of the desired random variable and $U$ is uniformly distributed, then $F^{-1}(U)$ has the desired distribution. There are ...
D.W.'s user avatar
  • 161k

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