Notation Confusion

[TheFearful]

I was given a project to do, but I don't understand this notation and am rather confused, so I don't even know where to get started. I am supposed to be using the clock function to see how long it takes for the code below to finish running.

Prefix Averages (Quadratic): The following algorithm computes prefix averages in quadratic time by applying the definition.
Algorithm prefixAverages1(X, n)
Input array X of n integers
Output array A of prefix averages of X
A ← new array of n integers
for i ← 0 to n − 1 do
s ← 0
for j ← 0 to i do
s ← s + X[j]
A[i] ← s / (i + 1)
return A

This is what I have.

#include <iostream>
#include <time.h>
#include <algorithm>

using namespace std;

const int SIZE = 900000;

int prefixAverages(int x[], int n);
int prefixAverages2(int y[], int n);


int main()
{
    clock_t t;

    int x[SIZE];
    int y[SIZE];
    t = clock();

    prefixAverages(x, SIZE);

    return 0;
}

int prefixAverages1(int x[], int n)
{

}

I believe I can do what I am asked to do, but have no idea what that notation means.

[Ancient Dragon]

What are you confused about?

for i ← 0 to n − 1 do

In c++ this would be for(i = 0; i < n-1; ;)

or it could be coded as a do loop

int i = 0;
do {
  // something
} while( i < n-1);

[sepp2k]

Can you clarify what exactly you don't understand? The arrow means assignment, for i <- x to y means a for loop that iterates i from x to y and everything else seems to be the same as in C (i.e. / is division, [] is array access etc.).

One thing I see wrong with your signature is that the pseudo code said that the "output" (i.e. the return value) should be an array, but you declared the function as returning an int.

[TheFearful]

I am confused with the input/output part
Input array X of n integers
Output array A of prefix averages of X

so would it be something like

int x[n];
int A[whatever the prefix values of x is?]

?

[TheFearful]

int main()
{
    float t;

    int x[SIZE];

    t = clock();

    int *A = prefixAverages(x, SIZE);
    t = clock() - t;
    //cout << "It took me " << t << "clicks (" << t/CLOCKS_PER_SEC << " seconds)." << endl;

return 0;
}

int *prefixAverages(int x[], int n)
{
    int A[SIZE];
    int s;
    for(int i = 0; i < n; i++)
    {
        s = 0;
        for(int j = 0; j <= i; i++)
        {
            s = s + x[j];
        }
        A[i] = s / (i+1);
    }
    return A;
}

And then the program crashes when I run it.

[Schol-R-LEA]

Has the instructor covered dynamic memory allocation (new and delete) yet?

[TheFearful]

I have learned a little bit about it over the winter break. Would I have to malloc it then?

[Schol-R-LEA]

I would recommend using the new operator rather than the C-style memory allocation, but that is what it sounds like you're expected to use, yes.

From the sounds of it, the intention is for you to create the first array in main() (or whatever function you are calling prefixAverages() from), then pass it to prefixAverages() as an argument along with the size of the array. You would then use new to allocate the second array.

int *A = new int[n];

Then, after filling A with the computed values, you would return it as an int pointer.

 int* y = prefixAverages(x, SIZE);

Oh, but don't forget to use delete before the end of the program to free the allocated array:

delete[] y;

EDIT: I forgot the square brackets on the delete.

[TheFearful]

int *prefixAverages(int x[], int n)
{
    int *A = new int[n];
    int s;
    for(int i = 0; i < n; i++)
    {
        s = 0;
        for(int j = 0; j <= i; i++)
        {
            s = s + x[j];
        }
        A[i] = s / (i+1);
    }
    return A;
}

That is the change I made. There is no syntax error, but there is a run-time error I believe.

Also did

int *y = prefixAverages(x, SIZE);

    delete[] y;

in my main function.

Edit:I am having a Stack Overflow.

[Schol-R-LEA]

in the inner loop, you are incrementing i instead of j. This leads to you walking off of the end of the array A, but I would expect it to give a segfault, not a stack overflow. How odd.

[TheFearful]

I fixed it! I messed up in my second for loop. I had i++ instead of j++
Thank you for the help!

The stack overflow was from my const int being too large.

[Schol-R-LEA]

Wait, I apologize, I would expect it to make an infinite loop, as it would never even get to A[]. A stack overflow is still surprising to me, though.

EDIT: Oh, right, it is overflowing into a 64-bit value. Makes sense now.