# Tag Info

15

I have not (nearly) read enough books to name $5000 worth of them. Therefore, I will suggest some groups of literature you should cover as well as point you towards selected representatives. I can not claim to have read most of the books in full myself, so I have to rely mostly on descriptions, cursory impression and reputation. I have looked into or worked ... 13 Don Knuth is a teacher, and is always very thorough when he writes. So one should expect that he states all prerequisites in his books. To ascertain that, I went to look in my own issue of the first volume. Indeed the preface states some prerequisites on page v, which he sums up into "the single requirement that the reader should have already written and ... 11 For an introduction to the theory of computation I recommend you these great books (in order of increasing "complexity"): 1) Introduction to the Theory of Computation by Michael Sipser It is very readable, theorems are very well explained and there are plenty of exercises (some with solutions and/or hints) and references. 2) Computers and Intractability:... 11 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 answer the question better than just providing the table of contents of the book. PART 1: AUTOMATA AND LANGUAGES. 1. Regular Languages. 2. Context-Free Languages. ... 10 It is not easy to come by books that consider the denotational semantics of$\lambda\$-calculus. One possibility is: Roberto M. Amadio and Pierre-Louis Curien: Domains and Lambda-Calculi Type-theoretic accounts are easier to get hold of: Bob Harper, Practical Foundations of Programming Languages (there is also a printed version). Benjamin Pierce, Types and ...

10

Your list is extremely problematic. To start with, I would flatly skip books 6,11,12,14,15,16,17: Books 6, 11 and 15 are general mathematics which is not really needed unless you become a theoretical researcher. Books 12 and 14 cover recursion theory which is not computer science (even though it deals with computability!). Books 16 and 17 cover advanced ...

8

For Computer Science, I would recommend you Computer Science: An Overview 11th J. G. Brookshear. If you are more interested, you can attend one of the online courses, you can register for free and finish these courses online with exercises. I recommend you one of these: An Introduction to Computer Science from Harvard, more informations you can find ...

8

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 could browse through at my leisure. I ended up reading almost the whole book, even the chapters on topics I was already very familiar with, just because the book ...

8

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 The Complexity of Theorem Proving Procedures (Stephen A. Cook) 1.2 On the Conceptual Complexity of Algorithms (J. Hartmanis, R. E. Stearns) 1.3 Quicksort (C. A. ...

8

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 computational complexity per se. Arora and Barak's book (A&B) seems self-contained. For example, you don't need to know the parts of Sipser or similar books ...

7

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 Singapore, in which the lecturer used this textbook: A Concise Introduction to Mathematical Logic, 3rd edition, by Wolfgang Rautenberg Personally, I like both the ...

7

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 the meaning of truth, proof, and computability, (and self referential music and art and ... a bunch of other stuff) aimed at people with a little bit of ...

7

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 Approach by Arora and Barak, which is an advanced textbook. I would recommend against the historical approach of reading old papers. While some old papers are ...

7

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 Knuth. It may be though that he will sometimes describe applications. But you can always skip that, and I doubt it makes much of the content. You should not be too ...

6

"Introduction to Modern Cryptography", Jonathan Katz and Yehuda Lindell. This is a great book for learning about provable security. And for actual crypto protocols and algorithms, there's always the classic: "Handbook of Applied Crypto" by Paul van Oorschot, A. J. Menezes, and Scott Vanstone. This is more a reference book than a textbook. And its available ...

6

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, operational semantics, Hoare logic, and static type systems. The exposition is intended for a broad range of readers, from advanced undergraduates to PhD students ...

6

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 Proceedings for HOPL-I and HOPL-II were also published as books, for HOPL-III, both the papers and video recordings of the presentations are available. (...

5

The theoretical "core" of a CS degree would consist of (1) basic data structures and algorithms, (2) formal languages, automata, complexity, computability. For the first, "CLRS" is the most-used textbook: http://mitpress.mit.edu/books/introduction-algorithms For the second, Sipser: http://www.amazon.com/Introduction-Theory-Computation-Michael-Sipser/dp/...

5

"Normative" means something that has to be followed, part of the standard. "Informative" is explanations meant to be understood by mere human beings, and that might be ambiguous or inaccurate. It is not to be relied on. Read it to understand, refer to the normative parts where it matters.

5

You might also consider taking advantage of some of the many online courses available. For example, both Stanford and MIT offer (free) online courses in computer science, and I think there are many others available as well. As far as books go, I second most of Yuval's recommendations, except that CLRS is a great reference, but a little overwhelming as an ...

5

There are a few good books on the TSP problem where you are likely to find some relevant information: Lawler et al., eds. The traveling salesman problem: A guided tour of combinatorial optimization. Wiley, 1985. G. Reinelt. The traveling salesman: computational solutions for TSP applications. Springer, 1994. G. Gutin and A. P. Punnen, eds. The traveling ...

5

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

5

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 by Cormen, Leiserson, Rivest, and Stein Algorithms by Sedgewick and Wayne Dr Dobb's Essential Books on Algorithms and Data Structures This also includes ...

5

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 reasoning and list induction and this is provided in Lectures on Constructive Functional Programming. More generally, the text "Algebra of Programming", by Bird ...

5

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 language a pure functional language on which it is possible to reason equationally. One might want to consult a book like Certified Programing with Dependent Types ...

5

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, Introduction to the Theory of Computation. Linz, An Introduction to Formal Languages and Automata. And a couple of older ones: Michael Harrison, Introduction to ...

5

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 IMP language and then give references to semantics of lambda calculus (typed untyped) unless you are reading Gunter. I am listing down a few below that I have referenced a number of times: Operational Denotational and ...

4

You don't specify what your company specializes in, so it's not easy to provide more than general recommendations. On the whole, I think the list you've put together is pretty good, and I wouldn't remove anything from it. Just a couple of additions and comments: 1) Cormen is a standard text. Sedgewick is another standard text. I've always gotten more out of ...

4

Here is a random collection of books on advanced algorithms based on what I consider as great book about advanced algorithms. Of course this is only my personal opinion and there are many other good books. Approximation Algorithms by Vijay V. Vazirani The Design of Approximation Algorithms by David P. Williamson, David B. Shmoys Computational geometry: an ...

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