11
$\begingroup$

I’m a sucker for mathematical elegance and rigour, and now am looking for such literature on algorithms and algorithm analysis. Now, it doesn’t matter much to me what algorithms are covered, but very much how they are presented and treated.¹ I most value a very clear and precise language which defines all used notions in a stringent and abstract manner.

I found that the classic Introduction to Algorithms, by Cormen, Leiserson, Rivest and Stein is pretty neat, but doesn’t handle the mathematics well and is quite informal with its proofs and definitions. Sipser’s Introduction to the Theory of Computation seems better in that regard, but still offers no seamless transition from mathematics to algorithms.

Can anyone recommend something?

¹: The algorithms should at least invole the management of their needed data using classical non-trivial abstract data structures like graphs, arrays, sets, lists, trees and so on – preferably also operating on such data structures. I wouldn’t be too interested if the issue of usage and management of data structures was ignored altogether. I don’t care much about the problems solved with them, though.

|cite|improve this question
$\endgroup$
  • 2
    $\begingroup$ This is subjective; define "good". Also, while we don't have a strict policy for list questions, there is a general dislike. Please note also this and this discussion; you might want to improve your question as to avoid the problems explained there. If you are not sure how to improve your question maybe we can help you in Computer Science Chat? $\endgroup$ – Raphael♦ Jul 27 '15 at 15:28
  • $\begingroup$ Related question. $\endgroup$ – Raphael♦ Jul 27 '15 at 15:29
  • $\begingroup$ @Raphael Thanks. I only used the word “good” in the title, in my question I specified what I want. While I intentionally did not get too specific, it should at least be clear that my focus is (as hinted) at mathematical elegance and rigour. I don’t think this answer screams for a list of books, because there shouldn’t be too many books falling into that category, – and even if so, I don’t believe in that “preserving the purity of a strict question–answer structure” thing going on at several stackexchange sites here – but not my call, I guess. I’m not sure if I can improve the question. $\endgroup$ – k.stm Jul 27 '15 at 16:52
  • $\begingroup$ Also, I don’t think the “reference-request” is appropriate for the question. At least not according to its description: Neither am I looking for papers nor am I interested in a specific and narrow issue. In fact, I am pretty open as to what contents are covered, see my second sentence. Is it okay if I remove the tag again? Maybe I could and should narrow down with what sort of algorithms I would be content? $\endgroup$ – k.stm Jul 27 '15 at 16:55
  • 2
    $\begingroup$ Perhaps you should look into denotational semantics and program verification. $\endgroup$ – Yuval Filmus Jul 28 '15 at 5:12
7
$\begingroup$

Hendrik Lenstra wrote in 1992:

Although it is, from a rigorous mathematical point of view, desirable that I define what I mean by an algorithm and its running time, I will not do so. My main excuse is that I do not know these definitions myself. Even worse, I never saw a treatment of the appropriate theory that is precise, elegant, and convenient to work with. It would be a laudable enterprise to fill this apparent gap in the literature.

I do not know whether any progress has been made since then, or whether this is even considered a "gap" by the consensus. But the point remains that at least some eminent mathematicians have been dissatisfied with the mathematical rigour of the derivation of algorithms. So, it may be there exists no book with the OP's desired level of formalism.

The cornucopia of practical perspectives we have due to Knuth, Gries, Stepanov, and others are intended to aid programmers more than mathematics and so inevitably fall short on rigor and long on subjectivity.

Nonetheless, Stepanov's work is widely acclaimed in Silicon Valley as one of the best attempts at a scientific synthesis.

In Elements of Programming, Alexander Stepanov and Paul McJones attempt to lay the abstract algebraic foundations of algorithms. The book begins with admittedly somewhat informal axiomatic definitions of entities, values and their attributes, but in 288 pages progresses deductively via a series of lemmas to the foundations of the Standard Template Library.

The TOC, preface and a sample chapter on Transformations and Their Orbits can be found here, and an introductory lecture here.

Stepanov's more recent and relaxed book, From Mathematics to Generic Programming, is structured more by a roadmap of the history of mathematics, building from Egyptian multiplication to monoids, semigroups, and Lagrange's theorem, eventually developing modern data structures with their iterators and algorithms used in the STL.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ ?!? "there currently exists no precise, elegant, and convenient mathematical derivation of the concept of an algorithm..." how about a Turing machine! $\endgroup$ – vzn Jul 30 '15 at 1:01
  • 1
    $\begingroup$ Lenstra does address Turing machines in the linked paper, but I think the idea is that they don't provide a full algebraic analysis. The quotation is pretty much verbatim, including the "gap" part, if you'd like to read it yourself. I'll edit the post to remove the suggested "consensus", in case it should be considered debatable. $\endgroup$ – user35908 Jul 30 '15 at 1:07
  • $\begingroup$ ofc am/ was aware you were quoting Lenstra but you could add quotes or a longer blockquote of his remarkable/ debatable/ questionable assertion $\endgroup$ – vzn Jul 30 '15 at 2:05
  • $\begingroup$ think that Turing machines cannot be derived, to the contrary they form the axiom of a computational system (ala the Church-Turing thesis). it is all of Lenstras analysis and CS in general that is derived from the axiom of the TM existence. $\endgroup$ – vzn Jul 30 '15 at 2:13
  • 1
    $\begingroup$ @Raphael, if mom says it would be a "laudable enterprise" to clean my room properly, the gist of her speech is "don't bother with cleaning your room." Am I misunderstanding you, or are you misunderstanding me? $\endgroup$ – user35908 Mar 30 '16 at 8:31
7
$\begingroup$

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 disappointed with the maths.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ I feared this answer might come up. I onced looked into it and it didn’t suit me. “You should not be too disappointed with the maths.” – maybe, but Knuth also doesn’t seem to define stuff, but he rather introduces it informally, explaining it. Great to get the idea across, not what I expect of mathematics, though. $\endgroup$ – k.stm Jul 27 '15 at 22:38
  • $\begingroup$ Maybe you could contribute to the field by publishing the mathematically obfuscated version of his work. But if what interests you is the "seamless transition from mathematics to algorithms", a better topic for you could be type theory. The relation between mathematics and algorithms is still a research topic. $\endgroup$ – babou Jul 27 '15 at 22:50
  • 1
    $\begingroup$ P.S. If you "feared this answer might come up", you should have said so in your question as it is one of the major reference books. Complete and documented questions get better answers. $\endgroup$ – babou Jul 27 '15 at 23:02
  • $\begingroup$ It only came to me after having asked the question, when I was away from my computer. My remark on Knuth’s book shouldn’t be taken in a pejorative way (which is how I think you have taken it for the “publishing the mathematically obfuscated version” comment) – that would be like next to blasphemy, probably. His way just is not what I am looking for either. Maybe there just isn’t anything like what I imagine out there … $\endgroup$ – k.stm Jul 27 '15 at 23:28
  • 2
    $\begingroup$ @k.stm Well, forget the obfuscation thing which is a whole topic in itself. The point is, I believe that algorithmics is not (yet?) mathematics. It may be that you can get formalizations, but they are likely to be simple encodings that lose the substance, with little benefit. That depends on the topic. It is probably much less true for automata theory, which does have significant algorithmics. The point is that identifying adequately the abstract mathematical nature of structures is non obvious. It is a matter of understanding, not of formalization, and it takes years. Think of it like physics $\endgroup$ – babou Jul 27 '15 at 23:51

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