Comparison of 2 algorithms for max distance calculation essay.

In this assignment you will analyse two algorithms, both theoretically and experimentally, in terms of both efficiency and correctness. You will be implementing them as executable programs, measuring their runtime characteristics, and comparing the results with theoretical predictions for these algorithms. The aim is to directly compare two different algorithms that both perform the same function but have different efficiencies. In particular, you must ensure that both programs are analysed under exactly the same conditions, to ensure that the results are meaningfully comparable. You will be required to count the number of basic operations performed, measure execution times, and produce a clear report describing your findings.

To complete this assignment you must submit a written report, and accompanying evidence, describing the results of your experiments to compare the efficiency of two given algorithms. The steps you must perform, and the corresponding summaries required in your written report, are as follows.

You must ensure you understand the algorithms to be analysed.

Your report must briefly describe the two algorithms and the task that they address.

You must establish the correctness of the algorithms.

Your report must include a proof of the partial correctness of each algorithm.

Your report must also include a proof that both algorithms terminate (total correctness).

You must define a common basis for meaningful comparison of the two algorithms, in terms of basic operations and the size of inputs.

Your report must describe your choice of ‘basic operation’ applicable to both algorithms.

Your report must describe your choice of ‘problem size’ applicable to both algorithms.

Your report must summarise the predicted (theoretical) time efficiency of the two algorithms. As part of this, you need to argue whether the best-case, average-case and worst-case are different. If they are, you are only request to reflect on the average-case efficiency. Of course, you may still reflect on the best-case and worst-case efficiencies if that can help in your process (as we have seen in some examples). You must present the arguments underpinning these predictions, either from first principles or referenced from a text. It is NOT sufficient merely to state the efficiency class with an accompanying reference.

You must describe the methodology you used for performing the experiments.

Your report must describe your choice of programming language and computing environment. Alignment of programming language, environment, and where appropriate, choice of data structures, are extremely important in providing a balanced comparison between the algorithms.

Your report must describe your programming language implementation of the given algorithms. You must ensure that the correspondence between features of the algorithms and the corresponding program code is clear, to confirm the validity of the experiments. The program code should replicate the structure of the algorithms as faithfully as possible.

Your report must explain how you showed that your programs work correctly.

Your approach should involve thorough testing. You must provide a clear explanation of how the testing corresponds to any input classes – groups of similar inputs, boundary cases and so on – identified during your formal analysis of the algorithms.

Your report must explain clearly how you produced test data for the experiments and chose cases to test, as appropriate. Usually this will involve generating random data for different sizes of input. In particular, it is important that both algorithms are tested using the same data, to ensure that the comparative results are meaningful.

Your report must explain clearly how you counted basic operations, e.g., by showing the relevant program code for maintaining ‘counter’ variables. In particular, it should be easy to see that the method used is accurate with respect to the original algorithms.

Your report must explain clearly how you measured execution times, e.g., by showing the relevant program code augmented with calls to ‘clock’ or ‘time’ procedures. Since it is often the case that small program fragments execute too quickly to measure accurately, you may need to time a large number of identical tests and divide the total time by the number of tests to get useful results.

You must describe the results of your experiments.

Building on the methodology for correctness considered above, your report must summarise the range of testing undertaken and note its coverage.

Your report must show in detail the results of comparing the number of basic operations performed by the two algorithms for different sizes of inputs. The results should be plotted as one or more graphs which make it easy to see how the two algorithms compare. You must produce enough data points to show a clear ‘trend’ in the outcomes. It must be clear how many individual data points contributed to the lines shown and how many individual tests contributed to each data point. You must briefly explain what the results reveal about the comparative efficiency of the two algorithms.

Your report must show in detail the results of comparing the execution times of the two programs for different sizes of inputs. The results should be plotted as one or more graphs which make it easy to see how the two algorithms compare.

You must produce enough data points to show a clear ‘trend’ in the outcomes. It must be clear how many individual data points contributed to the lines shown and how many individual tests contributed to each data point. You must briefly explain what the results reveal about the comparative efficiency of the two programming language implementations of the algorithms.

You must produce a brief written report describing all of the above steps.

Your report should be prepared to a professional standard and must not include errors in spelling, grammar or typography.

You are free to consult any legitimate reference materials such as textbooks, web pages, etc, that can help you complete the assignment. However, you must appropriately acknowledge all such materials used either via citations to a list of references, or using footnotes. (Copying your assignment from one of your classmates is not a legitimate process to follow, however. Note the comments below concerning plagiarism.)

Your report must be organised so that it is easy to read and understand. The main body of the report should summarise what you did and what results you achieved as clearly and succinctly as possible. Supporting evidence, such as program listings or execution traces, should be relegated to appendices so that they do not interrupt the ‘flow’ of your overall argument.

There should be enough information in your report to allow another competent programmer to fully understand your results. This does not mean that you should include voluminous listings of programs, execution traces, etc. However, you should include the important parts of the code, and brief, precise descriptions of your experimental methodology.

Describing Algorithms

In Analysis of algorithms we study and compare two or more algorithms under some specified circumstances which remains same for all and their results are measured on the basis of their space and run time requirements (Almuallim & Dietterich, 2014). The reason why analyze the algorithms is, to discover the most suitable algorithms for a particular application depending on its environment. To analyze the execution time of an algorithm the procedure that has to be followed is:

Implementation of all algorithms using same language.

Evaluate the time taken to perform all the basic operations

Discover unidentified quantities which can help to define basic operations’ execution frequency.

As an input to the program develop a realistic model.

Assuming the modeled input, examine the unknown quantities.

Evaluate the total execution time: multiply frequency by time and add.

To calculate the theoretical time efficiency of the two algorithms, Average-Case Analysis has been performed on both of them i.e. both algorithms have been tested over all possible inputs. To test the efficiency, the algorithms have been implemented in JAVA language using all its data sets and structure alignment. Similar basic operations and problem size have been applied to both to compare the results and predict the efficiency. A proper approach has been followed to develop test data and chose cases under different input sizes (Almuallim & Dietterich, 2014).

The last section of this report describes the outcome of the analysis and defines the best and worst algorithm, the basis of the outcome has been counted as ‘number of basic operations’ and ‘execution time’ i.e. space and time requirements.

The two algorithms provided for the comparison and analysis purpose performs the same function i.e. to calculate the maximum distance between two of its elements. For example, suppose there are five random numbers 12, 34, 40, 1 and 6, the algorithm will calculate the difference between every pair of numbers like (12 and 34), (12 and 40), (12 and 1), (12 and 6), (34 and 40) and so on (Almuallim & Dietterich, 2014). Every time a greater difference is found between two variables, the value of the return variable will be altered with the greater difference and after the loop ends the maximum difference possible will be returned. In this case the output that will be returned is 39 as the maximum difference between its two elements, which is the difference between 1 and 40. No other pair will have greater difference than this (Biebricher, Fuhr, Lustig, Schwantner & Knorz, 2016).

Let’s understand both algorithms in a more clear and understandable manner with the help of algorithm properties and elements.

The algorithm MaxDistance has been designed to generate the maximum distance between two of the elements that has been provided as input. It has following properties.

Finiteness: Algorithm MaxDistance has a finite number of steps and instructions and it will surely terminate after completion of all steps. This algorithm does not have any infinite loop running in it (Balcom, Laura & Tong, 2015).

Definiteness: Every instruction in the algorithm MaxDistance has been defined precisely and in a very clear manner which can be understood with very little efforts. No step or instruction has any kind of ambiguity.

Algorithm 1: MaxDistance

Example:

The above lines have been copied from the given algorithm which clearly shows that input and output statements have been defined in such manners which are self-explanatory (Balcom et. al, 2015).

Input: The algorithm MaxDistance takes a list of integer numbers as input which is entered by the user during run time. These numbers are finite and can either be defined in the source code or can be asked from the user during run time. These numbers will then be stored as an array of integers (Balcom et. al, 2015).

Output: The algorithm returns one single output that is the maximum distance between two of the elements provided in the input section as the list of integers (Balcom et. al, 2015).

The working of algorithm MaxDistance:

Acquire Data (Input): During run time the user will be prompted to enter ‘n’ numbers. This ‘n’ can either be defined explicitly within the source code with some finite digit or can be asked from the user while executing. Depending upon the size allowed an integer array A[] has been declared that can store that many numbers. When user is prompted to enter ‘n’ numbers, it is expected from the user to input a list of integer elements only otherwise run time error will be accounted (Biebricher, et. al, 2016).

Computation and Iteration: Few variables has been declared and defined for the computation purposes of the algorithm which are dmax, i and j. All three variables have been initialized with the value 0. There are two iterations in this algorithm one of them runs as the outer loop which is controlled by the ‘i’ variable and another runs as the inner loop which is controlled by the ‘j variable (Biebricher, et. al, 2016). See below:

The first loop runs from 0 to ‘n-1’ positions and second loop also runs from ‘0’ to ‘n-1’ positions. This means that there will be total ‘n’ iterations for the outer loop where inside each iteration of the outer loop there will be ‘n’ iterations. So there will be total ‘n * n’ iterations. For example:

When ‘i’ will be 0 it will be counted as:

i=0; Iteration 1:

j=0; iteration 1

j=1; iteration 2

j=n-1; iteration n

Similarly for i=1

i=1; Iteration 2

j=0; iteration 1

j=1; iteration 2

j=n-1; iteration n

upto i=n-1

Computations and evaluations inside inner loop:

For each iteration of variable ‘i’ these steps will be performed:

Step 1: The value of ‘j’ will be initialized to zero

Step 2: The value of ‘i’ and ‘j’ will be compared and if they are equal, the inner loop will break at that very point; next iteration of ‘j’ will be computed. In case variable ‘i’ and variable ‘j’ are not equal difference will be calculated between A[i] and A[j] and if the difference comes out to be greater than the value of dmax, the value of dmax will be replaced by the difference of A[i] and A[j]. The value of the variable ‘j’ would be incremented automatically by 1 and step 2 will be repeated until value of ‘j’ reaches ‘n-1’. After the value of ‘j’ becomes equal to ‘n’, the counter will move to step 1.

Properties

The outer loop will terminate after variable ‘i’ reaches value ‘n’. The iteration will not be calculated for ‘i=n’ and as soon the value of ‘i’ becomes equal to ‘n’ it will come out of the outer loop.

Report Results: The final value of the variable ‘dmax’ which has been computed in the processing steps will be returned and displayed to the user. This value will represent the maximum distance between two of its elements.

The algorithm MaxDistance2 has the same function as that of MaxDistance been i.e. to generate the maximum distance between two of the elements that has been provided as input. It has similar properties as that of MaxDistance.

Finiteness: Algorithm MaxDistance2 has a finite number of steps and instructions and it will surely terminate after completion of all steps. This algorithm does not have any infinite loop running in it (Balcom et. al, 2015).

Definiteness: Every instruction in the algorithm MaxDistance2 has been defined precisely and in a very clear manner which can be understood with very little efforts. No step or instruction has any kind of ambiguity (Balcom et. al, 2015).

Input: The algorithm MaxDistance2 takes a list of integer numbers as input which is entered by the user during run time. These numbers are finite and can either be defined in the source code or can be asked from the user during run time. These numbers will then be stored as an array of integers (Balcom et. al, 2015).

Output: The algorithm returns one single output that is the maximum distance between two of the elements provided in the input section as the list of integers (Balcom et. al, 2015).

The working of algorithm MaxDistance2:

Computation and Iteration: Few variables has been declared and defined for the computation purposes of the algorithm which are dmax, temp, i and j. The three variables dmax, i and j have been initialized with the value 0 while temp has only been declared and not initialized. There are two iterations in this algorithm one of them runs as the outer loop which is controlled by the ‘i’ variable and another runs as the inner loop which is controlled by the ‘j variable. See below:

The first loop runs from 0 to ‘n-2’ positions and second loop runs from ‘i+1’ to ‘n-1’ positions. This means that the outer loop will run for total ‘n-1’ iterations while inner loop will start running first for ‘n-1’ iterations and with every increasing iteration of ‘i’, the number of times the loop ‘j’ will run will be one less than the previous time, and for the last iteration of j the loop will run only for one time. Hence for every iteration of ‘i’ the j^th loop will run for (n-1)*(n-i-1) times. For example:

Elements

When ‘i’ will be 0 it will be counted as:

i=0; Iteration 1:

j=1; iteration 1

j=2; iteration 2

j=n-1; iteration n-1

Similarly for i=1

i=1; Iteration 2

j=2; iteration 1

j=3; iteration 2

j=n-1; iteration n-1

upto i=n-2, the last iteration for ‘i’ will be:

i=n-2; Iteration n-1

j=n-1; iteration 1

Terminate

Computations and evaluations inside inner loop:

Step 1: The value of variable ‘j’ will be initialized to ‘i+1’.

Step 2: The difference between the elements present at location A[i] and A[j] will be calculated. The value of the difference will be stored in the variable ‘temp’. Now value of ‘temp’ will be compared to the value of variable ‘dmax’, in case the value of ‘temp’ is greater than the value of ‘dmax’: the content of dmax will be changed by the value of temp i.e. dmax will now contain the new value which will be equal to the current difference between A[i] and A[j]. In case the value of ‘temp’ is smaller than ‘dmax’: the variable ‘j’ will be incremented by 1 automatically and step 2 will be repeated until value of ‘j’ reaches ‘n-1’. After the value of ‘j’ becomes equal to ‘n’, the counter will move to step 1.

The outer loop will terminate after variable ‘i’ reaches value ‘n-1’. The iteration will not be calculated for ‘i=n-1’ and as soon the value of ‘i’ becomes equal to ‘n-1’ it will come out of the outer loop.

Partial Correctness

To prove the total correctness of an algorithm, we must prove that the algorithm returns an output i.e. partial correctness of an algorithm and Termination of the algorithm (Cerny, Okseniuk & Lawrence, 2013).

|- assert(P); C; assert(Q);

An algorithm is partially correct if the following statement can be proved true:

“If the pre-condition is true, the post-condition must be true”.

In the statement ‘|- assert(P); C; assert(Q);’

Assert(P) defines the pre-condition before the execution of the algorithm, C defines the execution of the algorithm and Assert(Q) defines the post-condition before the execution of the algorithm (Cerny et. al, 2013).

Pre-Condition: We have assumed that pre-condition for MaxDistance is initially satisfied i.e. The array of integers A[1…n] hold only natural numbers between 1 and n such that 1<s<n; where s and n are natural numbers. Also the value of dmax has been defined to be natural integer (Cerny et. al, 2013).

dmax =0 and A[1---n] = 1<s<n

Post-Condition: The variable dmax will contain the maximum distance between two of its elements. To rule out the confusion of initial value of variable dmax and final value of dmax, let’s denote the final value of dmax by dmax’.

dmax = either 0 or Maximum Distance

These pre-conditions and post-conditions remain same for both the algorithms.

Proof:

To prove the correctness of given algorithm:

i=0;j=0;dmax=0;

for (i<n;i++)

{

for (j<n;j++)

{

if (i==j) and (A[i]-A[j])>dmax

dmax= A[i]-A[j]);

} end for

}end for

return dmax

We can see that the major part of the algorithm contains a loop; hence if we prove that the loop works in a correct manner and output is being produced, we can prove the partial correctness.

The following table shows the value of interest:

Iteration Number for outer loop (value of i)	0				1				2				3				--------	n-1
Iteration Number for inner loop (value of j)	0	1	2	n-1	0	1	2	n-1	0	1	2	n-1	0	1	2	n-1	--------	0	1	2	n-1
dmax	Max(A[i]-A[j])=dmax’				Max(A[i]-A[j])=dmax’				dmax’				dmax’				-------	dmax’

Loop Invariant:

dmax_i>=0 and dmax_i = max(A[i]-A[j]) = dmax’

Base Case: Before the start of loop the value of i and j are 0. So the dmax = A[0]-A[0] =0 , so loop invariant holds.

Induction Step: Let us assume s>=0 and loop invariant holds for s^th iteration. Then loop invariant will hold true for the s+1^th iteration automatically.

Dmax_s+1= Max of (A[s] – A[0],A[s]-A[1] -----------, A[s]-A[n])

= dmax’.

Hence for s+1^th iteration the loop invariant hold true. This proves that the end of the program the algorithm returns the maximum difference between two of the array elements which proves the partial correctness.

Proof:

To prove the correctness of given algorithm:

i=0;j=i+1;dmax=0;

for (i<n-1;i++)

{

for (j<n;j++)

{

temp=A[i]-A[j];

if temp>dmax

dmax=temp;

} end for

}end for

return dmax

We can see that the major part of the algorithm contains a loop; hence if we prove that the loop works in a correct manner and output is being produced, we can prove the partial correctness.

Iteration Number for outer loop (value of i)	0				1				2				3				--------	n-2
Iteration Number for inner loop (value of j)	1	2	3	n-1	2	3	4	n-1	3	4	5	n-1	4	5	6	n-1	--------	n-1
dmax	Max(A[i]-A[j])=dmax’				Max(A[i]-A[j])=dmax’				dmax’				dmax’				-------	dmax’

Loop Invariant:

dmax_i>=0 and dmax_i = max(A[i]-A[j]) = dmax’

Base Case: Before the start of loop the value of i is 0 and j is i+1 i.e. 1. So the dmax = A[0]-A[1] =either 0 or greater because statement ‘ if temp>dmax’ makes sure that dmax will only alter its value in case it is greater than the previous one.

, so loop invariant holds.

Induction Step: Let us assume s>=0 and loop invariant holds for s^th iteration. Then loop invariant will hold true for the s+1^th iteration automatically.

Dmax_s+1= Max of (A[s] – A[s+1],A[s]-A[s+2] -----------, A[s]-A[n-1])

= dmax’.

As we can see that the algorithm looks for max distance between A[s]_thvariable and the rest of the list while the greater distance can even exist between A[s] and A[0,1----s-1], the algorithm will only work correctly if the input is a non-decreasing list of integers, otherwise the output will not be as expected.

In both algorithms MaxDistance and MaxDistance2:

As j_k increases at each iteration, ‘n-j_k’ decreases and at one point the value of j_k will become sufficiently large to dis-satisfy the given condition and hence it will terminate after a finite number of steps.

Similarly, in the outer loop the value of i_kincreases with every iteration while the value of n-i_kdecreases. As per the condition has been defined the loop will terminate in MaxDistance as soon the value of ‘i’ becomes equal to ‘n’ while in algorithm MaxDistance2 the outer loop will terminate when i_kreaches value n-1.

The efficiency of an algorithm depends upon two main parameters: Time and Space. Time refers to the time taken by the algorithm during execution to traverse all instructions and terminate and produce the output, whereas space denotes the number memory locations occupied by the variables defined in the algorithm.

To measure time efficiency of any algorithm we calculate the time complexity of the algorithm which is generally referred as function of input size or ‘problem size’, T(n), where n denotes the problem size. There are two ways to calculate time complexity: Empirical analysis or Posteriori and the other method is Mathematical analysis or Apriori.

The method used in this report to evaluate time complexity for MaxDistance and MaxDistance2 is Apriori.

In both algorithms there are two inputs required to be entered by the user.

The total number of elements to be entered into the array

The list of elements.

To calculate the maximum complexity of algorithms, the input size for total number of elements has been restricted to 10. It means that there can be maximum 10 elements in the array that needs to be compared.

Also, for every list element the input size is restricted to 1 to 100. It is assumed that user will not enter a list item which is greater than 100.

Also, it has been assumed that the value of n cannot be 0 and it should be at least 1 or greater than 1. So for value of n, the following condition must be true:

1<=n<=10

And for the list elements the condition that holds true is:

1<= A[i] <=100

The above statements are common base for evaluating efficiency of both algorithms and will hold true in each case.

When there are loops present in an algorithm, its time complexity is measured by the expression

T (n) ? n × T_R

So for any statement S that requires ‘p’ operations and executes ‘q’ times within a loop, the total count of basic operations is counted as p × q operations. This principle is known as multiplication principle.

Also, the time complexity of decision statement i.e. IF than Else is represented as:

T(n) = Maximum { TP, TQ} where P represents the statement to be executed in case the condition holds true and Q otherwise. The maximum of both is chosen as the final count. But in given algorithms MaxDistance and MaxDistance2 there are no statements to be executed when case holds false so it will not make any difference in this case.

Now, let’s calculate time complexity for given algorithms:

Instruction	Cost	Frequency
dmax=0	C1	1
For (i=0 to n-1)do	C2	n
For (j=0 to n-1)do	C3	n
If Condition	C4	n
dmax = A[i] – A[j]	C5	n(maximum)
return dmax	C6	1

The total cost will be: C1 + (n.C2 (n.C3 (n.C4+n.C5))) +C6

àC1 + n² C2 .C3(n.C4+n.C5) + C6

àC1 + n³C2.C3(C4+C5)+C6

Ignoring the co-efficient in the above function and using big O notation the complexity comes out to be O (n^3).

Instruction	Cost	Frequency
dmax=0	C7	1
For (i=0 to n-2)do	C8	n-1
For (j=i+1 to n-1)do	C9	n-1
temp= A[i] – A[j]	C10	n-1
If Condition	C11	n-1
dmax = temp	C12	n-1(maximum)
return dmax	C13	1

The total cost will be: C7 + (n-1).C8 (n-1.C9(n-1.C10+n-1.C11+ n-1.C12)) +C13

àC7 + (n-1)² C8 .C9(n-1.C10+n-1.C11+n-1.C12) + C13

àC7 + (n-1)³ C8 .C9(C10+C11+C12) + C13

Ignoring the co-efficient in the above function and using big O notation the complexity comes out to be O (n-1^3).

Clearly, Algorithm MaxDistance2 is more efficient than MaxDistance on the Time Complexity factor as the loop runs for fewer times in MaxDistance2 as compared to MaxDistance.

In the case of first algorithm i.e. MaxDistance, we want to discover the case that whether it is possible to have less execution time than O (n^3). The answer is yes.

Suppose the input array is of size 5 where elements are [A[0]=5, A[1]= 1, A[2]= 2, A[3]= 3, A[4]= 4,

In this case statement:

dmaxß A[i]-A[j]

run only for 1 time as we get the maximum distance of two elements in the 2nd loop of the 1^st iteration i.e. A[0]-A[1] where 0 represents i and 1 represents ‘j’.

Similarly worst case will be the input array is of size 5 where elements are [A[0]=3, A[1]= 4, A[2]= 2, A[3]= 1, A[4]= 5,

In this case statement:

dmaxß A[i]-A[j] runs for maximum number of times i.e. n*n as we get the maximum distance of two elements in the last loop of the last iteration i.e. A[4]-A[3] where 4 represents i and 3 represents ‘j’.

As we can see that the both loops (Outer and Inner) will continue till end termination, the worst case, best case and average case makes hardly any difference to the time efficiency of this algorithm (Gale & Church, 2010). In all cases the time efficiency of the algorithm MaxDistance remains same:

Worst Case: O (n^3)

Best Case: O (n^3)

Average Case: O (n^3)

Let’s discuss an average case of input for the algorithm MaxDistance and evaluate its complexity.

This is considerably the most useful measure because worst and best cases might be rare and in general the random input size does not belong to either of these cases. For example: The input size for the variable n is ‘4’ and the list of elements in the array are: (A [0] = 7, A [1] = 5, A [2] = 20, A [3] = 6). The execution run time will be as follows

Instruction	Cost	Frequency
dmax=0	C1	1
For (i=0 to n-1)do	C2	n
For (j=0 to n-1)do	C3	n
If Condition	C4	n
dmax = A[i] – A[j]	C5	n-1
return dmax	C6	1

We see that the total cost in this case will be: C1 + (n.C2 (n.C3(n.C4+n-1.C5))) +C6.

àC1 + n² C2 .C3(n.C4+n-1.C5) + C6

? C1 + n³C2.C3(C4+C5)+C6 (approximately)

Ignoring the co-efficient in the above function and using big O notation the complexity comes out to be O (n^3). Hence for any average case the time complexity would be same i.e. O (n^3).

In the second algorithm MaxDistance2, let’s determine the execution time for the same case we determined for MaxDistance, i.e. The input size for the variable n is ‘4’ and the lists of elements in the array are: (A [0] = 7, A [1] = 5, A [2] = 20, A [3] = 6). The execution run time will be as follows:

Instruction	Cost	Frequency
dmax=0	C7	1
For (i=0 to n-2)do	C8	n-1
For (j=i+1 to n-1)do	C9	n-1
temp= A[i] – A[j]	C10	n-1
If Condition	C11	n-1
dmax = temp	C12	n-3
return dmax	C13	1

The statement dmax=temp will be executed less time while all other statements will execute maximum times. The complexity will be:

The total cost will be: C7 + (n-1).C8 (n-1.C9(n-1.C10+n-1.C11+ n-3.C12)) +C13

àC7 + (n-1)² C8 .C9(n-1.C10+n-1.C11+n-3.C12) + C13

? C7 + (n-1)³ C8 .C9(C10+C11+C12) + C13 (approximately)

Ignoring the co-efficient in the above function and using big O notation the complexity comes out to be O (n-1^3).

For the example case n is equal to 4, so the time complexity for the algorithm MaxDistance will be (4*4*4) = 64, while the time complexity for the algorithm MaxDistance2 will be (3*3*3) = 27 which is too much faster than the MaxDistance. This implies that the algorithm MaxDistance2 is better in terms of time efficiency than MaxDistance (Fuhr, Hartmann, Lustig, & Schwantner, 2011).

Programming Language and Environment

After the time efficiency has been calculated theoretically, a practical evaluation has been conducted to experiment out the comparison and compare the results calculated theoretically. To implement both algorithms, JAVA has been chosen as the programming language chosen. The best advantage and reason of choosing this language is platform independency i.e. JAVA is hardware independent language (Buntine, 2010). When we compile a JAVA source code, it provides an equivalent bytecode that can be run on any machine irrespective of its hardware configurations. It is the responsibility of the JRE of the computer system to actually execute the program. So, by implementing code in JAVA language, it gives a degree of freedom to execute the algorithms on any hardware platform but the comparison results will always be same (Buntine, 2010).

In today’s heterogeneous networks to operate on multiple platforms, Java has been designed dynamically adaptable, portable and architecturally neutral. The programming concepts of Java are simple and familiar to be learned easily, and it works on the principles of object oriented programming i.e. abstraction, encapsulation, polymorphism and inheritance to take advantage of modern software development methodologies and for achieving the compatibility with client systems (Buntine, 2010)..

The computing environment under which both algorithms have been executed is:

Java Virtual Machine (JVM) 32-bit operating system

Java Platform Version- 1.8

Java Product Version- 1.8.0_121

Architecture : x86

All java objects for 32 bit JVM are aligned by 4 bytes boundary meaning that if there is an object with two fields ‘byte’ and ‘int’ doesn’t occupies 17 (12 for object header, 4 for int and 1 for byte ) but 20 bytes. The byte needed to store different data types in java is as foolows:

double, long à8 bytes

float, int à 4 bytes

char, short à 2 bytes

boolean, byte à 1 byte

In both algorithms MaxDistance and MaxDistance2, we are only concerned with integer type data type. So to hold each data, memory size requirement is of one word, because in our computing environment of JVM 32 bit one word is equal to 4 bytes (Deogun & Raghavan, 2016).

Java Implementation of MaxDistance

The first statement of the given algorithm MaxDistance (A[0-----n-1]) explains that MaxDistance is a function that contains the instruction to calculate the maximum distance between two elements , also it takes as input an array of integer numbers which ranges from 0 to n-1.

The implementation for this statement in java has been done like:

int MaxDistance (int A[],int n) {}

In the above statement the first int represents the return type of the method as the method returns single integer value. MaxDistance is the definition of the method while int A[] and int n defines that the method receives two input as formal parameters which is the list of array elements and size n.

int i,j,dmax=0;

for(i=0;i<n;i++)

{

for(j=0;j<n;j++)

{

if((i!=j)&&((A[i]-A[j])>dmax))

dmax= A[i]-A[j];

}

return dmax;

As we can see in the algorithm MaxDistance there are three more variables used along with A [] and n which are ‘i’, ‘j’, ‘dmax’ so while implementing the code in java it is must to declare and initialize them. The statement below has been used to declare and initialize the variable as integer data type which means that these variables can only accommodate integer values in it.

int i,j,dmax=0;

The statements below are the logic statements to the algorithm which processes the actual input and calculates output. “{}” These brackets show the entry and exit of the loop which explains that statement (for (j=0;j<n;j++) is running as an inner loop. The alignment of these loops in the given algorithm shows that both of these loops are nested hence implemented.

for(i=0;i<n;i++)

{

for(j=0;j<n;j++)

{

if((i!=j)&&((A[i]-A[j])>dmax))

dmax= A[i]-A[j];

}

Statement if((i!=j)&&((A[i]-A[j])>dmax)) has been replicated for the given statement if i ≠ j and |A[i] – [A[j] |> dmax where ‘not equal to’ sign and ‘and’ sign has been changed as per the rules of java. Also the java does not support brackets ‘||” so in place of them ‘()’ these brackets have been used.

return dmax;

The above statement returns the output of the function within the variable dmax.

To execute the method MaxDistance, a main method has been created as per language requirements. The main method traverses the statements in an orderly manner (Dolan, Goldman, Cuda, & Nakamura, 2014).

public static void main (String args[])throws Exception

All statements under this method have been used to make program behave in a required manner.

System.out.println("Enter total Numbers Numbers to be entered");

n = Integer.parseInt(br.readLine());

System.out.println("Enter "+n+ " Numbers");

for(i=0;i<n;i++)

A[i] = Integer.parseInt(br.readLine());

These statements display a message to the user to enter the required input and take the input from the user and store them in the memory.

CalcMaxDistance obj = new CalcMaxDistance();

dmax=obj.MaxDistance(A,n);

The above statements creates an object of the class in which method MaxDistance has been defined and with the help of the object created, a call has been given to the method MaxDistance along with input data. The method MaxDistance returns an integer value that need to be stored, so dmax has been defined here to store the returned value.

System.out.println("The maximum distance is: "+ dmax);

This statement displays the final output to the user.

The first statement of second algorithm is almost same as the first one with a slight difference in the method definition MaxDistance2 (A [0-----n-1]). Like algorithm MaxDistance takes as input an array of integer numbers which ranges from 0 to n-1 (Creecy, Masand, Smith & Waltz, 2014).

The implementation for this statement in java has been done like:

int MaxDistance2 (int A[],int n) {}

The functions of all variables are same as defined in the previous section with only difference in method name (DeJong, 2015).

In algorithm MaxDistance2, there are four local variables: i, j, dmax and temp. All these variables hold integer values and thus have been defined with the statement.

int i,j,dmax=0,temp;

The statements below are the logic statements to the algorithm which processes the actual input and calculates output. “{}” These brackets show the entry and exit of the loop which explains that statement (for (j=i+1;j<n;j++) is running as an inner loop. The alignment of these loops in the given algorithm shows that both of these loops are nested hence implemented (Crawford, Fung, Appelbaum & Tong, 2009).

for(i=0;i<n-1;i++)

{

for(j=i+1;j<n;j++)

{

temp=A[i]-A[j];

if(temp>dmax)

dmax= temp;

}

It can be seen that here all statements are exactly same as defined in the algorithm which makes sure that the logic has been replicated the structure of the algorithms as faithfully as possible. Also, like MaxDistance, this also has a main function which helps in traversing the statements in an orderly manner.

To test the correctness of the program, both programs were compiled using java compiler and then executed by the JVM installed in the computer system. The programs were thoroughly tested using different types of input and similar inputs were used on both programs to check their validity.

The programs were checked against:

Run time errors, such as divide by zero and loop may run indefinitely. As there is no division operation occurring in any of the program, divide by zero error has been ruled out. When the program executed, it terminated after a finite number of steps which shows that none of the loop runs indefinitely and program terminates in finite steps.

Input Data: Although it has been mentioned and assumed that the value of ‘n’ entered by the user is between 1<=n<=10, but in case user enters a value 0 or other than this, the program does not terminates abruptly. In case user enters a value ‘0’ for variable ‘n’ then the results displayed will be as follows:

The program has been checked on several groups of data which counts as worst case, best case and average case and the program executed correctly for every input data type in both algorithms. Although algorithm MaxDistance2 has greater time efficiency over algorithm MaxDistance but there is one major drawback that the algorithm will return maximum distance between its two elements only if the higher element existence in array is before lower element, for example: If there are two elements 1 and 5 stored in array which are lowest and highest element then MaxDistance2 will return correct results only if element 5 is stored in the array at a position before position of element 1, otherwise it will not evaluate correct results while algorithm MaxDistance works correctly in all kind of input data.

To generate the test data no automated generation tools have been used and all data has been generated manually. Different values have been assigned to the variable ‘n’ which defines the input size. The input size assigned has been within the boundary limits decided for the algorithms. The different values decided for the variable ‘n’ has been applied to both algorithms and results were compared.

After the different values of ‘n’ have been decided a random data was generated to fill up the list of array elements and similar data has been applied to both algorithms. The techniques used to generate different kind of random input data are:

Generated list of array elements sorted in ascending order

Generated list of array elements sorted in descending order

Generated list of array elements unsorted

Worst case scenarios where maximum distance between two elements lies at the last loop of the last iteration.

Best case scenarios where maximum distance found second loop of the first iteration.

To measure basic operations count, count variables have been inserted at appropriate positions and maintained. In both algorithms, initially count was declared and initialized with value 1 as declaring the variables itself is a basic operation which counts as 1 operation (Cleverdon, 2011).

After declaring the variable ‘count’ and initializing, the count has been increased by one every time any basic operation encountered with the help of the statement (Cleverdon, 2011)

count = count + 1

The below codes shows the use of count variables at different positions while implementation (Cleverdon, 2011):

Program MaxDistance

int i,j,dmax=0,count=1;

for(i=0;i<n;i++)

{

count = count + 1;

for(j=0;j<n;j++)

{

count=count + 1;

if((i!=j)&&((A[i]-A[j])>dmax))

{

dmax= A[i]-A[j];

count=count+1;

}

count=count+1;

}

System.out.println("The total count is"+count);

Program MaxDistance2

int i,j,dmax=0,temp,count=1;

for(i=0;i<n-1;i++)

{

count = count+1;

for(j=i+1;j<n;j++)

{

count=count+1;

temp=A[i]-A[j];

count=count+1;

if(temp>dmax)

{

dmax= temp;

count=count+1;

}

count=count+1;

}

System.out.println("The total count is"+count);

To measure execution time of both the programs MaxDistance and MaxDistance2 a variable has been declared at the start of main method “startTime” that fetches the system current time and store it in a long data variable. After that another variable has been declared and defined at the end of the main method which evaluates the difference between variable startTime and the system’s time after execution (Borko & Bernick, 2013).

After that it stores the value which has been calculated in nano-seconds into a variable declared as ‘duration’. To understand the execution time in a better way the time has been divided by 1000000000 to get the results converted in seconds which makes the execution time more clear (Borko & Bernick, 2013).

After the implementation of execution time it was proved practically too that in case of time efficiency algorithm MaxDistance2 is better than MaxDistance (Borko & Bernick, 2013).

The code that has been used for implementation purposes is:

final long startTime = System.nanoTime();

final long duration = System.nanoTime() - startTime;

System.out.println("The total execution time is: "+duration);

second= duration/1000000000;

System.out.println("The total execution time is: "+second);

References:

Almuallim, H. & Dietterich, T. G. (2014). Learning with many irrelevant features. AAAI-91, pages 547, 552.

Balcom, M., Laura, B. & Tong, R. M. (2015). Advanced Decision Systems: Description of the CODEX system as used for MUC-3. In Proceedings of the Third Message Understanding Evaluation and Conference, Los Altos, CA: Morgan Kaufmann.

Biebricher, P., Fuhr, N., Lustig, G., Schwantner., M. & Knorz, G. (2016). The automatic indexing system AIR/PHYS|from research to application. In Eleventh International Conference on Research & Development in Information Retrieval, pages 333:342.

Borko, H. & Bernick, M. (2013). Automatic document classication. Journal of the Association for Computing Machinery, pages 151:161, Volume 2, doi:10.1111/j.1365-2648.2007.04412.x.

Buntine, W. (2010). A theory of learning classication rules. PhD thesis, School of Computing Science, University of Technology, Sydney.

Cerny, B. A., Okseniuk, A. & Lawrence, J. D. (2013). A fuzzy measure of agreement between machine and manual assignment of documents to subject categories. In Proceedings of the 46th ASIS Annual Meeting, page 265 Volume 1, issue no 34.

Cleverdon, C. W. (2011). The signicance of the Craneld tests of index languages. In Fourteenth Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, pages 3, 12.

Crawford, S. L., Fung, R. M., Appelbaum, L. A., & Tong, R. M. (2009). Classication trees for information retrieval. In Eighth International Workshop on Machine Learning, pages 245,249.

Creecy, R. H., Masand, B. M., Smith, S. J., & Waltz, D. L. (2014). Trading MIPS and memory for knowledge engineering: automatic classification of census returns on a massively parallel supercomputer. Technical Report TMC-192, Thinking Machines Corp., Cambridge, MA.

DeJong, G. (2015). An overview of the FRUMP system. In Lehnert, Wendy G. and Ringle, Martin H., editors, Strategies for Natural Language Processing, pages 149,176. Lawrence Erlbaum Associates, Hillsdale, New Jersey.

Dolan, C. P., Goldman, S. R., Cuda, T. V., & Nakamura, A. M. (2014). Hughes Trainable Text Skimmer: Description of the TTS system as used for MUC-3. In Proceedings of the Third Message Understanding Evaluation and Conference, Los Altos, CA: Morgan Kaufmann.

Deogun, J. S. and Raghavan, V. V. (2016). Description of the UNL/USL system used for MUC-3. In Proceedings of the Third Message Understanding Evaluation and Conference, Los Altos, CA: Morgan Kaufmann.

Fuhr, N., Hartmann, S., Lustig, G., & Schwantner, M. (2011) AIR/X|a rule-based multistage indexing system for large subjectelds. In RIAO 91 Conference Proceedings: Intel ligent Text and Image Hand ling, pages 606,623.

Gale, W. A. & Church, K. W. (2010). Poor estimates of context are worse than none. In Speech and Natural Language Workshop, pages 283,287, San Mateo, CA: Morgan Kaufmann.

Cite This Work

To export a reference to this article please select a referencing stye below:

My Assignment Help. (2021). Comparative Analysis Of Two Algorithms For Maximum Distance Calculation - An Essay. (70 Characters). Retrieved from https://myassignmenthelp.com/free-samples/itc505-ict-project-management/comparison-of-two-algorithms.html.

"Comparative Analysis Of Two Algorithms For Maximum Distance Calculation - An Essay. (70 Characters)." My Assignment Help, 2021, https://myassignmenthelp.com/free-samples/itc505-ict-project-management/comparison-of-two-algorithms.html.

My Assignment Help (2021) Comparative Analysis Of Two Algorithms For Maximum Distance Calculation - An Essay. (70 Characters) [Online]. Available from: https://myassignmenthelp.com/free-samples/itc505-ict-project-management/comparison-of-two-algorithms.html
[Accessed 24 November 2024].

My Assignment Help. 'Comparative Analysis Of Two Algorithms For Maximum Distance Calculation - An Essay. (70 Characters)' (My Assignment Help, 2021) <https://myassignmenthelp.com/free-samples/itc505-ict-project-management/comparison-of-two-algorithms.html> accessed 24 November 2024.

My Assignment Help. Comparative Analysis Of Two Algorithms For Maximum Distance Calculation - An Essay. (70 Characters) [Internet]. My Assignment Help. 2021 [cited 24 November 2024]. Available from: https://myassignmenthelp.com/free-samples/itc505-ict-project-management/comparison-of-two-algorithms.html.