Proving Algorithm Correctness - Northeastern University

1 CS 5002: Discrete StructuresFall 2018 Lecture 11: November 20, 20181 Instructors: 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)/2c3 Merge-Sort(A, low, mid)4 Merge-Sort(A, mid+1, high)5 Merge(A, low, mid, high)11-111-2 Lecture 11: November 20, 2018 Merge(A, low, mid, high)1 L = A[low:mid]//(L is a new array copied from A[low:mid])2 R = A[mid+1, high]//(R is a new array copied from A[mid+1:high])3i= 14j= 15fork=lowtohigh6ifL[i]<R[j]:7A[k] = L[i]8i=i+ 19else10A[k] = R[j]11j=j+ Mergesort AnalysisMergesort: AnalysisWe do 2 things in our analysis: What s the runtime?

2 Is it correct?Mergesort: What s the runtime?Recall the runtime of Mergesort:T(n) ={ (1)ifn 12T(n2) + (n) otherwiseExample: Recursion TreeT(n) = 2T(n/2) +nn(n2)T(n4)..T(1)..T(1)T(n4)..T(1)..T(1 )(n2)T(n4)..T(1)..T(1)T(n4)..T(1)..T(1)4 (n4)=n(n2) + (n2) =nnlgnMergesort: Runtime SummaryTODO: put a summary hereLecture 11: November 20, proof TechniquesProving CorrectnessHow to prove that an Algorithm is correct? proof by: counterexample (indirect proof ) Induction (direct proof ) Loop InvariantOther approaches: proof by cases/enumeration proof by chain of iffs proof by contradiction proof by contrapositiveFor any Algorithm , we must prove that it always returns the desired output for all legalinstances of the sorting, this means even if the input is already sorted or it containsrepeated by CounterexampleSearching for counterexamples is the best way to disprove the Correctness of some things.}

3 Identify a case for which something is NOT true If the proof seems hard or tricky, sometimes a counterexample works Sometimes a counterexample is just easy to see, and can shortcut a proof If a counterexample is hard to find, a proof might be easierProof by InductionFailure to find a counterexample to a given Algorithm does not mean it is obvious that the Algorithm induction is a very useful method for Proving the Correctness of recursive Prove base case2. Assume true for arbitrary valuen3. Prove true for casen+ 1 proof by Loop Invariant Built off proof by induction. Useful for algorithms that : find loop invariant, then prove:1. Define a Loop Invariant2. Initialization3. Maintenance4. TerminationInformally:1.

4 Findp, a loop invariant11-4 Lecture 11: November 20, 20182. Show the base case forp3. Use induction to show the proof by CounterexampleDefinition ( proof by counterexample )Used to prove statements false, or algorithms either in-correct or non-optimalExamples: counterexample Prove or disprove:dx+ye=dxe+dye. proof by counterexample :x=12andy=12 Prove or disprove: Every positive integer is the sum of two squares of integers proof by counterexample : 3 Prove or disprove: x y(xy x) (over all integers) proof by counterexample :x= 1, y= 3;xy= 3; 36 1 Greedy AlgorithmsDefinition (Greedy Algorithm )An Algorithm that selects the best choice at each step, instead ofconsidering all sequences of steps that may lead to an optimal solution.

5 It s usually straight-forward to find a greedy Algorithm that isfeasible, but hard to find a greedyalgorithm that isoptimal Either prove the solution optimal, or find a counterexample such that the Algorithm yields a non-optimal solution An Algorithm can be greedy even if it doesn t produce an optimal solutionExample: Interval SchedulingInterval scheduling is a classic algorithmic problem. In this example, we ll show how we can define a greedyalgorithm to solve the problem, and use counterexamples to show a reasonable approach to solving theproblem produces a sub-optimal Problem:We have a resourcer, such as a classroom, and a bunch of requestsq:{start, f inish}.

6 Howcan we schedule the requests to use the resource? We want to identify a setSof requests such that no requests overlap. Ideally, theSthat we find contains the maximum number of the diagram below, we see three sets of set of requests is the preferred choice for the interval scheduling problem as defined?timeS1S2S3 For these three sets of requests,S2is the set we would consider optimal, because it satisfies the greatestnumber of of solution:A simple heuristic that is an example of agreedy Scheduling: Simple Greedy AlgorithmLecture 11: November 20, 201811-5 Input:ArrayAof requestsq:{start, f inish}such that (q1={s1, f1}, q2={s2, f2}, .. qn={sn, fn})Output:S is the set of talks scheduledSchedule(A):1 Sort talks by start time; reorder so thats1 s2.

7 Sn2S= 3forj= 1 ton:4ifqjis compatible withS:5//The current request doesn t conflict with any others we ve chosen6S=S qj//Add it to the set of scheduled7returnSIn this Algorithm , the in Line 4, compatible withS means thatqjdoes not overlap any of the requestsalready , this Algorithm is written by specifying to putqjinS, then remove all requests Scheduling: VisuallyBelow is a diagram that represents the a set of requests to be scheduled. This time, ALL requests are in oneset, and we are attempting to create an optimal schedule of these schedule chosen by our Algorithm so far is shown in question is: is this an optimal solution? Remember, we said the optimal schedule will satisfy the inspection, I can see that we can choose a different set of requests that do not overlap, and that havemore requests I observe this counterexample , I notice that if I were to order the requests in terms offinishtime,I will be able to schedule more requests.

8 Upon reflection, this makes sense: By choosing the request thatSTARTS first, we may choose a very long request that prevents many other requests from being , choosing the request that finishes first leaves more time after that event to schedule more Scheduling: Correct Greedy AlgorithmJust for reference, here s the correct greedy Algorithm . The only difference is that we order the talks byfinish time rather than start :ArrayAof requestsq:{start, f inish}such that (q1={s1, f1}, q2={s2, f2}, .. qn={sn, fn})Output:S is the set of talks scheduled11-6 Lecture 11: November 20, 2018 Schedule(A):1 Sort talks by finish time; reorder so thatf1 f2 .. fn2S= 3forj= 1 ton:4ifqjis compatible withS:5//The current request doesn t conflict with any others we ve chosen6S=S qj//Add it to the set of scheduled7returnSInterval Scheduling: Proving the simple wrong Greedy algorithms are easy to design, but hard to prove correct Usually, a counterexample is the best way to do this Interval scheduling provided an example where it was easy to come up with a simple greedy Algorithm .

9 However, we were able to show the algorithmnon-optimalby using a counterexample . This also depended on our definition ofoptimal. Had we chosen a different definition of optimal(say, utilizing the room the greatest percentage of time), this Algorithm may not provide anoptimal by CounterexampleSearching for counterexamples is the best way to disprove the Correctness of some for finding counterexamples: Think about small examples Think about examples on or around your decision points Think about extreme examples (big or small) Summary: Counterexamples Sometimes it s easy to provide a counterexample It s usually enough to provide a counterexample to prove something wrong or False In algorithms, particularly useful for Proving heuristics or greedy algorithms wrong or proof by InductionThis semester, we ve used the following identity many times:n i=1i=n(n+ 1)2I waved my hands and said Right now, we ll just use it as a given.

10 We ll worry about how it s derivedlater . Well, the time has now, we know that it certainly works for some numbers, based on our experience:Lecture 11: November 20, 201811-7 Casen= 1 :1 i=1i=1(1 + 1)2 1 = 1 Casen= 5 :5 i=1i=5(5 + 1)2= 1 + 2 + 3 + 4 + 5 = 15 15 15 Casen= 30 :30 i=1i=30(30 + 1)2 465 = 465 Check my math on your own!But, just because we proved this true for a couple of instances doesn t mean we ve proved it is true for alln! Mathematical InductionDefinition (Mathematical Induction)1. Prove the formula for the smallest number that canbe used in the given Assume it s true for an arbitrary Use the previous steps to prove that it s true for the next numbern+ simple example:Theorem:For all pricesp 8 cents, the pricepcan be paid using only 5-cent and 3-cent coinsStep 1: Proving true for smallest number Show the theorem holds for pricep= 8 2:Assume true for arbitraryn Assume that theorem is true for somep 3:Show true forn+ 1 Show the theorem is true for pricep+ step: Assume pricep 8 can be paid using only 3-cent and 5-cent coins.