I'm reading Introduction to Algorithms and would like to know if learning the proofs is worthwhile.

  • $\begingroup$ Meh, proofs don't matter as long as it works. Or do they? $\endgroup$
    – Pradhan
    Feb 25 '15 at 22:48

That's up to you. Reading correctness proofs for algorithms is useful since:

  1. The proofs explain why the algorithms work. If you need to modify these algorithms, you'd better know how they work. Such an understanding is very useful even just for coding algorithms, and certainly for debugging them.
  2. The proofs are good examples of mathematical proofs. The mathematical notion of proof is one of the most important contributions of mathematics to the world, and is a way of knowing which you could find useful in life, even without using it yourself.
  3. If you continue in academia, say get a graduate degree, you might have to write such proofs in the future.

However, it is my understanding that most programmers don't come up with new algorithms, or even code classical ones. If this is your case, you can probably skip the proofs, indeed the entire course, if it were not made compulsory by your university (if any).

  • $\begingroup$ I don't really see how 2 and 3 apply. I know that knowing how to make proofs is useful, but I don't know why learning pre-made proofs would make me better at making proofs. Is it a practice makes perfect-type thing? $\endgroup$
    – Kelmikra
    Feb 22 '15 at 15:30
  • $\begingroup$ In order to become really proficient in proofs you have to come up with a few. But before you do that, you have to understand what a proof is. If you've never seen mathematical proofs before, chances are your conceptions of proofs are wrong. So yes, first you have to read a few, then you have to write a few. $\endgroup$ Feb 22 '15 at 18:06
  • 2
    $\begingroup$ Speaking as someone working in industry, I disagree with your conclusion. Indeed it is exceptional for programmers (outside certain highly specialized areas) to come up with new algorithms, but it is not so rare to have to decide between several algorithms, and to need to figure out which ones are appropriate for a particular problem (both in terms of correctness and performance). While this doesn't require writing proofs, it can require understanding proofs. Learning to prove algorithms is not required to be a programmer, but it does make one a better programmer. $\endgroup$ Feb 22 '15 at 20:35
  • 1
    $\begingroup$ @Kyth'Py1k Just like how programming has reusable patterns in it, writing proof also has patterns in it. Spotting these templates in pre-made proofs makes you better at creating your own proofs. $\endgroup$ Feb 22 '15 at 20:37
  • $\begingroup$ @Billiska Why not just learn the reusable patterns instead of specific proofs? Is learning by example simply easier? $\endgroup$
    – Kelmikra
    Feb 24 '15 at 2:07

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