Mathematical Problem Solving

Question

Will a study of the mathematical proof of a (data structure and algorithm based) problem, when posed as a proposition, highlight peculiar properties of the problem which may help in designing an optimal algorithm?

I think that proofs should yield interesting insights, and therefore can be used in designing algorithms. Since the program is expected to return a true response for every input, proof must be, in some way, built into the program. Is there any text I can refer to in this regard which will help in real problem solving?

Answer 1

Will a study of the mathematical proof of a problem [..], highlight peculiar properties of the problem which may help in designing an optimal algorithm?

Often they do. But not necessarily (unless you're a scholar of constructivism), for example when using the probabilistic method to show that a solution to said problem exists, then the proof will not help you designing any algorithm since it does not give you a construction.

Since the program is expected to return a true response for every input, proof must be, in some way, built into the program.

That would be nice if it were the case, but often proving correctness (see formal methods) of an algorithm is rather difficult and/or a real pain. That said, there is such a thing as proof-carrying code which does exactly that, but the proofs are not given to you for free.