from random import seed, sample

def make_data(data_size):#DO NOT REMOVE OR MODIFY THIS FUNCTION '''A generator for producing data_size random values ''' seed(0) data = sample(range(data_size * 3), k=data_size) data.sort() while True: yield data

def linear_search(lyst, target): pass

def binary_search(lyst, target): pass def jump_search(lyst, target): pass

def main(): pass

if __name__ == "__main__": main()

Students: This content is controlled by your instructor, and is not zyBooks content. Direct questions or concerns about this content to your instructor. If you have any technical issues with the zyLab submission system, use the Trouble with lab button at the bottom of the lab. 2.12 Project 2 - Benchmarking Search Algorithms Introduction Rather than focussing on a particular data structure, this project is about some of the important theoretical and practical realities that must be considered when choosing and implementing algorithms. Sorting and searching are at the heart of many ideas in Computing as a Science. This project will help train your intuition for algorithm analysis and Big-O notation. It is daimed that for sufficiently large lists, differing search algorithms exhibit significantly different performance characteristics. For this project, you will benchmark the temporal efficiency (speed) of the linear search, binary search, and jump search algorithms. You will do this by implementing the search functions yourself and including a buit-in measure their performance by counting the number of comparison operations performed - an approximation for how hard the algorithm has to work For this project a comparison is defined as a comparison between the value or target being searched for, and a value in the list. Do not count other comparisons. For example you should not count comparisons you perform when checking the validity of an index. Expected performance values (the number of comparisons performed) assume that you implement reasonable versions of the algorithms (i.e you arent performing a lot of neediess work). Recursion is not required for this project though you may use it if you want. Search Functions Implement the following search aigorithm functions: - (boolean, int) linear_search(lyst, target): Performs a linear search through lyst for target. Returns True if found, False otherwise; followed by the number of comparisons performed during the search. - (boolean, int) binary_search(lyst, target) : Performs a binary search through lyst for target. Retums True if found, False otherwise; followed by the number of comparisons performed during the search. - (boolean, int) jump search(lyst, target) : Performs a jump search through lyst for target. Returns True if found, False otherwise; followed by the number of comparisons performed during the search. As shown, each function should return a tuple containing first a boolean value (True/False) indicating if the search value was found, followed next by the number of comparisons performed by the algorithm while searching for the target value Assume the target type is integer, and the list contains only integers. Use of "lyst" as an identifier is NOT a typo since "list" is a data type in Python. All algorithms may assume the list is sorted. (Note. this means that when testing your functions with random data you should first sort the data) Testing Your Code As with Project 1. when you submit this project for grading the performance of your functions will be evaluated using an automated test suite In general it is NOT a good idea to become dependent upon your professors (or anyone else) to test your code for you Ulimately YOU are responsible for making sure that your code runs properly. To help you avoid becoming overly dependent upon our tests some of them have been hidden - meaning that if your project is not implemented correctly you may fail one of our tests without it being apparent why. This is to help you by encouraging you to develop YOUR OWN tests to validate your work. On this and future projects we highly recommend taking advantage of a conditionally executed main function (provided for you in the template), and any test functions you choose to implernent, to assist you as you develop your solutions. Expected Duration: 4 hours Run your program as often as you'd like, before submitting for grading. Below, type any needed input values in the first box, then click Run program and observe the program's output in the second box. Enter program input (optional) If your code requires input values, provide them here Program output displayed here Coding trail of your work History of your effort will appear here once you begin working on this zyLab. main.py Load default template