monyet's blog

Proof this, proof that, proof everything
By monyet, 10 years ago, In English

Hello guys, sometimes i'm having trouble proofing my algorithm correctness. I've seen many Editorial where the author make some lemmas and proof their correctness. Is there a book where I can learn something like that? I've read several books this , it doesn't help much.

Thanks guys!

  • Vote: I like it
  • +8
  • Vote: I do not like it

»
10 years ago, # |
  Vote: I like it +16 Vote: I do not like it

One way to proof an algorithm is, find something that is always true when the program iterates over. You need to: 1.prove that the condition is true before start; 2.proof iterations will not change it.

And it sounds very similar to Proof by Induction in math. Maybe some math proving guide is helpful too.

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I think a rigorous introductory class on algorithms would be good. You should be able to find such MOOC courses on Coursera, MIT OpenCourseWare, ...

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

This is a really great text on the said topic :-

http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-042j-mathematics-for-computer-science-spring-2005/lecture-notes/l2_proofs.pdf

→ Reply