Expand the project developed in the previous exercise to perform the following experiment:
Expand the project developed in the previous exercise to perform the following experiment: Time the sequential
search and the binary search methods several times each for randomly generated values, and record the results in a table. Do not time individual searches, but groups of them. For example, time 100 searches together or 1,000 searches together. Compare the running times of these two search methods that are obtained during the experiment.
Regarding the efficiency of both search methods, what conclusion can be reached from this experiment? Both the table and your conclusions should be included in a separate Word document.
Exercise 3: Searching Applications
The following problem is a variation of Project 4 in the “Projects” section of Chapter 18 in our textbook:
Consider an array data of n numerical values in sorted order and a list of two numerical target values. Your goal is to compute the smallest range of array indices that contains both of the target values. If a target value is smaller than data[0], the range should start with a -1. If a target value is larger than data[n-1], the range should end with n.
For example, given the array
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| 5 | 8 | 10 | 13 | 15 | 20 | 22 | 26 |
the following table illustrates target values and their corresponding ranges:
| 2, 8 | [-1, 1] |
| 9, 14 | [1, 4] |
| 12, 21 | [2, 6] |
| 14, 30 | [3, 8] |
Devise and implement an algorithm that solves this problem.
Exercise 4: Hashing
Suppose that the type of key in a hashing application you are implementing is string (Sections 21.7 and 21.8 in our textbook explain hash functions for strings). Design and implement a hash function that converts a key to a hash value. Test your function by computing the hash values for the Java keywords. Was a key collision produced?
Looking for a Similar Assignment? Order now and Get 10% Discount! Use Coupon Code "Newclient"
