juan cuesta

Greenhorn

Posts: 3

posted 6 years ago

HI people, Im student of sotware development, Im triying to solve this excersise and im stack , i hope someone can help me! thank you ;)

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]

Exercise 1: Computational Complexity

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?

Exercise 2: Implementation

Implement the two algorithms in Java and perform a thorough experimental analysis of their running times. Plot their running times as a function of their input size as scatter plots. Choose representative values of the size n, and run at least 5 tests for each size value n in your tests.

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]

Exercise 1: Computational Complexity

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?

Exercise 2: Implementation

Implement the two algorithms in Java and perform a thorough experimental analysis of their running times. Plot their running times as a function of their input size as scatter plots. Choose representative values of the size n, and run at least 5 tests for each size value n in your tests.

posted 6 years ago

Hello Juan, and welcome to the Ranch!

Can you please explain how far you got with these exercises and where you got stuck? We're happy to help you here, but we're not going to do all of your homework for you. If you've started writing some code and it doesn't work like you expected, or you get an error, then please post your code and explain exactly what it does and how that differs from what you expected, or what the error exactly is.

Can you please explain how far you got with these exercises and where you got stuck? We're happy to help you here, but we're not going to do all of your homework for you. If you've started writing some code and it doesn't work like you expected, or you get an error, then please post your code and explain exactly what it does and how that differs from what you expected, or what the error exactly is.

Campbell Ritchie

Marshal

Posts: 56553

172

Matthew Brown

Bartender

Posts: 4568

9

posted 6 years ago

I'd guess it's meant to be a pseudo-language - it's just to illustrate the algorithm, not to be actually runnable.

Have you gone through it by hand for some small numbers, as the question advises you to do? That would be the best starting point, to make sure you actually understand what it's doing.

Have you gone through it by hand for some small numbers, as the question advises you to do? That would be the best starting point, to make sure you actually understand what it's doing.