task2 (2)

pdf

School

Brigham Young University, Idaho *

*We aren’t endorsed by this school

Course

381

Subject

Computer Science

Date

Nov 24, 2024

Type

pdf

Pages

4

Uploaded by PrivateStarPartridge3

Report
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)
WEEK 02 3 2.2. Campus Construction. BYU-Idaho has employed Idaho Construction to build a new building on campus dedicated to cooking classes. BYU-I wants the new building be as tall as possible because each floor will be dedicated to a differ- ent cuisine of food. Rexburg zoning laws limit all new construction buildings to be no higher than height h, where h is a positive integer. Idaho Construction has decided to build the new building by stacking two giant aluminum cubes on top of each other. It’s important to note, the aluminum cubes can only be made with a limited set of positive integer side lengths S = { s 0 , ..., s n 1 } Help the construction company purchase cubes for the new building. For my solution, I’ll go over each value in the array and use an auxiliary data set to store already passed values to check duplicates. If I find a duplicate then I proceed to multiply the number by 2 or sum them up which is the same and see if it fits the requirement h. 1 seen = set () 2 f o r num in S : 3 i f num in seen : // Checking i f there ’ re duplicates 4 i f num 2 == h : 5 return num 6 e l s e : 7 seen . add (num) (a) Assuming the input S fits within Θ( n ) machine words, describe an expected O(n)- time algorithm to determine whether there exist a pair of side lengths in S that exactly sum to h. For my solution, I’ll go over each value in the array and use an auxiliary data set to store already passed values to check duplicates. If I find a duplicate then I proceed to multiply the number by 2 or sum them up which is the same and see if it fits the requirement h. 1 seen = set () 2 f o r num in S : 3 i f num in seen : // Checking i f there ’ re duplicates 4 i f num 2 == h : 5 return num 6 e l s e : 7 seen . add (num) (b) Unfortunately for Idaho Construction, there is no pair of side lengths in S that sum exactly to h. Assuming that h = 800 n 8 , describe a worst-case O(n)-time algorithm to return a pair of side lengths in S whose sum is closest to h without going over.
Your preview ends here
Eager to read complete document? Join bartleby learn and gain access to the full version
  • Access to all documents
  • Unlimited textbook solutions
  • 24/7 expert homework help
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