I'm interested both mathematics and computer science. I like math because one can formalize it rigorously and I have seen that many things can be defined by sets. Is there similar thing in computer science, as for example asymptotic notation is sometimes defined in very odd way, see https://math.stackexchange.com/questions/2731290/how-one-can-define-rigorously-the-time-and-space-complexities-of-algorithms ? I'm looking way to learn CS in a very rigorous way.

  • 1
    $\begingroup$ Give some more context. What level are you? Why only self-learning as a tag? Why do you think the run time estimates are not rigorous? $\endgroup$ – Buffy Aug 16 '18 at 10:45
  • 1
    $\begingroup$ I'm not entirely sure what you mean by a "rigorous way." On the flip side, it seems you're looking for ways to "define" things in CS rigorously, not "learn" CS rigorously. $\endgroup$ – Gypsy Spellweaver Aug 16 '18 at 16:40
  • $\begingroup$ I have been asked to review this question (should I close). There are two comments that you need to address. Please improve the question, or it may be closed. $\endgroup$ – ctrl-alt-delor Aug 21 '18 at 10:47
  • $\begingroup$ By "rigorous" I'm assuming you mean in a way that can be formally proven (in the mathematical proof sense) to be correct or incorrect. Most programs which can be rigorously demonstrated to be correct are trivial. As real world complexities creep in it gets harder and harder to create formal proofs of correctness. $\endgroup$ – Onorio Catenacci Aug 24 '18 at 15:23

Be careful of what you wish for. Assuming you want rigorous self study, I'll recommend a few books. They are fairly old, but are classics.

The Art of Computer Programming. Knuth is a mathematician at heart. The link is to the boxed set, but you can buy individual volumes.

Elements of the Theory of Computation. This is as rigorous as you want to be and addresses directly the question of run-time bounds of various sorts.

Similar is

Introduction to the Theory of Computation by Sipser

A somewhat different view of computation is found in

Structure and Interpretation of Computer Programs: A classic introduction to functional programming in Scheme - yet quite deep.

For what it's worth, I have a doctorate in Mathematics and taught CS for over 40 years.


Relational Databases and SQL.

The Relational Database came from very arcane foundations in Mathematics which I still do not understand. But I have reduced the description and steps for the first 3 Normal Forms (which took a decade to develop) down to a few sentences! I hand that out to my students.

If there is anything more math-y in computing than databases, I have yet to see it. "A minute to learn, a lifetime to master." It is the most useful thing you can become an expert at, and largely uncontroversial. (Except for Nulls. Maybe you can help smooth that one out for us!)


Not the answer you're looking for? Browse other questions tagged or ask your own question.