[algogeeks] Re: Median Finding algorithms.
Is it acceptable if I find the median in O(logn) time and then, find k numbers closest to the median in O(k) space and O(n) time? _dufus On Aug 30, 4:38 pm, Nagendra Kumar wrote: > Given a set S of n distinct numbers and a positive integer k <= n. > Determine the k numbers in S that are closest to the median of S. > Find an O(n) algorithm --~--~-~--~~~---~--~~ 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 -~--~~~~--~~--~--~---
[algogeeks] Re: N-Ary Tree and Resource management
When we talk of a binary search tree having O(log n) complexity for search, that does assume that the tree is fairly balanced. And of course the that fact we talk of average case. For any tree the worst case would be at least O(n). The whole advantage of using a tree in the 1st place lies in the fact that operations can be done in O(log n) in average case. I don't know of any algo that can do it in O(log n) worst case! :) On Sun, Aug 30, 2009 at 5:05 PM, Dave wrote: > > When you say that checking if any of the ancestors is O(n log n) are > you assuming that the tree is balanced? It wouldn't be O(n log n) if > the tree degenerates into a linked list, would it? So what is your > justification in assuming balance? > > Dave > > On Aug 30, 6:01 pm, Ramaswamy R 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 >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- Hide quoted text - > > > > - Show quoted text - > > > -- 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 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 -~--~~~~--~~--~--~---
[algogeeks] Re: N-Ary Tree and Resource management
Aargh, silly me :D
I think we can assign a prime number, Prime_i > 1 to all the nodes i
in the tree.
Preprocessing : Each node i must maintain a product Pi of all the
prime numbers corresponding to to each of its nodes in the subtree
rooted at node i (including node i). This can be done in O(n) time.
Locking:-
Whenever we lock a particular node i we communicate Pi to the root
node. The root node would keep product (lets call it P, which has
initial value 1) which would be basically product of Pi of all the
nodes i which have been locked. O(1) time.
We also tag each of the ancestor node j of i with value Vj = 2 (a code
which would indicate that a node cannot be locked because one of its
descendent has been locked)...and increment the value lock_count, LCj
(which is initially 0) to indicate how many of its descendent have
been locked O(logn) time.
Tag the node i with value Vi = 1 ( a code which would indicate that
node i has been explicitly locked).
Unlocking:-
Whenever we unlock a particular node i we set the root node's P = P/
Pi. O(1) time.
And decrement lock_count for all of the ancestor nodes j of node i
(LCj--)
If LCj == 0 reset Vj = 0 indicating that no descendent of node j is
currently locked.
Querying:-
To check if node i is currently in a locked set.
Check Vj.
If Vj != 0
{
j is locked.
}
Else
Divide P by Prime_i.
{
If remainder == 0 then node i is in a locked state (basically node
i has one of its ancestor/parent explicitly locked).
otherwise node i is in a unlocked state
}
Phewthat was one long post.
I hope I made myself clear.
_dufus
On Aug 30, 4:21 pm, Nagendra Kumar wrote:
> @Dufus.
> if d is locked then only b,a,g,h cannot be locked .But
> c,f,e,i,j can be locked.
>
>
>
> On Sun, Aug 30, 2009 at 1:41 PM, Dufus wrote:
>
> > Before I propose my solution I have a query.
> > Consider the following tree:-
>
> > a
> > / \
> > b c
> > / \ /
> > d e f
> > / \ /\
> > g h i j
>
> > Initially all the nodes are in unlocked state.
> > Say user choses to lock node d.
> > Now by the given condition:-
> > i) none of its children {g,h} can be locked.
> > ii) none of the nodes which have d as child (ie. ancestors of d) can
> > be locked which are {b,a} // Since a node i cannot be locked if any of
> > its descendant is already locked.
>
> > Also note that a is ancestor of all the nodes in the tree, we end up
> > locking the WHOLE TREE (i.e. once d is locked no other node in the
> > tree can be locked)!!!
>
> > I think something is wrong here.
>
> > Nagendra/Priya any comments?
>
> > _dufus
>
> > On Aug 30, 11:10 am, priya k 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 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 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;
> >>
[algogeeks] Re: N-Ary Tree and Resource management
When you say that checking if any of the ancestors is O(n log n) are you assuming that the tree is balanced? It wouldn't be O(n log n) if the tree degenerates into a linked list, would it? So what is your justification in assuming balance? Dave On Aug 30, 6:01 pm, Ramaswamy R 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 > 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- Hide quoted text - > > - Show quoted text - --~--~-~--~~~---~--~~ 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 -~--~~~~--~~--~--~---
[algogeeks] Re: N-Ary Tree and Resource management
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 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 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 -~--~~~~--~~--~--~---
[algogeeks] Re: N-Ary Tree and Resource management
@Dufus.
if d is locked then only b,a,g,h cannot be locked .But
c,f,e,i,j can be locked.
On Sun, Aug 30, 2009 at 1:41 PM, Dufus wrote:
>
> Before I propose my solution I have a query.
> Consider the following tree:-
>
> a
> / \
> b c
> / \ /
> d e f
> / \ /\
> g h i j
>
> Initially all the nodes are in unlocked state.
> Say user choses to lock node d.
> Now by the given condition:-
> i) none of its children {g,h} can be locked.
> ii) none of the nodes which have d as child (ie. ancestors of d) can
> be locked which are {b,a} // Since a node i cannot be locked if any of
> its descendant is already locked.
>
> Also note that a is ancestor of all the nodes in the tree, we end up
> locking the WHOLE TREE (i.e. once d is locked no other node in the
> tree can be locked)!!!
>
> I think something is wrong here.
>
> Nagendra/Priya any comments?
>
> _dufus
>
>
>
> On Aug 30, 11:10 am, priya k 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 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 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 > > >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 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
-~--~~~~--~~--~--~---
[algogeeks] Median Finding algorithms.
Given a set S of n distinct numbers and a positive integer k <= n. Determine the k numbers in S that are closest to the median of S. Find an O(n) algorithm --~--~-~--~~~---~--~~ 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 -~--~~~~--~~--~--~---
[algogeeks] Re: String- Anagrams.
@Anil: Dictionary is given to you. For each string t in array u = sort(t). if(s == u) print (t). If dictionary has millions of words. So you will go for each word one by one. Then How will make it efficient in terms of time. -Nagendra On Sun, Aug 30, 2009 at 3:56 PM, Anil C R wrote: > > are we like given a dictionary or something? > if we are, its quite simple... > 1. load the dictionary into an array. > 2. sort the given string lexicographically. call it s > 3.t for each string t in the array, >u = sort > if s=u then print t > > then again, if we are asked to print all permutations, we can do it > recursively...or there is Johnson-Trotter: > http://en.wikipedia.org/wiki/Steinhaus%E2%80%93Johnson%E2%80%93Trotter_algorithm > > > > --~--~-~--~~~---~--~~ 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 -~--~~~~--~~--~--~---
[algogeeks] Re: String- Anagrams.
are we like given a dictionary or something? if we are, its quite simple... 1. load the dictionary into an array. 2. sort the given string lexicographically. call it s 3. for each string t in the array, u = sort t if s=u then print t then again, if we are asked to print all permutations, we can do it recursively...or there is Johnson-Trotter: http://en.wikipedia.org/wiki/Steinhaus%E2%80%93Johnson%E2%80%93Trotter_algorithm --~--~-~--~~~---~--~~ 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 -~--~~~~--~~--~--~---
[algogeeks] Re: String- Anagrams.
i think u have to print various permutations of string. On Sun, Aug 30, 2009 at 1:02 PM, Nagendra Kumar wrote: > > Write a method to print all valid anagrams of a string > > -Nagendra > > > > --~--~-~--~~~---~--~~ 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 -~--~~~~--~~--~--~---
[algogeeks] Re: birthday panga
Shiyam's approach sounds like a typical radix tree implementation e.g. Radix tree based routing in networking. that's a good solution for a very big data set and where we do'nt want to store non-used data portions. On Fri, Aug 28, 2009 at 6:42 PM, Shyam wrote: > > I think we can have a BST that is keyed based on birth day date and > month this is done as follows.. If i have a birth day on Jan 2 nd then > key value is 2(2nd day of the year) if birthday is feb 14th then its 45 > (31+14).The tree nodes can have a count of number of people whose > b'days are on that day or you can have a ptr to linked list that has > names of persons who have bdays on same day from nodes in BST. > > Hope it was helpful > Cheers!! > Shiyam > > -- "Subvert the paradigm." - C.K. Prahlad --~--~-~--~~~---~--~~ 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 -~--~~~~--~~--~--~---
[algogeeks] String- Anagrams.
Write a method to print all valid anagrams of a string -Nagendra --~--~-~--~~~---~--~~ 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 -~--~~~~--~~--~--~---
[algogeeks] Re: N-Ary Tree and Resource management
@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 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 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 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
>> > 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 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
-~--~~~~--~~--~--~---
[algogeeks] Re: N-Ary Tree and Resource management
Before I propose my solution I have a query.
Consider the following tree:-
a
/ \
bc
/ \/
d e f
/ \ /\
g h i j
Initially all the nodes are in unlocked state.
Say user choses to lock node d.
Now by the given condition:-
i) none of its children {g,h} can be locked.
ii) none of the nodes which have d as child (ie. ancestors of d) can
be locked which are {b,a} // Since a node i cannot be locked if any of
its descendant is already locked.
Also note that a is ancestor of all the nodes in the tree, we end up
locking the WHOLE TREE (i.e. once d is locked no other node in the
tree can be locked)!!!
I think something is wrong here.
Nagendra/Priya any comments?
_dufus
On Aug 30, 11:10 am, priya k 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 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 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 > >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 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
-~--~~~~--~~--~--~---
