Design an efficient algorithm that achieves the following task: IN JAVA Given a link list of
Question:
Design an efficient algorithm that achieves the following task: IN JAVA
Given a link list of n floating-point numbers, it returns a two-dimensional link list, say M, of size n × n in which the entry M[i][j] for i ≤ j contains the average of the array entries A[i] through A[j].
That is: if i ≤ j, then M[i][j] = (A[i] + · · · + A[j])/( j − i + 1) , whereas for i > j we have that M[i][j] = 0.
Describe the algorithm that creates this matrix in pseudocode.
What is the running time of your algorithm concerning the link list size n?
Implement the algorithm in Java.
Measure the running time of your Java program for random inputs of size n = 10, 11, 12, etc.
Does the growth of the running time correspond to your estimates?
Algorithm Design And Applications
ISBN: 9781118335918
1st Edition
Authors: Michael T. Goodrich, Roberto Tamassia