@Priya:
How it will come to O(log n). The statement
while(cond)
m=m->parent;
will covers top to bottom in a tree.
whick will be O(n). explain ur logic hoiw is it O(log n).
-Nagendra.
On Sun, Aug 30, 2009 at 11:40 AM, priya k<[email protected]> wrote:
> @Dufus: You mean to say do preprocessing and hash all the nodes that cannot
> be locked, if am not wrong. And again, Everytime we lock a node, we need to
> update the hash and that would be O(n) worst case. Can we do anything better
> ?
>
> --Priya
>
> On Sun, Aug 30, 2009 at 10:26 AM, Dufus <[email protected]> wrote:
>>
>> Priya, as mentioned by you your isLock() takes O(logn) time.
>> We need to use Hash table as auxillary DS for O(1) query time.
>>
>> _dufus
>>
>> On Aug 30, 8:35 am, priya k <[email protected]> wrote:
>> > // Data Structure for the n-ary tree
>> >
>> > struct node
>> > {
>> > int data;
>> > node * child[m];
>> > bool lockFlag; // Indicates if a node is locked or not
>> > node *parent; //Holds the immediate parent of the node
>> > int LockCount; //Holds how many nodes arrested this node
>> >
>> > };
>> >
>> > // Takes logm(N) in the worst case
>> >
>> > bool check(node *NodeToBeLocked)
>> > {
>> > node *m=NodeToBeLocked;
>> >
>> > if(m->flag==true || m->LockCount>0)
>> > return false; // since the node is already locked or any of its
>> > subtrees already locked, return false
>> >
>> > while(m && !m->lockFlag)
>> > m=m->parent;
>> >
>> > if(m && m->lockFlag)
>> > return false; // if any of its ancestors have been already locked
>> >
>> > return true;
>> >
>> > }
>> >
>> > // Takes logm(N) in the worst case
>> >
>> > bool lock(node *NodeToBeLocked)
>> > {
>> > if(check(NodeToBeLocked)) // If true, Node is free to be locked
>> > {
>> > node *m=NodeToBeLocked;
>> > m->lock=true;
>> > node *prevChild=m;
>> > m=m->parent;
>> > while(m)
>> > {
>> > m->LockCount++;
>> > prevChild=m;
>> > m=m->parent;
>> > }
>> > return true;
>> > }
>> > return false; //err.. cannot be locked
>> >
>> > }
>> >
>> > // Takes logm(N) in the worst case
>> >
>> > bool unlock(node *NodeToBeUnLocked)
>> > {
>> > node *m=NodeToUnBeLocked;
>> > m->lock=false; // Unlock the Node
>> > node *prevChild=m;
>> > m=m->parent;
>> > while(m)
>> > {
>> > m->LockCount--;
>> > prevChild=m;
>> > m=m->parent;
>> > }
>> >
>> > }
>> >
>> > Thanks,
>> > Priya
>> >
>> > On Sat, Aug 29, 2009 at 11:35 PM, 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)
>>
>>
>
>
> >
>
--~--~---------~--~----~------------~-------~--~----~
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
-~----------~----~----~----~------~----~------~--~---
