15.082J & 6.855J & ESD.78J15.082Overview of lectureWhat is a proof?Proof by contradictionProof by Contradiction: √2 is irrationalTheorem: There are infinitely many prime numbers.ContrapositiveProof by inductionSlide 10Theorem: every tree with n nodes has n-1 arcs.Assume the theorem is true if there are at most k nodes.Proofs by minimum counterexampleProof by Minimum Counterexample: every tree with n nodes has n-1 arcs.Let T be the minimal counterexample.Mental BreakSlide 17Proving an algorithm is correctProof that Euclid’s Algorithm is correctInductive StepProof of FinitenessBreadth First SearchProving the key invariantSlide 24Slide 25SummarySlide 2715.082J & 6.855J & ESD.78J Algorithm Analysis15.082•Overview of subject•Importance of Algorithm Analysis•Importance of homework•Midterms•Moving forward2Overview of lectureProof techniques•Proof by contradiction•Mathematical Induction•Smallest counterexampleAlgorithm Analysis•Quick review of proving correctness•Euclid’s algorithm for computing gcd•Proof that bfs gives shortest distances3What is a proof?From Wikipedia: In mathematics, a proof is a convincing demonstration (within the accepted standards of the field) that some mathematical statement is necessarily true.Proofs are obtained from deductive reasoning, rather than from empirical arguments. That is, a proof must demonstrate that a statement is true in all cases, without a single exception.4Proof by contradictionFrom Wikipedia: A proof by contradiction is a form of proof that establishes the truth or validity of a proposition by showing that the proposition being false would imply a contradiction. Since … a proposition must be either true or false, and its falsity has been shown impossible, the proposition must be true.5Proof by Contradiction: √2 is irrational 6Defn: a rational number can be expressed as a/b, where a and b are integers.Theorem: √2 is irrational. Proof. Suppose that √2 = a/b, where a and b are integers. Suppose further that a/b have no common divisors greater than 1. Then 2 = a2/b2, and a2 = 2 b2. Since a2 is even, it follows that a is even. Suppose a = 2c. Then (2c)2 = 2 b2 ⇒ 4c2 = 2b2 ⇒ 2c2 = b2 ⇒ b is even. But this contradicts that a and b have no common divisors. So, √2 is irrational. QEDTheorem: There are infinitely many prime numbers.7Fact that will be used in the proof: Any integer that is not a prime number has a factor that is a prime number. Proof of theorem (by contradiction). Suppose that there are finitely many primes.Let {p1, p2, …, pn} be the set of prime numbers.Let x = 1 + (p1 × p2 × … × pn).Then pj is not a divisor of x for j = 1 to n, which contradicts the fact given above. Therefore there are infinitely many primes.ContrapositiveThe contrapositive of “A B” is “¬B ¬A”.⇒ ⇒The contrapositive is logically equivalent to the original statement.Example: All monkeys are mammalsContrapositive: If something is not a mammal, it is not a monkey.8B AExample: If a point is in A, it is in B.Contrapositive: If a point is not in B, it is not in A.Proof by inductionThink first about dominos. Suppose 86 dominos are lined up so that if domino i falls, then domino i+1 will fall. Suppose also that domino 1 falls. Will domino 86 fall? 9Video of PC dominosProof by induction10Mathematical induction is a method of mathematical proof typically used to establish that a given statement is true of all natural numbers. It is done by proving that the first statement in the infinite sequence of statements is true, and then proving that if any one statement in the infinite sequence of statements is true, then so is the next one.Theorem: every tree with n nodes has n-1 arcs.Facts that we will use in the proof. 1. Every tree with at least two nodes has a node with exactly one incident arc. 2. Deleting a node with degree 1 from a tree, results in a tree.11Step 1. Establish the basis of the induction. It is easy to see that trees with two nodes have one arc.Step 2. Inductive Step We need to show that the conclusion is true for all trees of k+1 nodes if it is true for all trees of k nodes.Assume the theorem is true if there are at most k nodes.Let T be any tree with k+1 nodes.Let node j be a node with degree 1.12jT’ = T\jT’ has k nodes. By the inductive hypothesis T’ has k-1 arcs. T has one more node and one more arc than T’. So, T’ has k+1 nodes and k arcs. QEDProofs by minimum counterexampleThis technique combines a proof by contradiction with a proof by induction. The induction works in the opposite direction, from k to k-1.Step 1. Assume that the theorem is false and that there is a counterexample.Step 2. Show that there is no counterexample with n = 1 (or 2).Step 3. Show that if there is a counterexample with n = k, then there is a counterexample with n < k. This shows that there can be no smallest counterexample, and thus no counterexample.13Proof by Minimum Counterexample: every tree with n nodes has n-1 arcs.Facts that we will use in the proof. 1. Every tree with at least two nodes has a node with exactly one incident arc. 2. Deleting a node with degree 1 from a tree, results in a tree.14Step 1. Establish that the theorem is true for n = 1 or 2. It is easy to see that trees with two nodes have one arc.Step 2. Counterexample step. We need to show that the conclusion is false for some tree of k-1 nodes if it is false for some tree of k nodes.Let T be the minimal counterexample.Let T be the counterexample with k nodesLet node j be a node of T with degree 1.15jT’ = T\jBy assumption, T has k nodes but does not have k-1 arcs. T’ has k-1 nodes and one fewer arc than T. Thus T’ does not have k-2 arcs, and is a smaller counterexample than T. QEDMental BreakHow many copies of Moby Dick were sold during Herman Melville’s lifetime. 50 copiesThere was an event that occurred the same day as the birth and the death Samuel Clemens (Mark Twain). What was it. The appearance of Halley’s comet.What famous author coined the word “nerd” Dr. Seuss, in If I Ran the Circus.In how many of the Sherlock Holmes books by Sir Arthur Conan Doyle did Holmes say “Elementary, my dear Watson”? None.Ernest Vincent Wright wrote Gadsby, which is 50,000 words long. What is Gadsby most famous for? It does not contain the letter