Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Proving termination and correctness of the algorithm

  1. Jul 14, 2013 #1
    I've been trying to prove the following, without much success.
    Let ##B## and ##C## be nonempty finite subsets of an ordered field ##\mathbb{F}##. Define the swapping operation ##S## as follows:
    It takes an element ##b## from ##B##, an element ##c## from ##C##, removes ##b## from ##B## and gives it to ##C##, removes ##c## from ##C## and gives it to ##B##.


    Now suppose that ##\max(B) \geq \min(C)##. Then prove that in a finite number of operations of S, the sets ##B## and ##C## can be transformed so that ##\max(B) < \min(C)##.

    Where would I start? I'm thinking by we can use induction/loop invariants, but I don't have much experience in algorithm proofs, so I could use some help. Thanks!

    BiP
     
    Last edited by a moderator: Jul 14, 2013
  2. jcsd
  3. Jul 14, 2013 #2

    verty

    User Avatar
    Homework Helper

    I can think of 3 ways to prove this. The invariant idea is probably what your teacher/the author wants. Try to find a way to measure how far you are from the final state. That is, given B and C, can you estimate how many swap operations are required?
     
  4. Jul 14, 2013 #3
    I actually made the problem myself. It is part of a larger project in which I have been trying to rigorously prove correctness of Gauss-Jordan elimination. The algorithm I described above is needed to make sure a finite number of row interchange operations exist on a matrix so that all nonzero rows precede the zero rows.

    I'm clueless as to how you would do this proof. Like I said, I don't have much experience in algorithms let alone proving their correctness. Perhaps you could recommend me a text, or help me work through this problem?

    Which 3 ways are you referring to?

    Thanks by the way.

    BiP
     
  5. Jul 14, 2013 #4

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

  6. Jul 14, 2013 #5

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    First of all, the field hypothesis is unnecessary. It works for any totally ordered set.

    Try an induction proof:
    Let ##B## have ##n## elements and ##C## have ##m## elements.

    1) Can you prove this in the case that ##B## has ##1## element?
    2) Assume that it works for any ##B## with ##n^\prime<n## elements. Prove that it works for ##n##. Hint: take the element ##\max(B)##. Look at the set ##B^\prime = \{\max(B)\}##. Apply (1) to get this element smaller than ##\min(C)##. Then take ##B^{\prime\prime}## the set of all elements bigger than ##\min(C)##. This has ##<n## elements.
     
  7. Jul 14, 2013 #6

    Bacle2

    User Avatar
    Science Advisor

    Do you keep track of the elements that have been swapped? Owise, how do you prevent an infinite loop; say you have (assume restricition of standard ordering on naturals):

    C={1,3,4,8}

    B={2,5,6}

    S: 4<->6

    Then

    C'={1,3,6,8}

    B'={2,4,5}

    What prevents you from swapping 4 and 6 again (strictly-speaking, 6<->4 )...and again.....

    Why don't you try to write a small program .

    You may have to index the terms of C,B, so that you have finite sequences, instead of sets.
     
  8. Jul 15, 2013 #7

    AlephZero

    User Avatar
    Science Advisor
    Homework Helper

    Label the elements of both sets ##e_1, e_2, \dots e_k## where ##e_1 \le e_2 \le \dots \le e_k## (independent of which set they are in).

    For ##p = 1, 2, \dots## up to the number of elements in ##C##:

    If ##e_p## is not in ##C##, swap ##e_p## from ##B## with any element ##e_q## of ##C## such that ##q > p##.

    Done!
     
  9. Jul 15, 2013 #8

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    I think you meant max(B)≤min(C), not max(B)<min(C). Consider the sets B={0}, C={0}. This satisfies the condition that max(B)≥min(C). Swap all you want and you will never be able to transform the sets such that max(B)<min(C).
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Proving termination and correctness of the algorithm
  1. Euclidean algorithm (Replies: 2)

  2. Terminal objects (Replies: 8)

  3. EM algorithm (Replies: 0)

  4. Randomized Algorithms (Replies: 2)

Loading...