Proving termination and correctness of the algorithm

[Bipolarity]

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

 

[verty]

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?

 

[Bipolarity]

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?

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

 

[micromass]

If you want to type LaTeX, please use two hashtags to start and two hashtags to end. For example

##\frac{2}{3}##

I'll clean up your post.

See: https://www.physicsforums.com/showpost.php?p=3977517&postcount=3

 

[micromass]

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

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.

 

[Bacle2]

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

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.

 

[AlephZero]

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!

 

[D H]

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)$.

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).