[SOLVED] (csci 323) programming assignment 1: “array-search algorithms”

One of the most basic programming problems is “search”, that is finding an item (“key”) in a structure. The structure may
be linear (array) or hierarchical (tree), ordered (e.g. alphabetical or numerical order) or unordered (no particular order).There are several search algorithms available. In this assignment, we consider a sorted list of random data and compare
several algorithmic approaches:Submissions:
Please submit the following in the Google form that will be provided.
● Source code (Assignment1.py)
● Console output with chart (Assignment1.txt)
● Bar graph (Assignment1.png)[1] Install the Python language and interpreter and the PyCharm integrated development environment (IDE) and get the
sample “Hello User” program running as outlined in Assignment #0.
[2] Add a comment at the top. (This will also be a template for commenting future assignments)
# Analysis of Algorithms (CSCI 323)
# Summer 2024
# Assignment 1 – Empirical Analysis of Search Algorithms
# Jane Doe (your name)
# Acknowledgements:
# I worked with … (if applicable)
# I used the following sites … (if applicable)[3] Define a function main() which will be the springboard for the execution of all other code in this assignment.
def main():
pass # placeholder until actual function content is provided[4] Add these lines just below the main() function to ensure that importing of this module into another program will not
automatically run it.
if __name__ == “__main__”:
main()
[4] Create a program configuration. Note: one will automatically be created if you run via the Run menu item.[1] Define a function random_list(size) that returns a list of size random numbers.
Can use random.sample().
See https://stackoverflow.com/questions/22842289/generate-n-unique-random-numbers-within-a-range
Then sort the list in sorted order.[2] Define a function native_search(list, key) that wraps the built-in index function
[3] Define the following functions utilizing the code from the references provided. Ensure that signatures are consistent.:
● linear_search(list, key) – see https://www.geeksforgeeks.org/linear-search/
● binary_search(list, key) – see https://www.geeksforgeeks.org/binary-search/● better_binary_search(list, key) – see https://www.geeksforgeeks.org/the-ubiquitous-binary-search-set-1/
● randomized_binary_search(list, key) – see https://www.geeksforgeeks.org/randomized-binary-search-algorithm/● exponential_search(list, key) – see https://www.geeksforgeeks.org/exponential-search/
● interpolation_search(list, key) – https://www.geeksforgeeks.org/interpolation-search/
● jump_search(list, key) – https://www.geeksforgeeks.org/jump-search/● fibonacci_search(list, key) – https://www.geeksforgeeks.org/fibonacci-search/
● ternary_search(list, key) – https://www.geeksforgeeks.org/ternary-search/See below regarding Interpolation Search, Jump Search
[4] Add code to verify that the current search determines the correct position
[5] Add code to time each of the search functions
[6] Add code to run each search multiple times for different random keys[7] Add code to plot the timings for the algorithms. See https://www.geeksforgeeks.org/matplotlib-tutorial/
Use this code as a starting point for plotting the times. However, modify it to make it more generic (not just for searches).def plot_times(dict_searches, sizes, trials, searches, file_name):
search_num = 0
plt.xticks([j for j in range(len(sizes))], [str(size) for size in sizes])
for search in searches:
search_num += 1
d = dict_searches[search.__name__]x_axis = [j + 0.05 * search_num for j in range(len(sizes))]
y_axis = [d[i] for i in sizes]
plt.bar(x_axis, y_axis, width=0.05, alpha=0.75, label=search.__name__)
plt.legend()
plt.title(“Runtime of search algorithms”)plt.xlabel(“Number of elements”)
plt.ylabel(“Time for ” + str(trials) + ” 100 trials (ms)”)
plt.savefig(file_name)
plt.show()
Use this code as a starting point for printing the results:
def print_times(dict_searches)
pd.set_option(“display.max_rows”, 500)
pd.set_option(“display.max_columns”, 500)
pd.set_option(“display.width”, 1000)
df = pd.DataFrame.from_dict(dict_searches).T
print(df)Use this code as a starting point for running the searches:
def run_searches(searches, sizes, trials)
dict_searches = {}
for search in searches:
dict_searches[search.__name__] = {}
for size in sizes:
for search in searches:
dict_searches[search.__name__][size] = 0
for trial in range(1, trials + 1):
arr = random_list(size)
idx = random.randint(0, size-1)
key = arr[idx]
for search in searches:
start_time = time.time()
idx_found = search(arr, key)
end_time = time.time()
if idx_found != idx:print(search.__name__, “wrong index found”, arr, idx, idx_found)
net_time = end_time – start_time
dict_searches[search.__name__][size] += 1000 * net_time
return dict_searches
def main():
sizes = [10, 100, 1000, 10000]
searches = [native_search, linear_search, binary_search, interpolation_search]
trials = 1000
print_times(dict_searches)plot_times(dict_searches, sizes, trials, searches)
Make this fix to Jump Search near the end:
if arr[int(prev)] == key:
return int(prev)The code for Interpolation Search on Geeks for Geeks has a bug. This one should work instead, though you may want to
change the order of the parameters:
def interpolation_search_helper(arr, lo, hi, key):
if arr[lo] == arr[hi]:
if key == arr[lo]:
return lo
else:
return -1
if lo <= hi and arr[lo] <= key <= arr[hi]:
pos = int(lo + ((hi – lo) / float(arr[hi] – arr[lo])) * float((key – arr[lo])))
if arr[pos] == key:
return pos
elif arr[pos] < key:
return interpolation_search_helper(arr, pos + 1, hi, key)
else:
return interpolation_search_helper(arr, lo, pos – 1, key)
return -1