[Solved]: Good mathematical book on algorithms

Problem Detail: 

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.

Asked By : k.stm

Answered By : jrodatus

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/44779