Pseudocode/Java Mystery Algorithm

I have an algorithm, and I want to figure it what it does. I'm sure some of you can just look at this and tell me what it does, but I've been looking at it for half an hour and I'm still not sure. It just gets messy when I try to play with it. What are your techniques for breaking down an algoritm like this? How do I analyze stuff like this and know whats going on?

My guess is its sorting the numbers from smallest to biggest, but I'm not too sure.

1. mystery(a1 , a2 , . . . an : array of real numbers)
    2. k = 1
    3. bk = a1
    4. for i = 2 to n
        5. c = 0
        6. for j = 1 to i − 1
            7. c = aj + c
        8. if (ai ≥ c)
            9. k = k + 1
           10. bk = ai
    11. return b1 , b2 , . . . , bk

Here's an equivalent I tried to write in Java, but I'm n开发者_如何转开发ot sure if I translated properly:

public int[] foo(int[] a) {
        int k=1;
        int nSize=10;
        int[] b=new int[nSize];
        b[k]=a[1];
        for (int i=2;i<a.length;){
            int c=0;
            for (int j=1;j<i-1;)
                c=a[j]+c;
            if (a[i]>=c){
                k=k+1;
                b[k]=a[i];

---

Google never ceases to amaze, due on the 29th I take it? ;)

A Java translation is a good idea, once operational you'll be able to step through it to see exactly what the algorithm does if you're having problems visualizing it.

A few pointers: the psuedo code has arrays indexed 1 through n, Java's arrays are indexed 0 through length - 1. Your loops need to be modified to suit this. Also you've left the increments off your loops - i++, j++.

Making b magic constant sized isn't a good idea either - looking at the pseudo code we can see it's written to at most n - 1 times, so that would be a good starting point for its size. You can resize it to fit at the end.

Final tip, the algorithm's O(n²) timed. This is easy to determine - outer for loop runs n times, inner for loop n / 2 times, for total running time of (n * (n / 2)). The n * n dominates, which is what Big O is concerned with, making this an O(n²) algorithm.

---

The easiest way is to take a sample but small set of numbers and work it on paper. In your case let's take number a[] = {3,6,1,19,2}. Now we need to step through your algorithm:

Initialization:

i = 2
b[1] = 3

After Iteration 1:

i = 3
b[2] = 6

After Iteration 2:

i = 4
b[2] = 6

After Iteration 3:

i = 5
b[3] = 19

After Iteration 4:

i = 6
b[3] = 19

Result b[] = {3,6,19}

You probably can guess what it is doing.

---

Your code is pretty close to the pseudo code, but these are a few errors:

• Your for loops are missing the increment rules: i++, j++
• Java arrays are 0 based, not 1 based, so you should initialize k=0, a[0], i=1, e.t.c.

Also, this isn't sorting, more of a filtering - you get some of the elements, but in the same order.

---

How do I analyze stuff like this and know whats going on?

The basic technique for something like this is to hand execute it with a pencil and paper.

A more advanced technique is to decompose the code into parts, figure out what the parts do and then mentally reassemble it. (The trick is picking the boundaries for decomposing. That takes practice.)

Once you get better at it, you will start to be able to "read" the pseudo-code ... though this example is probably a bit too gnarly for most coders to handle like that.

---

When converting to java, be careful with array indexes, as this pseudocode seems to imply a 1-based index.

From static analysis:

• a is the input and doesn't change
• b is the output
• k appears to be a pointer to an element of b, that will only increment in certain circumstances (so we can think of k = k+1 as meaning "the next time we write to b, we're going to write to the next element")
• what does the loop in lines 6-7 accomplish? So what's the value of c?
• using the previous answer then, when is line 8 true?
• since lines 9-10 are only executed when line 8 is true, what does that say about the elements in the output?

Then you can start to sanity check your answer:

• will all the elements of the output be set?
• try running through the psuedocode with an input like [1,2,3,4] -- what would you expect the output to be?

---

def funct(*a)
  sum = 0
  a.select {|el| (el >= sum).tap { sum += el }}
end

Srsly? Who invents those homework questions?

By the way: since this is doing both a scan and a filter at the same time, and the filter depends on the scan, which language has the necessary features to express this succinctly in such a way that the sequence is only traversed once?