# Are proofs worth the effort?

I bought the de-facto book for learning about data structures and algorithms (CLRS). The book is though quite good but the singularity is in the proofs. The book is filled with Lemmas, theorems, peculiar symbols and unimaginable recurrence relations which are very hard to understand. I am able to somehow get the algorithms but the discrete mathematics just not for me.

So should I leave them out and just concentrate on algorithims?

-
If you want to grasp the "why" of the content then yes which will almost certainly make you a better programmer. – Rig Jul 2 '12 at 15:35
@Rig: Certainly. but just have a look at error probability proof of Miller-Rabin primality testing. Just the size gives me headaches. – Shashank Jain Jul 2 '12 at 15:47
Proofs help you understand when you totally mess up the algorithm implementation. Saw a misunderstanding in the formula on a spreadsheet nearly sink a company once. Sometimes people who can just plug algorithms shouldn't be doing it as they don't know how to test the output to see if they really got it right. – Fiasco Labs Jul 2 '12 at 15:48
The Miller-Rabin primality test is an example of an algorithm with a proof that is MUCH more complicated than the algorithm itself. I recall spending a big chunk of time just to research some of the individual lines of that proof, though someone with a better grounding in the relevant theory would probably have better luck. Proofs for randomized primality-testing algorithms are complicated. – Brian Jul 2 '12 at 17:06
What's on the other side of the equation? If you're choosing an algorithm for your nuclear fusion reactor, you should definitely worry about this. If you're trying to build a blog for your cat, not so much. For anything in between ... it depends. – Piskvor Jul 2 '12 at 17:45

Usually looking through the proof helps to understand the algorithm better. It shows why the algorithm works and what facts it is based on. Sometimes it even helps to see what the author was thinking about, or gives a clue how to edit and/or optimize the algorithm for special needs.

If later you'll need to make your own algorithm, these proofs will really help. On the other hand, if you just need to use some famous algorithms, it's ok to miss the proofs. But I'd still recommend you take a look at them. Even if you don't understand everything in details, at least try to take your time and grasp the general idea.

-

To judge whether something is 'worth the effort' you must consider the value to you of what you get for your effort. In this case, learning to understand the proofs would mean, well, that you understand the proofs. We can't decide for you how much you consider that worth.

If you are happy to look up a list of algorithms and costs, then by all means do so.

Mind you, there is the nagging worry that if you do skip the proofs, if you ever find yourself in a situation where you come across (or even think up for yourself) a method you can't find documented anywhere, you won't know what to do...

-

If you look for a `practical way` to understand and/or implement the algorithms, I would suggest a different book - Practical Algorithms for Programmers .

However, if you are looking at academics and theory part to build your own customized algorithm and base it on some other existing once, you may probably continue with what you have.

-

In my opinion, proofs are not really terrifically useful, unless you're inventing the algorithm in question, or looking to work in theoretical CS. If you're just implementing the algorithm, what's important is that you can understand the description, and that you know it has been proved to be correct.

-
I think programmers are making themselves a bad favor by refusing to study anything more pure than "How to write code". Math is useful, sooner or later. Then again, I studied math and loved it, so I'm not exactly impartial. – K.Steff Jul 4 '12 at 0:19

Here is a great example of why proofs are necessary and why you should be able to understand and come up with them: http://stackoverflow.com/q/11320423/811001

Many times while programming, you'll have to come up with your own ad-hoc algorithms. Or perhaps you need to make an optimization to an existing algorithm. In those cases, you better be able to back up your algorithm/optimization with a proof of why it works.

-