task2 (2)

WEEK 02 Name: Collaborators (if any): 1. Tasks 1.1. Hash it out. Insert integer keys C = [3, 18, 42, 31, 40, 56, 71] in order into a hash table of size 9 using the hash function h(k) = (8k + 2) mod 7. Collisions should be resolved via chaining, where collisions are stored at the end of a chain. Draw a picture of the hash table after all keys have been inserted (can insert a drawing into the PDF doc instead of writing syntax to create the drawing in LaTex). Solution: • Assumption: I’ll use an array for the hash since keys will be numbers in- stead of using a dictionary where keys can be other than numbers (numbers included). • Assumption 2: The way I’m thinking is to create an array that instead of number will store linked lists so when there are collisions for example inserting 2 and 3 in the same array index I won’t lose data. In summary, I’ll be inserting a linkedlist with the number being the head into an array. NOTE: It can be solved as and array that stores arrays in case of collitions. That is another solution but I’ll stay with the linked list. • Assumption 3: I’ll refer to the class LinkedList(head) as the class to cre- ate a linked list with the first parameter being the head and the method next_node(value) to insert the next node in the already created linked list in case of collision. 1 store = [ 0 ] ∗ 9 //Here I ’m creating an array of s i z e 9 , I ’m giving 0 as an arbitrary value f o r checking purposes 2 C = [ 3 , 18 , 42 , 31 , 40 , 56 , 71] // Given in the problem as values to i n s e r t in our hash table 3 f o r num in C: 4 index = (11 ∗ num+4) % 9 5 i f store [ index ] : //Here I check i f value at index i s d i f f e r e n t than 0 meaning the index has already been manipulated 6 store [ index ] . next_node (num) Date : September 24, 2023. 1

2 WEEK 02 7 e l s e : // In case of store [ index ] being 0 meaning there ’ s no c o l l a t i o n at the given index , we proceed to create the l i n k e d l i s t at the index . 8 store [ index ] = LinkedList (num) 2. Week 01 Exercises/Problems 2.1. Searching for Keys. Emelyne is a busy mom who is on the hunt for her car keys. Unfortunately she has no idea which room her keys are in. Her house is composed of an infinite number of rooms, each identified by a unique positive integer. In each room in the house is an Amazon Alexa who can tell Emelyne whether or not her keys are in the room having a strictly higher room identifier than their own. Asking every Amazon Alexa in the house would take forever, and Emelyne wants to find her car keys quickly. Supposing the keys are in room k, describe an algorithm to help Emelyne find her keys by talking to at most O(log k) Alexas. Solution: • Assumption 1: Once I reach a room, alexa will tell me if the keys are found or if keys are in a higher room number • Assumption 2: I will use a tree binary search approach assuming the binary search is already constructed and ready • Assumption 3: Assuming the tree is balanced I should be getting a Time complexity of O(log(e)) with e being the height of the tree in the worst-case scenario. For my solution, I’m going over some x room number to then get an answer from Alexa if the key is in the room. Depenfing on the answer I’ll go to the left or right. I was thinking also about doing this in a sorted array which is basically the same idea as a binary search tree. 1 def tree ( node , key ) : 2 i f tree i s None : 3 return 4 i f node . value > key ) : 5 return tree ( node . right , key ) 6 e l i f node . value < key : 7 return helper ( tree . l e f t , key ) 8 e l i f node . value == key : 9 return key 10 tree ( some random number f o r the f i r s t room)

4 WEEK 02 For my solution, I added a new variable that will help me with the closest number. If I find a duplicate I check if the sum of these duplicate is larger but more bigger than h compared to the last duplicate stores in closest. For example, if h is 9 and I have duplicates of 3 closest will store this number closest = 3 but if later I get another duplicate let’s say 4 the sum of this duplicate is bigger than the store value in closest so we update out closest variable. 1 seen = set () 2 c l o s e s t = 0 3 f o r num in S : 4 i f num in seen : // Checking i f there ’ re duplicates 5 i f num ∗ 2 > c l o s e s t and num ∗ 2 < h : 6 c l o s e s t = num ∗ 2 7 e l s e : 8 seen . add (num) 9 return c l o s e s t / 2