Win a copy of The Java Performance Companion this week in the Performance forum!
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

Need some help!!

 
juan cuesta
Greenhorn
Posts: 3
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Saloon Keeper
Posts: 15359
39
Android IntelliJ IDE Java Scala Spring
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Sheriff
Pie
Posts: 49402
62
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
By the way, which language is that? It looks rather like BASIC which I learnt 40 years ago.
 
Matthew Brown
Bartender
Posts: 4567
8
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic