[Solved] CMPT435 Assignment 3-Searching and hashing

Goals • to implement searching and hashing, and to understand their performance.Requirementsand Notes • Download the the text Aile magicitems.txt from our web site if youdon’t have it already.• Read it line by line into an array.• Sort the array using one of your sort implementations from AssignmentTwo. (Include a copy of your sorting code in this assignment’s directoryso that it’s easy to compile.)• Develop your own implementation of linear and binary search.• Randomly select 42 items.• Perform a linear search on the (sorted) array for each of those randomlyselected items. Print the number of comparisons for each search andcompute the overall average.• Perform a binary search on the (sorted) array for the same “randomly”selected items as before. Print the number of comparisons for eachsearch and compute the overall average.• Record your results in a table in your LaTeX document. Also note theasymptotic running time of each sort and explain why it is that way.• Develop your own implementation of a hash table (with chaining) ofsize 250. Use the hash function we spoke about in class (and in theexample code on our web site at https://www.labouseur.com/courses/algorithms/Hashing.java.html).• Load your hash table with the magic items.• Retrieve the same 42 (no longer-) randomly selected items from yourhash table. Print the number of (get + comparisons) for each item andcompute the overall average. (Every get is one, then count thecomparisons needed to handle chaining.)• Add your results to the LaTeX document, including the asymptoticrunning time of hashing with chaining and explain why it is that way.[60 points][30 points][10 points]As usual, your code must separate structure from presentation, beprofessionally formatted yet uniquely yours (show some personality), useand demonstrate best practices, and make me proud to be your teacher. [−∞ if not]Resources • Linear and binary search are described in our text in sections 10.2 and 27.3.• Hash tables with chaining are described in our text in section 11.2.Submi5ngYour Work In addition to your source code, commit your LaTeX document in both .tex and .pdf formsto your GitHub repository. For your code, make many commits to GitHub. If you don’t makeenough commits, I will not accept your work. Be sure that you make your Ainal commit forthis assignment on or before the due date. (See our syllabus for those details.)Assignment 3 – 100 points