Write a program that randomly generates an array of 500,000 integers between 0 and 499.999, and then prompts the user for a search key value. Estimate the execution time of invoking the linearSearch method in Listing A below. Sort the array and estimate the execution time of invoking the binarySearch method in Listing B below. You can use the following code template to obtain the execution time: long startTime = System.currentTimeMillis(); [your code goes here] long endTime = System.currentTimeMillis(); long executionTime endTime - startTime; Here are two sample runs: Enter a search key: 11079 Searching... The key, 11079, was found at index 357158. Linear search execution time: 7 milliseconds. Searching... The key value, 11079, was found at index: 11115. Binary search execution time: milliseconds. Enter a search key: 95043 Searching... The key, 95043, was not found. Linear search execution time: 11 milliseconds. Searching... The key value, 95043, was not found. Binary search execution time: 0 milliseconds. A. Linear Search public static int linearSearch (int[] list, int key) { for (int i=0; i < list.length; i++) { if (key list[i]) Activate Win Go to Settings to return i; } return -1; A. Linear Search public static int linearSearch (int[] list, int key) { for (int i = 0; i < list.length; i++) { if (key ==list[i]) return 1; return -1; } } B. Binary Search public static int binarySearch (int[] list, int key) { int low = 0; = int high list.length - 1; while (high = low) { int mid = (low + high) / 2; if (key = list [mid]) high mid 1; else if (key == list [mid]) else return mid; low mid + 1; } return -low - } 1; // Now high < low, key not found 7.2 Analyze scores 1. Design: Create the pseudocode to design the process for a program that reads an unspecified number of scores and determines how many scores are above or equal to the average and how many scores are below the average. A negative number should signify the end of the input. Assume that the maximum number of scores is 100. 2. Implementation: Follow your pseudocode to implementent your program. Please submit the following: 1. Click the Write Submission button and enter your pseudocode 2. The zipped (compressed) file containing your project folder with the entire project 3. A captured image (jpeg or png) of your screen showing your program's output 7.3 Dice Rolling Create a flowchart for an application to simulate the rolling of two dice. Requirements: The application should use an object of class Random once to roll the first die and again to roll the second die. The sum of the two values should then be calculated. Each die can show an integer value from 1 to 6, so the sum of the two values will vary from 2 to 12, with 7 being the most frequent sum and 2 and 12 being the least frequent sums. Table 1 below shows the 36 possible combinations of the two dice. Your application should roll the dice 36,000 times. Use a one-dimensional array to tally the number of times each possible sum appears. Print the results in tabular format. Determine whether the totals are reasonable (e.g., there are six ways to roll a 7, so approximately one-sixth of the rolls should be 7). Table 1 123456 1234567 2345678 3456789 1 456789 0 11 56789 01 111 6789 0 1 2 Here is an example tabular format: 2 3 4 56 7 8 9 10 11 12 ### ### ### ### ### ### ### ### Implementation: Follow your flowchart to implement your program. Please submit the following: 1. Your flowchart as an image file (jpeg or png) 2. A captured image of your screen showing your program's output. 3. The project folder containing your entire project