2
$\begingroup$

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

$\endgroup$

closed as primarily opinion-based by D.W., David Richerby, Wandering Logic, Raphael Feb 23 '15 at 7:10

Many good questions generate some degree of opinion based on expert experience, but answers to this question will tend to be almost entirely based on opinions, rather than facts, references, or specific expertise. If this question can be reworded to fit the rules in the help center, please edit the question.

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

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).

$\endgroup$
  • $\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$ – Yuval Filmus 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$ – Gilles 'SO- stop being evil' 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$ – Apiwat Chantawibul 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.