6 replies to this topic

[owh786]

Hello, i am a university student, i have just begun my second year in computer science. I need some help on Prefix Averages and the following questions (I would ask the teaching assistants, but they don't explain properly and I need something that I am able to read up on later):

Given an array X storing n numbers, we want to compute an array A such that A is the average of elements X[0], X[1], … , X, for i=0,1, …, n-1.

For example imagine that we have a ten element array X = [7, 3, -1, 2, 9 ,0, 0.8, 52, 2.2, 900].

Then the array A would be computed as follows according to table 4.1:

Array A |Contents of A | Value|
A[0] (X[0])/1 |7.000
A[1] (X[0]+X[1])/2 | 5.000
A[2] (X[0]+X[1]+X[2])/3 |3.000
A[3] (X[0]+X[1]+X[2]+X[3])/4 | 2.750
A[4] (X[0]+X[1]+X[2]+X[3]+X[4])/5 | 4.000
A[5] (X[0]+X[1]+X[2]+X[3]+X[4]+X[5])/6 | 3.333
A[6] (X[0]+X[1]+X[2]+X[3]+X[4]+X[5]+X[6])/7 | 2.971
A[7] (X[0]+X[1]+X[2]+X[3]+X[4]+X[5]+X[6]+X[7])/8 |[I]9.100
A[8] (X[0]+X[1]+X[2]+X[3]+X[4]+X[5]+X[6]+X[7]+X[8])/9 | [I]8.333
A[9] (X[0]+X[1]+X[2]+X[3]+X[4]+X[5]+X[6]+X[7]+X[8]+X[9])/10 |[I]97.500
Table 4.1: Prefix Average Example


Let us analyse two algorithms that solve this problem:

Algorithm 4.1. PrefixAverages1(X)
Input: X- a 1-D numerical array of size n
1) Let A = an empty 1-D numerical array of size n
2) For i = 0 to n-1
3) Let s = X[0]
4) For j = 1 to i
5) Let s = s + X[j]
6) End For
7) Let A[i] = s /(i+1)
8) End For
Output: An n-element array A of numbers such that A[i]
is the average of elements X[0],X[1], … ,X[i]

Algorithm 4.2. PrefixAverages2(X)
Input: X- a 1-D numerical array of size n
1) Let A = an empty 1-D numerical array of size n
2) Let s = 0
3) For i = 0 to n-1
4) Let s = s + X[i]
5) Let A[i] = s / (i+1)
6) End For
Output: An n-element array A of numbers such that A[i]
is the average of elements X[0],X[1], … ,X[i]


1) What is the difference between the two algorithms? Read these two algorithms carefully. If necessary, it might be helpful to set up an array yourself and apply these two algorithms on it by running through them by hand for small size values of n.

2) Analyse both algorithms by counting primitive operations and derive T(n) for both algorithms. What is the time complexity (Big-Oh, O(n)) of each algorithm? Which one is the most efficient?


Please help!!!

Edited by owh786, 19 October 2011 - 06:20 AM.

[WingedPanther]

Standard question: what do you have so far?

[owh786]

so far I don't understand what a prefix average is :confused:

[WingedPanther]

a[i] is the average of x[0] through x[i]. The a[i] is a prefix average.

[owh786]

ok, i now understand what the prefix average is. thank you.
what does D mean in this, and also why is there a smaller case "a" for?:

Algorithm 4.1. PrefixAverages1(X)
Input: X- a 1-D numerical array of size n
1) Let A = an empty 1-D numerical array of size n

[lethalwire]

D = Dimensional
1-D = 1-Dimensional
2-D = 2-Dimensional
3-D = 3-Dimensional
...
etc.

Smaller case for "a":
It's just part of the statement. "a 1-D numerical array of size n", a bright green 1-D balloon.

A is of course, the 1-D array of size n.

[owh786]

Algorithm 4.1. PrefixAverages1(X)
Input: X- a 1-D numerical array of size n
1) Let A = an empty 1-D numerical array of size n
2) For i = 0 to n-1
3) Let s = X[0]
4) For j = 1 to i
5) Let s = s + X[j]
6) End For
7) Let A[i] = s /(i+1)
8) End For
Output: An n-element array A of numbers such that A[i]
is the average of elements X[0],X[1], … ,X[i]

Why is there another For loop added (the one in bold and italics)?