1880c_lists.py You should be writing this module. This is the name the tests will expect assoc_list_test.py This file is provided. It has tests for all required functions. It can be found on canvas and will serve as the basis for our grading process, as well as a helpful tool for your personal development. 5 Software Design We will be representing an association between a key and a value in python using a tuple with two elements, the first being the value, and the second being the key. While this choice is arbitrary (I.E. basically any representation and order could work) this is probably not your first choice for representations so be careful when coding that you don't get the ordering of these elements confused. We will store two types of association lists - linear lists (unsorted) and binary lists (sorted by key value) So the following dictionary: bin_list - "Crow": 3. raven" : 49. "fish" : 2 "cat" 13. would be represented like this as a linear association list: [(3. Crow). (49, 'raven'), (2, 'fish'. (13. "cat ] and would be represented like this as a binary list: [(13, 'cat'), (3, crow'), (2, 'fish'), (49 'raven ] We will place no restrictions on plausible value objects, but, due to the need to sort, we will only use key objects that are comparable data types in python (I.E data types which allow you to use and >) This means we can use numbers (int or float) or strings The functions we need are based on the core operations in the dictionary class: contains(dict, key) returns True or False denoting if the key is in an association in the dictionary or not get(dict, key), returns the value associated with the key in the dictionary if possible) or the special value None in pwthon if key is not in the dictionary (Note, None without quotes, it's a special value, not a string) put(dict, key, value) modifies the dictionary so that the given key is now associated with the given value. If key was already associated with something the old value should be updated to the new value. If the key was not associated with a value in the dictionary, a new value asociation should be led to the dictionary The test file has examples that might help you understand these functions better if needed. 6 Required Functions There are six required functions in this lab, three representing the linear search (unsorted) association list, and three representing the binary search (sorted) association list. lin_contains(lin_dict, key) contains function for use with a linear (unsorted) asso- ciation lists. Expected to run in O(n) time lin_get(lin_dict, key) get function for use with linear (unsorted) association lists. Expected to run in O(n) time lin.put(lin_dict, key, value) put function for use with linear (unsorted) association lists. Expected to run in O(n) time bin_contains (bin_dict, key) contains function for use with binary (sorted) associa- tion lists. Expected to run in O(log(n)) time bin_get(bin_dict, key) get function for use with binary (sorted) association lists. Expected to run in O(log(n)) time bin_put(bin_dict, key, value) put function for use with binary (sorted) association lists. Expected to run in O(n) time. Note, this function is required to maintain the sorted order of bin_dict. The behavior of the three primary functions contains, get, put) are as described above. The get and contains methods have required return value behavior, but the put functions do not. You can return whatever you want from the put functions, so long as the expected changes to the association list is made. The big-O runtime behavior listed above are requirements for this code, the three lin- functions should run in linear O(n) time. The bin-get and bin.contains functions are required to use a binary search algorithm and run in O(log(n)) time. (It is not enough to just use a binary search, if you loop over the entire list afterwords for any reason, you will still have On) runtime.) bin.put must maintain sorted order of bin dict. This means that if it needs to add a new key, it will need to figure out where the key goes in the list. While it is technically possible to do this with a binary search, it requires a modification we did not discuss. Therefore, we do not require using binary search in the bin.put function. This is not a major concern, however, as adding an element into the middle of a list is an O(n) process - therefore this function is not possible to do in O(log(n)) anyway. While you can consult the textbook's code for binary search if needed, you should know in advance that the code will not work without modification due to the fact that associations are stored as tuples ordered value then key. You should try, however, to write this algorithm from memory / first-principals. While it is a bit harder, you stand to learn more from the lab if you do. 1880c_lists.py You should be writing this module. This is the name the tests will expect assoc_list_test.py This file is provided. It has tests for all required functions. It can be found on canvas and will serve as the basis for our grading process, as well as a helpful tool for your personal development. 5 Software Design We will be representing an association between a key and a value in python using a tuple with two elements, the first being the value, and the second being the key. While this choice is arbitrary (I.E. basically any representation and order could work) this is probably not your first choice for representations so be careful when coding that you don't get the ordering of these elements confused. We will store two types of association lists - linear lists (unsorted) and binary lists (sorted by key value) So the following dictionary: bin_list - "Crow": 3. raven" : 49. "fish" : 2 "cat" 13. would be represented like this as a linear association list: [(3. Crow). (49, 'raven'), (2, 'fish'. (13. "cat ] and would be represented like this as a binary list: [(13, 'cat'), (3, crow'), (2, 'fish'), (49 'raven ] We will place no restrictions on plausible value objects, but, due to the need to sort, we will only use key objects that are comparable data types in python (I.E data types which allow you to use and >) This means we can use numbers (int or float) or strings The functions we need are based on the core operations in the dictionary class: contains(dict, key) returns True or False denoting if the key is in an association in the dictionary or not get(dict, key), returns the value associated with the key in the dictionary if possible) or the special value None in pwthon if key is not in the dictionary (Note, None without quotes, it's a special value, not a string) put(dict, key, value) modifies the dictionary so that the given key is now associated with the given value. If key was already associated with something the old value should be updated to the new value. If the key was not associated with a value in the dictionary, a new value asociation should be led to the dictionary The test file has examples that might help you understand these functions better if needed. 6 Required Functions There are six required functions in this lab, three representing the linear search (unsorted) association list, and three representing the binary search (sorted) association list. lin_contains(lin_dict, key) contains function for use with a linear (unsorted) asso- ciation lists. Expected to run in O(n) time lin_get(lin_dict, key) get function for use with linear (unsorted) association lists. Expected to run in O(n) time lin.put(lin_dict, key, value) put function for use with linear (unsorted) association lists. Expected to run in O(n) time bin_contains (bin_dict, key) contains function for use with binary (sorted) associa- tion lists. Expected to run in O(log(n)) time bin_get(bin_dict, key) get function for use with binary (sorted) association lists. Expected to run in O(log(n)) time bin_put(bin_dict, key, value) put function for use with binary (sorted) association lists. Expected to run in O(n) time. Note, this function is required to maintain the sorted order of bin_dict. The behavior of the three primary functions contains, get, put) are as described above. The get and contains methods have required return value behavior, but the put functions do not. You can return whatever you want from the put functions, so long as the expected changes to the association list is made. The big-O runtime behavior listed above are requirements for this code, the three lin- functions should run in linear O(n) time. The bin-get and bin.contains functions are required to use a binary search algorithm and run in O(log(n)) time. (It is not enough to just use a binary search, if you loop over the entire list afterwords for any reason, you will still have On) runtime.) bin.put must maintain sorted order of bin dict. This means that if it needs to add a new key, it will need to figure out where the key goes in the list. While it is technically possible to do this with a binary search, it requires a modification we did not discuss. Therefore, we do not require using binary search in the bin.put function. This is not a major concern, however, as adding an element into the middle of a list is an O(n) process - therefore this function is not possible to do in O(log(n)) anyway. While you can consult the textbook's code for binary search if needed, you should know in advance that the code will not work without modification due to the fact that associations are stored as tuples ordered value then key. You should try, however, to write this algorithm from memory / first-principals. While it is a bit harder, you stand to learn more from the lab if you do