Rama, can you explain your O(1) time and additional O(n) space algorithm to check if a node is in a locked state. Trust me it is more difficult then it sounds.
_dufus On Aug 31, 4:01 am, Ramaswamy R <[email protected]> wrote: > To begin with I find the invariant doesn't hold in the system progressively. > Forget about islock and assume that we only do lock / unlock. Given that a > node cannot be locked if any of its descendants / ancestors is locked. It is > never possible for the tree to enter a state where any of the descendant of > a locked node is locked. > > If that invariant holds then all we need to check is if any of the ancestors > are locked, which is O(log n). O(1) would either require hash table (and > O(n) storage) unless we choose to replicate the lock state in all of the > ancestors as well (which is a pretty ugly solution considering what unlock > would have to do). > > If we can supplement the tree node with a lock status and pointer to child > (only used while unlocking) which is locked we should be able to do it all > in the asked for complexities :). Ugly but possible. Of course there is an > O(n) extra storage. > > On Sat, Aug 29, 2009 at 11:05 AM, nagendra kumar > <[email protected]>wrote: > > > > > > > Given a n-ary tree of resources arranged hierarchically. A process > > needs to lock a resource node in order to use it. But, > > A node cannot be locked if any of its descendant or ancestor is > > locked. > > I was supposed to > > -> write the structure of node > > -> write codes for > > -> islock()- returns true if a given node is locked and false if it is > > not > > -> lock()- locks the given node if possible and updates lock > > information > > -> unlock()- unlocks the node and updates information. > > Codes should be : > > Islock –O(1) > > Lock()- O(log n) > > unLock()- O(log n) > > -- > Yesterday is History. > Tomorrow is a Mystery. > Today is a Gift! That is why it is called the Present :). > > http://sites.google.com/site/ramaswamyr --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. 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 -~----------~----~----~----~------~----~------~--~---
