Unable to implement pseudocode

Question

I came across a pseudocode which I am unable to implement because, I am unable to understand it:

i, c := 0,0;
do i ≠ n →
    if v = b[i]           → c, i := c + 2, i + 1
       c = i               → c, i, v := c + 2, i + 1, b[i]
       c ≠ i ^ v ≠ b[i]    → i := i + 1
    fi
od

I think that tis pseudocode is about finding the value v which has occurred more than n / 2 times in b[].

What exactly you cannot understand? The notation of pseudo code or why does it work correctly? — SPIRiT_1984
– SPIRiT_1984, Commented Jun 19, 2012 at 6:15
What are you trying to implement ! What does this pseudo code supposed to be doing("sorts number", " kills racoons" ? — Jay D
– Jay D, Commented Jun 19, 2012 at 6:18
@JayD I have already mentioned in the question what does the pseudo code do. It is related to finding the value v which have occured more than n/2 times in an array b[n] — Snehasish
– Snehasish, Commented Jun 19, 2012 at 6:22

Daniel Fischer · Accepted Answer · 2012-06-19 08:29:31Z

3

The three conditions in the if are alternatives, they should be translated to an if-else if-else chain. The assignment-like statements c,i,v := c+2, i+1, b[i] are multiple assignments, as far as I know like the Python multiple assignments, so the i in b[i] refers to the old value of i. That yields

// n and v are initialised to something sensible, hopefully
i = 0;
c = 0;
while(i != n) {
    if (b[i] == v) {
        c = c + 2;
        i = i + 1;
    } else if (c == i) {
        c = c + 2;
        v = b[i];  // conjecture that the b[i] on the RHS refers to the old i
        i = i + 1;
    } else {
        i = i + 1;
    }
}

Since i is incremented in every branch, we can lift that out, and get

for(i = 0, c = 0; i != n; ++i) {
    if (b[i] == v) {
        c += 2;
    } else if (c == i) {
        c += 2;
        v = b[i];
    }
}

answered Jun 19, 2012 at 8:29

Daniel Fischer

184k19 gold badges319 silver badges436 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Snehasish Over a year ago

But what have you done with the condition : c ≠ i ^ v ≠ b[i] You have neglected it completely !!

Daniel Fischer Over a year ago

That condition is a consequence of the two others being false. It translates to c != i && v != b[i], which is exactly the case if neither of the two first conditions is true, so in the first loop, it's the final else, in the second loop, it need not appear because in that case the only thing that is done is incrementing i which happens in all cases.

Michael · Accepted Answer · 2012-06-19 07:02:27Z

0

Whoa, this isn't what I expected to ever see. It looks like Dijkstra's do-od notation (not sure what's a good reference, maybe this: http://www.cs.grinnell.edu/~stone/courses/compilers/introduction-to-Dijkstra.pdf).

Roughly what this is doing is a series of guarded checks. If some condition holds, then do the implication. As for implementing something in do-od notation, I'm not too sure. Something along the lines of:

i = c = 0;
while (i != n) {
    if (v == b[i]) {
        c = c+2, i = i+1;
        if (c == i) c = c+2, i = i + 1, v = b[i];
        if (c != i || v != b[i]) i = i + 1
    }
}

No idea what those intermediate variables are, and I've always conceptualized do-od programs as something closer to hardware (with everything running and testing in parallel). Good luck

answered Jun 19, 2012 at 7:02

Michael

2,29115 silver badges14 bronze badges

2 Comments

Michael Over a year ago

I have no idea what n, v, or b should be set as before starting...See if figuring out the do-od notation helps at all.

Jim Balter Over a year ago

Those assignments are supposed to happen concurrently, so you're using the wrong i to index b[i] in the c == i case. Also, the if has three independent guards, so the v == b[i] test should just be one of a three-way branch.

Collectives™ on Stack Overflow

Unable to implement pseudocode

2 Answers 2

2 Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related