One (compressed-optional) prefix trie with each course ptrs to students and another prefix tree for students having ptrs to courses. Guaranteed O(m) search time instead of O(n*m) if using hash table where m avg size of word at hand to be compared to n nodes.
On Sun, Oct 30, 2011 at 7:31 PM, WgpShashank <shashank7andr...@gmail.com>wrote: > 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 algogeeks@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- Mohit -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
