Proving That an Algorithm Works Correctly, Explained

UPI Study › Courses › Data Structures and Algorithms › Free lessons › Lesson 7.6 Free with a free account

Proving That an Algorithm Works Correctly

Data Structures and Algorithms · Chapter 7: Measuring Algorithm EfficiencySection 7.6 · lesson 30 of 8710 min · free with a free account

← Growth Categories and Asymptotic BoundsNext lesson: When to Call Itself vs. When a Loop Does Better →

Earn 3 college credits for Data Structures and AlgorithmsRecommended for credit by NCCRS · Computer Science 251 · self-paced · one payment, lifetime access
Enroll in Data Structures and Algorithms · $250 →Download the syllabus (PDF)

In this lesson

Prove loops correct with invariants, induction, contradiction, and variants.

  • State a method's precondition and postcondition precisely
  • Prove a loop correct with an invariant's initialization, maintenance, and termination
  • Choose between a counterexample, induction, and contradiction for a given claim
  • Distinguish partial from total correctness using a loop variant

Free study notes

Get this lesson's notes by email

The key points and 4 practice questions with answers, in your inbox. One email, free.

One email. Unsubscribe in one click.

Transcript

Everything said in the video, section by section (1,435 words). Read along, or search it.

Opening Question

A Max Method That Returns Zero

This method should return the largest value in an array. Try it on four, nine, six: it returns nine. On three, eight, one, seven: eight. It passes every test you'd think to write. Now give it minus five, minus two, minus nine. It returns zero, a number that isn't even in the array. How could you have caught that, without a lucky test? By proving the method correct.

Definition

Preconditions and Postconditions

You can't prove a method correct until you say precisely what correct means. A precondition is what must be true when the method starts: the inputs it's designed to accept. A postcondition is what it promises when it ends: the result. Correctness is always a claim about the pair. If the precondition holds at the start, the postcondition holds at the end. Inputs that break the precondition are outside the claim.

Worked Example

Contracts for Sum, Index Of, and Max

For sum, the precondition is that the array isn't null, and it promises the total of every element. For index of, it promises the smallest index holding the target, or minus one if there's none. Find max needs a real precondition: at least one element. An empty array has no largest value, so there's nothing to promise. Choosing that is a design decision, and the proof uses it.

Definition

Loop Invariants and Three Obligations

A loop may run thousands of times, so we can't check each pass. Instead, find a statement that stays true on every pass: a loop invariant. It's true each time the loop test is about to run: before the first pass, after every pass, and when the loop exits. Proving it has three obligations. Initialization: it's true before the first test. Maintenance: if it's true before a pass, it's true after. And termination: when the test fails, the invariant plus the failed test give the postcondition.

Worked Example

Proving the Sum Loop Correct

Take sum. The invariant: each time the test runs, s equals a zero plus up to a of i minus one: the elements handled so far. Initialization: i is zero and s is zero, the sum of no elements. Maintenance: the body adds a of i to s, and i goes up by one. So s is again the sum of everything before the new i. Termination: the test fails when i equals the length. So s is the sum of the whole array: the postcondition.

Strategy

How to Find a Useful Invariant

Finding the invariant is usually the hard part. Ask: after the loop has handled some of the elements, what's true about the work so far? Accumulating a total? The total holds the combined value of the elements handled so far. Looking for the best? Best is the best of those elements. Searching? None of them is the target. And a useful invariant isn't just true. I is never negative is an invariant of sum, but it says nothing about s. A good invariant is strong enough to give the postcondition.

Quick Check

Invariant for Counting Negatives

Quick check. A loop walks through an array, and counts how many elements are negative. Which invariant would prove it correct? Count equals the negatives in the first i elements. Count is never more than i. Or i is never more than the length. Pause, and decide. The first. When the test fails, i equals the length, so count is the number of negatives in the whole array: the postcondition. The other two are true, but useless. Neither says anything about which elements were counted.

Counterexamples

One Failing Input Disproves a Claim

Different claims call for different tools. To show a claim is false, one failing input is enough: a counterexample. The claim, the buggy find max returns the largest element of any array, falls to minus five, minus two, minus nine. It returns zero, and the largest element is minus two. But a counterexample can only disprove. A thousand inputs that work prove nothing.

Induction

Proving the Sum Formula by Induction

To show a claim for every whole number n from one up, use induction. The base case shows it for the first value. The inductive step shows: if it holds for k, it holds for k plus one. Each true statement knocks over the next, like dominoes. Claim: one plus two, up to n, equals n times n plus one, over two. Base case: for one, both sides are one. Inductive step: assume it holds for k. Add k plus one to both sides. The right side becomes k plus one, times k plus two, over two: the formula for k plus one.

Connection

Invariants Mirror Induction

Induction and loop invariants are close relatives. Initialization is the base case. Maintenance is the inductive step, with the number of passes playing the role of n. That's why an invariant covers a loop of any length.

Contradiction

Proof by Contradiction for Index Of

To show something can't happen, use contradiction: assume it does, and follow the consequences until something impossible appears. Claim: if index of returns minus one, no element equals the target. Assume the opposite: it returned minus one, yet some element matches. Let j be the first matching index. The loop only moves past indexes whose element differs from the target, so it reaches j. There, the test is true, and the method returns j. It can't return both minus one and j. So the assumption was wrong, and the claim is true.

Comparison

Choosing the Right Proof Tool

So: a counterexample shows a claim is false, but can't prove one true. Induction proves a claim for every n, or every pass; don't forget the base case. And contradiction shows something can't happen. The impossibility must be genuine, not just surprising.

Worked Example

Proving the Corrected Find Max

Now find max, corrected. Max starts at a zero, and the loop starts at one. The invariant: max is the largest of a zero up to a of i minus one. Initialization uses the precondition. A zero exists only because the array isn't empty, and it's the largest of the one element seen. Maintenance: if a of i is bigger, max becomes a of i. Otherwise max is already at least a of i. Either way, max is the largest so far. Termination: at the end, it's the largest of the whole array. Now try the buggy version. With max equal to zero, the invariant is false at initialization, since zero may not be an element. The proof fails exactly where the bug lives.

Worked Example

Two Exits from Index Of

Index of can leave its loop two ways, so its termination step has two cases. The invariant: none of the elements before i equals the target. If it returns i, nothing before i matched, and a of i does: i is the first match. If the test fails, i is the length, nothing matched, and minus one is right.

Termination

Variants Prove the Loop Stops

Look at every termination step: it starts from, when the test fails. That quietly assumes the loop stops. The invariant never shows it. An invariant gives partial correctness: if the method stops, the result is right. Total correctness also needs the loop to stop. For that, find a variant: a whole number that's never negative and shrinks on every pass. For these loops it's the length minus i: five, four, three, two, one, zero. Now a countdown by twos, looping while x isn't zero. From six: six, four, two, zero, done. From five: five, three, one, minus one, and on. It steps over zero, never stopping.

Common Mistake

Partial Versus Total Correctness

Here, x is odd is a perfectly valid invariant for an input of five, yet the loop never stops. So the method is partially correct, but not totally correct. The fix: a stronger precondition, x is a non-negative even number, or a safer test, x greater than zero. Write both parts of an argument: the invariant for the answer, and the variant for the stopping.

Quick Check

Integer Division Breaks the Mean

Quick check. This method should return the exact mean of any non-empty array of whole numbers. Which input is a counterexample: two and four, one and two, or just five? Pause, and decide. One and two. The sum is three and the length two, so the mean is one point five. But s over the length divides two ints, so the method returns one point oh. Two and four averages to exactly three, and five to five, so they pass. One failing input refutes the claim. Dividing by a double fixes it.

Key Takeaways

Correctness Proof Essentials

To sum up. Testing covers the inputs you tried. A proof covers every input the precondition allows. A loop invariant needs initialization, maintenance and termination, and it must be strong enough to give the postcondition. Counterexamples disprove, induction proves for every n, and contradiction rules out the impossible. And a variant shows the loop stops.

Think About It

Five Hundred Random Tests

Something to think about. A friend tested a method on five hundred random arrays, and it never failed, so they call it correct. What kind of input might random arrays rarely produce? And what does a proof give you that the tests don't?

About Data Structures and Algorithms at UPI Study

Data Structures and Algorithms (Computer Science 251) is a self-paced online course of 87 video lessons in 17 chapters, from Java and object-oriented design to arrays, linked lists, recursion, stacks and queues, trees, heaps, hash tables, sorting and graphs. It carries a NCCRS credit recommendation for 3 semester credits.

Every lesson transcript is free on pages like this one, and the videos are free with a free UPI Study account. Enrolling adds a practice quiz after each lesson, the graded work and final exam that earn the credit, lifetime access, and an official transcript on completion. UPI Study has helped over 130,000 students with college credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Enroll now → Course details Download the syllabus All Computer Science courses Every course with PRO →

Compare: Discrete Math vs Data Structures and Algorithms · Intro to Java vs Data Structures and Algorithms

Why take it here

Why students take Data Structures and Algorithms with UPI Study

How programs store and search dataData Structures and Algorithms teaches how to organize data and measure how fast code runs: arrays, linked lists, stacks, queues, trees, heaps, hash tables, sorting and graphs, all written in Java. It is a core course in computer science and software degrees.
Credit at a fraction of the priceThe same 3 credits can cost $750 or more at a US college. Here it is one payment, self-paced, with lifetime access.
Finish your degree soonerTransfer credits reduce the courses you still owe, so you can graduate earlier or lighten a heavy semester.
Strengthen an applicationA completed college-level course on an official transcript shows admissions and scholarship committees you can do the work.
Study on your own scheduleNo start dates, no deadlines. Watch the lessons, practice, and take the final when you are ready.
130,000+students helped with college creditsACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Where the credit goes

Universities that work with NCCRS

Data Structures and Algorithms carries a NCCRS credit recommendation. These universities work with NCCRS; some are UPI Study's signed partners. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Thomas Edison State UniversityThomas Edison State UniversitySigned partnerUniversity of the PeopleUniversity of the PeopleSigned partnerCharter Oak State CollegeCharter Oak State CollegeSigned partnerStrayer UniversityStrayer UniversitySigned partnerColumbia Southern UniversityColumbia Southern UniversitySigned partnerIndiana TechIndiana TechSigned partnerPenn StatePenn StateWorks with NCCRSSouthern New Hampshire UniversitySouthern New Hampshire UniversityWorks with NCCRSSUNYSUNYWorks with NCCRS +many more cooperating universitiesFind my college →

Find my college → Not listed? Ask Athena in the corner of this page, or book a 15-minute call.

FAQ

Questions students ask us

About Proving That an Algorithm Works Correctly

What is a loop invariant?
A loop invariant is a statement that is true each time the loop test is about to run: before the first pass, after every pass, and when the loop exits. Proving one has three parts: initialization, maintenance, and termination, where the invariant plus the failed test give the postcondition. For a sum loop, the invariant is that s equals a[0] + ... + a[i-1].
Why does a find max method fail when it starts max at zero?
Starting max at 0 fails for arrays whose values are all negative, because 0 is larger than every element and is not even in the array. For {-5, -2, -9} it returns 0 instead of -2. The fix is to start with max = a[0] and loop from i = 1, which needs the precondition that the array has at least one element. Then the invariant holds from the start.
What is the difference between partial and total correctness?
Partial correctness means that if the method stops, its result is right; total correctness also requires that it stops. A loop invariant proves partial correctness, and a variant, a whole number that is never negative and shrinks on every pass, proves termination. A loop like while (x != 0) x = x - 2; stops when started at 6 but never stops from 5, because x steps over zero.
When should you use a counterexample, induction, or contradiction?
Use a counterexample to show a claim is false, since one failing input is enough, although no number of passing inputs proves a claim true. Use induction to prove a claim for every n: show a base case, then show that if it holds for k, it holds for k + 1. Use contradiction to show something cannot happen, by assuming it does and deriving something impossible.

About the Data Structures and Algorithms course

How many college credits is Data Structures and Algorithms?
Data Structures and Algorithms (Computer Science 251) carries a NCCRS credit recommendation for 3 semester credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.
How much does Data Structures and Algorithms cost and what is included?
$250, paid once, with lifetime access: all 87 video lessons, a practice quiz after each, the graded work and final exam, and an official transcript when you finish. Students who want several courses choose UPI Study PRO instead.
Which universities accept UPI Study credits?
UPI Study has signed partner agreements with universities such as Thomas Edison State University, University of the People and Charter Oak State College, and works with universities such as Penn State, SNHU and SUNY. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities. Use "Find my college" on this page to check yours.
How long does Data Structures and Algorithms take?
It is self-paced with no deadlines. The 87 lessons total about 15 hours of video; most students add reading and practice time and finish in a few weeks to a few months, on their own schedule.
How are the exams done?
Quizzes and assignments are online in the course. The final exam is taken online with proctoring; a person on the UPI Study team checks assignments, usually within two days.
How do my credits reach my college?
When the course shows 100% complete, request the official transcript from your dashboard. It is sent to the college you name, and you can send it to more than one. Check your college first with "Find my college" on this page, or ask Athena.

Ready for the full course? Earn 3 credits in Data Structures and Algorithms.

87 video lessons, a quiz after each one, and the graded work that earns the credit. Recommended for credit by NCCRS.

Enroll in Data Structures and Algorithms →Download the syllabusEvery course with PRO →
Data Structures and Algorithms
3 credits · NCCRSEnroll →