From Prof. Tom Leighton
Prove that n^3 + 3n^2 + 2n is dividible by 3.
Ans : It's n^3 - n + 3( n^2 + n). And n^3 - n is (n-1)n(n+1) and one out of every 3 #'s is div by 3. QED
Class taught by a billionaire with a $1 salary.
What :
Proofs - what they are, good and bad ones. Why proofs? You want to be able to prove your software won't do something bad.
Induction, strong induction, invariants - very useful for the "proving" related to undesired states.
GCD of 2 numbers is a linear combination of the numbers. Euclid's theorem and lemma : GCD(a,b) = GCD( rem(b,a), a) -- very cute one.
No comments:
Post a Comment