PDF4PRO ⚡AMP

Modern search engine that looking for books and documents around the web

Example: confidence

Proving Algorithm Correctness

Back to document page

CS 5002: Discrete StructuresFall 2018Lecture 11: November 20, 20181Instructors: Adrienne Slaughter, Tamara BonaciDisclaimer:These notes have not been subjected to the usual scrutiny reserved for formal may be distributed outside this class only with the permission of the Algorithm CorrectnessReadings for this week:Rosen: Chapter 5: Induction and RecursionObjective: Analyzing Divide and Conquer Algorithms1. Review of Mergesort2. Ways to prove algorithms correct Counterexample Induction Loop Invariant3. Proving Mergesort correct4. Other types of IntroductionLast week, we focused on computing runtime of algorithms, in particular divide-and-conquer and Merge Sort AlgorithmMerge-Sort(A, low, high)1if(low < high)2mid=b(low+high)/2c3Merge-Sort(A, low, mid)4Merge-Sort(A, mid+1, high)5Merge(A, low, mid, high)11-111-2Lecture 11: November 20.

proof by cases/enumeration proof by chain of i s proof by contradiction proof by contrapositive For any algorithm, we must prove that it always returns the desired output for all legal instances of the problem. For sorting, this means even if the input is already sorted or it contains repeated elements. Proof by Counterexample

  Proof, Proving, Correctness

Download Proving Algorithm Correctness


Information

Domain:

Source:

Link to this page:

Please notify us if you found a problem with this document:

Spam in document Broken preview Other abuse

Related search queries