[Solved]: Good mathematical book on algorithms

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.