Tag: correctness

Confused by proof of correctness of Majority

I have been studying a streaming algorithm to determine if there is a majority element in a stream. But am confused by a proof for it.

The algorithm works as follows. You keep one counter $ c$ and a store for one item called $ a^*$ . When a new item arrives, first you check if $ c == 0$ . If so you set $ c=1$ and $ a^*$ stores the arriving item. Otherwise, if $ c>0$ and the arriving item is the same as $ a^*$ you increment $ c$ or decrement $ c$ if not.

If there is a majority element then it will be stored in $ a^*$ at the end.

In the notes from http://www.cs.toronto.edu/~bor/2420f17/L11.pdf there is a proof of this fact (called simpler proof).

enter image description here

I can see that if there is a majority item then $ c’$ will be positive at the end of the stream. But:

  • How do we know that $ a^*$ will hold the majority item at the end?
  • Does $ c’$ being positive imply that $ c$ will be positive too?

Negative cycle detection using bellamn ford and its correctness

I recently started studying algorithms on my own using corman and mit algo videos in youtube. I am going thru bellman ford.

enter image description here

I have 2 doubts in correctness of algorithm

1) why are we relaxing (num of vertices – 1) times all the edges. Why not some finite number of times till earlier values and new values remain same.

2) Second for loop(lines 5,6,7 in algo image) is for detecting negative edge cycle. THen i have gone through this correctness. I have seen a theorem that if there is a negative edge cycle reachable from source s then we can find an edge uv such that d(v)>d(u)+w(u,v) [I understood the proof by contradiction(if summing all vertices of negative edge cycle results in sum of all weights along negative cycle positive which means contradiction as it must be negative – page 2 of https://web.stanford.edu/class/archive/cs/cs161/cs161.1168/lecture14.pdf]

But i am not able to visualise such an edge if i have some negative edge cycle from source vertes s. Please help me how such edge exists?

Hoare’s Logic partial/total correctness

So a friend of mine does freelancing and he needed some help with a question about Hoare’s logic. He handed out the problem to me with a pretty narrow deadline. I had no idea what Hoare’s logic is so I looked up some videos on YouTube (channel name: COMP1600 Videos) and got some understanding of the topic. But looking at the question, I really have no idea what to do and where to begin. I have tried some stuff following the rules in the youtube video but I don’t think its any progress. Below is the problem he gave me:

Given the following program,

PV( int x, int y) {          while (true) {                  if (x <= 50)                          y++;                  else                          y--;                  if (y < 0)                          break;          x++;       }          assert(x == 102); }

assume that the precondition is that x ≤ 50 ∧ x ≥ 0 ∧ y ≤ 50 ∧ y ≥ 0 ∧ x = y. Prove that assertion failure never occurs based on Hoare Logic. (a) Prove the partial correctness of the function.

(b) Prove the total correctness by additionally showing that the function is always terminating.

I am completely lost as what to do and where to begin.

Correctness of Simple Programs

For a homework assignment I am asked to provide claim sequences to verify that the given conditional does indeed satisfy its specification (to compute in r the absolute value of x). 

val x: Z = readInt() var r: Z = x  l"""{ 1. r == x               premise }"""  if (x < 0) {   l"""{     1. x < 0              premise     2. r = x              premise     3. r < 0              algebra 1 2   }"""   r = -x   l"""{      1. r = -x                premise      2. x < 0                 premise      3. r_old < 0             premise   }""" } else {   l"""{      //   also in this branch, you must prove all the 3 assertions   }""" } assert(!(x < 0)  | r == -x)   // if x < 0 then r = -x assert(!(x > 0)  | r ==  x)   // if x > 0 then r = x assert(!(x == 0) | r ==  0)   // if x = 0 then r = 0

This is the code we are given to start and are asked to prove the 3 assertions. Im having trouble starting out because I am not sure what structure I need to use. Do I need 3 sub proofs in each conditional in order to prove the three assertions?

annotations for partial correctness

I am reading about hoare login but I don’t really understand the annotations part. This is what I know about annotations:

The inserted annotation is expected to be true whenever the execution reaches the point of the annotation

This function f(x,n) calculates x^n

enter image description here

For the given code, the answers for annotations are the following:

before while:

(K >0) ^ (Y x P^K = X^n)

after while statement:

(K > 0) ^ (Y x P^K = X^n)

I understand the K>0 part but I don’t get why we’re using the second part.

Proving correctness and optimality of a greedy algorithm

Here is a (slightly abridged) problem from Kleinberg and Tardos:

Consider a complete balanced binary tree with $ n$ leaves where $ n$ is a power of two. Each edge $ e$ of the tree has an associated length $ \ell_e$ , which is a positive number. The distance from the root to a given leaf is the sum of the lengths of all the edges on the path from the root to the leaf.

Now, if all leaves do not have the same distance from the root, then the signals we send starting from the root will not reach the leaves at the same time, and this is a big problem. We want the leaves to be completely synchronized, and all to receive the signal at the same time. To make this happen, we will have to increase the lengths of certain edges, so that all root-to-leaf paths have the same length (we’re not able to shrink edge lengths). If we achieve this, then we say the tree has zero skew.

Give an algorithm that increases the lengths of certain edges so that the resulting tree has zero skew and the total edge length is as small as possible.

This problem was in the “Greedy Algorithms” chapter.

I know the solution to this problem is as follows:

Let the subtrees below the root be $ L$ and $ R$ . If the height of $ L$ is greater than $ R$ , then increase the edge length from the root to the right subtree by $ \verb!height(L) – height(R)!$ . Conversely, if the height of $ R$ is greater than the height of $ L$ , then increase the edge length from the root to $ L$ by $ \verb!height(R) – height(L)!$ . We repeat this procedure recursively on $ L$ and $ R$ .

I am having trouble proving the following:

  • $ 1)$ The resulting tree upon termination of this algorithm is a zero-skew tree (the length from the root to any leaf is the same).

  • $ 2)$ The sum of the edge lengths is minimized with this algorithm.

I have tried to prove these facts in many ways, such as induction and direct proof, but I am having a lot of difficulty doing so.

I would greatly appreciate some help in solving this problem.

Can someone verify the correctness of this Candidate-Elimination exercise?

enter image description here

My attempt:

Step 0: GH: {< ?,?,?,? >}, SH: {< ∅,∅,∅,∅ >}

Step 1: GH: {< f,?,?,? >, < ?,t,?,? >, < ?,?,t,? >, < ?,?,?,f >}, SH: {< ∅,∅,∅,∅ >}

Step 2: GH: {< ?,?,t,? >, < ?,?,?,f >}, SH: {< t,f,t,f >}

Step 3: GH: {< ?,?,t,? >, < t,?,?,f >}, SH: {< t,f,t,f >}

Step 4: GH: {< ?,?,t,? >}, SH: {< t,f,t,? >}

Step 5: GH: {< ?,?,t,? >}, SH: {< t,?,t,? >}

The versionspace are exactly those GH and SH of the last step.

How come correctness proofs aren’t tautological?

Consider the following function on binary trees, which is supposed to tell whether a given int is a member of a binary tree t:

type tree = Leaf | Node of int * tree * tree;;  let rec tmember (t:tree) (x:int) : bool =   match t with       Leaf -> false     | Node (j,left,right) -> j = x || tmember left x || tmember right x ;;

If one wants to prove that this function is correct, one would need to define first what tree membership actually means, but then I can find no formal way of doing this except for saying that x is a member of t if and only if it is either equal to the root of t, or it is a member of the left or right subtree of t. This is essentially saying that x is a member of t if and only if tmember t x outputs true.

What am I missing here?