programming forums Java Java JSRs Mobile Certification Databases Caching Books Engineering OS Languages Paradigms IDEs Build Tools Frameworks Products This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
Sheriffs:
Saloon Keepers:
Bartenders:

# Need some help!!

juan cuesta
Greenhorn
Posts: 3
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.

Jesper de Jong
Java Cowboy
Sheriff
Posts: 16060
88
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.

Campbell Ritchie
Marshal
Posts: 56553
172
By the way, which language is that? It looks rather like BASIC which I learnt 40 years ago.

Matthew Brown
Bartender
Posts: 4568
9
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.