Thursday, February 14, 2013
Proof by induction for algorithms using 'course of values' induction: Strings in Python:
With standard induction: Can be bounded by single quotes, double quotes or even triple quotes.
Prove the statement E(n) is true for all n in a set Multiple things to start string because of apostrophes or quotation marks within strings…
Base case: ex: "It's a sunny day" would work but 'It's a sunny day' would not
ProofE(n)is truefor firstelement ex2: 'Tome said "Whyis there,"owlishly'
Inductive step: ex3: 'He\'s here'
Assume E(n) is true for n
Prove that if E(n) is true, then E(n+1) is also true
Strings are immutable. You cannot change a piece of a string without making a copy that has the wanted
Course of values induction: changes
Assume E(n) is true for all elements of the set up to n Built in functions: \t = tab char
\n = new line