Computer Science in mathematical setting

Question

I have come to like math better than coding. Maybe because I am a beginner in both coding and math, I prefer taking math proofs apart and playing around with them to seeing some trivial piece of code do some trivial thing.

I'd like to explore the mathematical side of programming using pen and paper. Are there any books that deal with programming problems in mathematical setting? Or what would be the branch of knowledge that studies coding or generally computer science problems purely from math standpoint?

Thanks.

Answer 1

The theory of algorithm analysis and design has a large portion which is quite pure mathematics. There are plenty of hard and open questions related to computability and complexity (other than the famous $P=NP$ problem).

More on the side of the foundations of computation, logic (e.g., Turing machines) is strongly related to imperative programming languages while $\lambda $-calculus is related to functional programming.

Finally, the general theory of programming languages design and analysis is strongly related to category theory.

These are several routes you can try to take that, I hope, will answer your question.

Answer 2

Two books on mathematical CS that I like are Introduction to the Theory of Computation by Michael Sipser and Languages and Machines by Thomas Sudkamp. Another person you could look up is Edsger W. Dijkstra. He was the most paper oriented CS person that I know of.

Answer 3

There are many places that mathematics and computer science intertwine. One example is finding the zeros (or equivalently the fixed point) of a function. We can often find sufficient conditions for the existence of a root, but we need an algorithm to construct (or explicitly name) one. A possible solution to this problem is the bisection method which solves it for continuous functions. Another solution is Newton's method if your function is differentiable. Implementing these algorithms can be a challenge and a good indicator of how well you understand a language.

One thing that sets computer science apart from math is that there is an emphasis on speed which is a natural follow up to existence theorems from math. Another problem is finding the integral of a function. You can of course use Riemannian sums, but this is very inefficient. Better solutions include the rectangle method or Simpson's Rule. The thing from mathematics which most closely resembles black magic to me is called Gaussian quadrature and is another solution to this problem which calculates the approximation (sometimes the exact answer) by only evaluating a couple of points.

You really should consider working in both subjects as they complement each other. Math can provide the bare minimums for a solution, then computer science asks how we can find the solution faster which can lead to more interesting questions back in mathematics.

Answer 4

Some books that helped me in this area:

1. Art Lew "Computer Science: A Mathematical Introduction"
2. John Hopcroft and Jeffrey Ullman "Introduction to Automata Theory, Languages and Computation"
3. Hopcroft and Ullman "The Design and Analysis of Computer Algorithms"
4. Richard Johnsonbaugh "Discrete Mathematics" (More of a general purpose Discrete Maths book and done at a MUCH gentler place than the others!)

Combine these with the three volumes of Knuth (ie "The art of Computer Programming") and the two volumes of Apostol's "Calculus" books and you should have (just) enough knowledge to tackle a PhD in Computer Science! :-) Hope this help!

Answer 5

Concrete Mathematics: A Foundation for Computer Science [Ronald L. Graham, Donald E. Knuth, Oren Patashnik]