CAB301 - Algorithms and Complexity - Empirical Analysis of an Algorithm

Algorithm to be Analysed ALGORITHM BruteForceMedian(A[0..n - 1]) // Returns the median value in a given array A of n numbers. This is the kth element, where k =|n/ 2|, if the array was sorted. k<- |n/ 2| for i in 0 to n - 1 do numsmaller <- 0 // How many elements are smaller than A[i] numequal <- 0 // How many elements are equal to A[i] for j in 0 to n-1 do if A[j] < A[i] then numsmaller <- numsmaller + 1 else if A[j] = A[i] then numequal <- numequal + 1 if numsmaller < k and k <= (numsmaller + numequal) then return A[i]     To complete this assignment you must submit a written report, your implementation of a given algorithm in C++, and a file detailing the results of your experiments to measure a given algorithm’s average-case efficiency. The steps you must perform, and the corresponding (brief) summaries required in your written report, are as follows.   1. You must ensure you understand the algorithm to be analysed. • Your report must briefly describe the algorithm.   2. You must ensure you understand the algorithm’s predicted (theoretical) average-case efficiency with respect to its ‘basic operation’.   • You must explain clearly the choice of basic operation for the particular algorithm of interest. • Your report must summarise the expected time efficiency of the algorithm with respect to the size of its input(s).   This should be expressed as the algorithm’s predicted average-case efficiency and/or order of growth. You must explain as clearly as possible how these predictions were calculated or justified. (In some cases you will find an appropriate analysis in the literature. In other cases you may need to calculate the algorithm’s efficiency yourself.)   3. You must decide on an appropriate methodology, tools and techniques for performing the experiments.   • Your report must describe your choice of computing environment. You must also say how you produced test data for the experiments, or chose cases to test, as appropriate.   4. You must implement the given algorithm in C++ and verify its functional correctness.   • Your report must describe your programming language implementation of the given algorithm. You must ensure that the correspondence between features of the algorithm and the program code is clear, to confirm the validity of the experiments. (For instance, implementing a recursive algorithm iteratively would not be acceptable because the time efficiency of the program may be very different from that of the algorithm. Similarly, certain code refactorings or optimisations may influence the experiments in undesirable ways.) The program code should replicate the structure of the algorithm as faithfully as possible.   • Your report must explain how you showed that your program works correctly. (Thorough testing would normally be sufficient, although you may prefer to give a formal proof of correctness.)