Objective Students will be able to design algorithms using a divide-and-conquer technique and conduct a comparison study of the performance of a divide and conquer algorithm vs. an iterative algorithm. Assignment Problem Suppose that you are given an array a sorted in non-decreasing order that contains n elements. Consider the problem of determining how many times a given value k occurs in the array. Design and implement a computational experiment to contrast the number of comparisons performed in these approaches: O(n) approach - sequentially test each element 0(m + log n) approach - find a location loc of k with binary-search and then count the number of occurrences of k to the left and right of loc (m is the total number of occurrences) Ollog n) approach - locate the boundaries of the block of occurrences of k in a. Please consult the class slides and the textbook, Section 5.1.1, for a discussion on these approaches. Count the number of comparisons made by each approach and save the results in a .csv file that can be open in an Excel file later. Format your .csv file as follows: , ,, , ,, , ,,, ,, , ,, For example (the numbers are not taken from a real example; they are offered to illustrate the content of the file) 553 691 100 200 300 400 500 448 5102 774 7126 66482 324 31 288 107 218 91 2153 96 All of the data (array values and search values) should be randomly generated using the method nextInt() from the java.util.Random class. The study will be conducted for each of the following cases separately: 1) arrays will contain small blocks of duplicated keys and 2) arrays will contain large blocks of duplicated keys. Consider not less than 10,000 runs of these algorithms (i.e., your .csv and Excel files should have, at least, that number of lines). Use Excel to depict graphically the results of your experiment. What did you observe? Objective Students will be able to design algorithms using a divide-and-conquer technique and conduct a comparison study of the performance of a divide and conquer algorithm vs. an iterative algorithm. Assignment Problem Suppose that you are given an array a sorted in non-decreasing order that contains n elements. Consider the problem of determining how many times a given value k occurs in the array. Design and implement a computational experiment to contrast the number of comparisons performed in these approaches: O(n) approach - sequentially test each element 0(m + log n) approach - find a location loc of k with binary-search and then count the number of occurrences of k to the left and right of loc (m is the total number of occurrences) Ollog n) approach - locate the boundaries of the block of occurrences of k in a. Please consult the class slides and the textbook, Section 5.1.1, for a discussion on these approaches. Count the number of comparisons made by each approach and save the results in a .csv file that can be open in an Excel file later. Format your .csv file as follows: , ,, , ,, , ,,, ,, , ,, For example (the numbers are not taken from a real example; they are offered to illustrate the content of the file) 553 691 100 200 300 400 500 448 5102 774 7126 66482 324 31 288 107 218 91 2153 96 All of the data (array values and search values) should be randomly generated using the method nextInt() from the java.util.Random class. The study will be conducted for each of the following cases separately: 1) arrays will contain small blocks of duplicated keys and 2) arrays will contain large blocks of duplicated keys. Consider not less than 10,000 runs of these algorithms (i.e., your .csv and Excel files should have, at least, that number of lines). Use Excel to depict graphically the results of your experiment. What did you observe