Review programming in a high-level language Implement linear search and binary search algorithms Evaluate performance...

Transcribed Image Text:

Review programming in a high-level language • Implement linear search and binary search algorithms Evaluate performance of linear and binary search algorithms Instructions 1. Implement a method that will search a given array using the linear search algorithm. 2. Implement a method that will search a given array using a recursive binary search algorithm. 3. Write a driver program to test the methods implemented in questions 1-2. Note that you have to sort the input array before using the binary search algorithm, you can use any sort method available (e.g., sort method in the Java Collection Framework). 4. You need to create multiple datasets to test the speed of your algorithms. Test the program for array sizes N= 16, 32, 64, 128, 256, 512, 1024, 2048, 220 Initialize the array with random numbers between the ranges 1 through N (Please note that we will be using these datasets for both linear search and binary search. Remember to sort the array before using binary search. These datasets will be our dataset that we will be searching our keys inside those datasets 5. Use a text file with 1,000 random numbers in the range 1 through 1000 as the search keys. You need to search all those 1000 numbers inside every dataset. 6. Compare the execution time for linear search and binary search. Include the time taken for sorting with the binary search time (you have to sort only once for each array size). Use a table or plot to summarize the results and document your observations and explanations in the report. In short you need to calculate the computation times as follows: Size of dataset Linear Search Binary Search 16 32 64 128 ww 2^20 Review programming in a high-level language • Implement linear search and binary search algorithms Evaluate performance of linear and binary search algorithms Instructions 1. Implement a method that will search a given array using the linear search algorithm. 2. Implement a method that will search a given array using a recursive binary search algorithm. 3. Write a driver program to test the methods implemented in questions 1-2. Note that you have to sort the input array before using the binary search algorithm, you can use any sort method available (e.g., sort method in the Java Collection Framework). 4. You need to create multiple datasets to test the speed of your algorithms. Test the program for array sizes N= 16, 32, 64, 128, 256, 512, 1024, 2048, 220 Initialize the array with random numbers between the ranges 1 through N (Please note that we will be using these datasets for both linear search and binary search. Remember to sort the array before using binary search. These datasets will be our dataset that we will be searching our keys inside those datasets 5. Use a text file with 1,000 random numbers in the range 1 through 1000 as the search keys. You need to search all those 1000 numbers inside every dataset. 6. Compare the execution time for linear search and binary search. Include the time taken for sorting with the binary search time (you have to sort only once for each array size). Use a table or plot to summarize the results and document your observations and explanations in the report. In short you need to calculate the computation times as follows: Size of dataset Linear Search Binary Search 16 32 64 128 ww 2^20

Answer rating: 100% (QA)

Solution To complete the tasks youve outlined you can use a highlevel programming language like Java Heres a stepbystep guide on how to implement line... View the full answer