We Will Use Closed Addressing or Open hashing based approach which called saperate chaining and i think it will be sufficient solve it .isn't it Here is Approach.
Let we have m students & n course . Each student & course have unique ID & identified by it as well.we can use Associate data structure because here we need to maintin the relationship between students & course. HashTable or HashMap seems to be good fit in case of choosing the data structures.We Will Use Closed Addressing or Open hashing based approach which called saperate chaining.Hash table has two filed in each slot key & pair.Each slot of the HashTable has studentid or course id as key and a pointer to a linked list that contains the value when key hashed to the same location. e.g. Using this approach Whenever collsion occurs in any hashtable e.g. if one student can have more courses they will added to linked list (value part ) pointed by pointer from hash table thus collision will also resolved .similerly can be done for course hashTable.where following operation plays important roles. 1.Lookup requires scanning the list for an entry with the given key. O(n) 2.Insertion requires adding a new entry record to either end of the list belonging to the hashed slot. O(1) or O(n) 3.Deletion requires searching the list and removing the element.O(n) Instead of a list, one can use any other data structure that supports the required operations. For example, by using a self-balancing (AVL or RB) Tree with worst-case time of common hash table operations (insertion, deletion, lookup) can be brought down to O(log n) rather than O(n). However, this approach is only worth the trouble and extra memory if one expects to have many entries hashed to the same slot 1.Lookup requires scanning the tree for an entry with the given key we have to trace whole tree upto depth in case of self balancing tree its O(logn) 2.Insertion requires adding a new entry record to end of the list belonging to the hashed slot.Again we have to search place to insert. 3.Deletion requires searching the list and removing the element.Again we have to search whole tree which takeso O(logn) again. Let me know if anything wrong or better have u in mind ? Thanks Shashank Mani Computer Science BIrla Institute of Technology Mesra. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/Db5pSD-useoJ. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
