Re: [algogeeks] Re: MS QUESTION_LINKED LIST
@Algo-Geek : this wont work , as requirement of the problem is different . even i misunderstood the problem and posted the algo above doing the same as you have mentioned , but question doesn't say next larger element on right side. It just ask for next larger element cud be on left or cud be on right. so solution is merge sort. On Thu, Mar 29, 2012 at 8:45 AM, Algo-Geek wrote: > using stack, the problem can be solved in O(n) time. here is the algo :- > 1- push first node in stack. mark next node as current > 2 - start from current element and check if the node on top of stack is > smaller than current , then pop the node and make its next_largest pointer > set to current. Do this until the stack is empty or the node on top of > stack becomex greater than current. > 3- If the node on top of stack is greater than current, push the current > node on top of the stack. Move current to current->next > 4 - Do this iteration for all nodes until current becomes NULL > 5 - if stack is empty,we are done else pop each element of stack and make > its next_largest point to NULL > > On Saturday, 24 March 2012 00:50:43 UTC+5:30, ATul SIngh wrote: >> >> Given a linked list with each node having two pointers : one pointing to >> next node & other to null; >> how will u point the second pointer to next larger no. and return the >> pointer to smallest node >> >> >> >> -- >> ATul Singh | Final Year | Computer Science & Engineering | NIT >> Jalandhar | 9530739855 | >> > -- > 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/-/RJYgDkGw6NsJ. > > 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. > -- 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.
[algogeeks] Re: MS QUESTION_LINKED LIST
using stack, the problem can be solved in O(n) time. here is the algo :- 1- push first node in stack. mark next node as current 2 - start from current element and check if the node on top of stack is smaller than current , then pop the node and make its next_largest pointer set to current. Do this until the stack is empty or the node on top of stack becomex greater than current. 3- If the node on top of stack is greater than current, push the current node on top of the stack. Move current to current->next 4 - Do this iteration for all nodes until current becomes NULL 5 - if stack is empty,we are done else pop each element of stack and make its next_largest point to NULL On Saturday, 24 March 2012 00:50:43 UTC+5:30, ATul SIngh wrote: > > Given a linked list with each node having two pointers : one pointing to > next node & other to null; > how will u point the second pointer to next larger no. and return the > pointer to smallest node > > > > -- > ATul Singh | Final Year | Computer Science & Engineering | NIT Jalandhar > | 9530739855 | > -- 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/-/RJYgDkGw6NsJ. 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.
Re: [algogeeks] [URGENNT] : naukri.com paper pattern
10 multiple choice questions on C : very easy , Kanetkar will suffice. Aptitude : subjective , with mostly mathematical puzzles . Lengthy due to time consuming problems. Focus on accuracy .Series completion, Time speed distance,permutation and combination is what i can recall in the aptitude paper. On Tue, Mar 27, 2012 at 8:07 PM, aditya gupta wrote: > Hi all, > > nauri.com is visiting at my friend's college , can someone plz tell the > pattern of its paper?? > > -- > 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. > -- 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.
Re: [algogeeks] Re: need suggestions
Thanks Don! On Wed, Mar 28, 2012 at 7:09 AM, Don wrote: > Let's say that you have 16 processors. You are trying to solve the 0-1 > knapsack problem for 40 items. > Each item i has size S[i], and you need to find the subset of items > which sums as close to T as possible without exceeding T. > > Pick four of items. There are 16 possible combinations of those items: > (none of those 4 items included) > 0001 (only item #1 included) > ... > (all four items included) > > You will essentially ask each of the 16 processors to solve the > knapsack problem for 36 items, starting with one of the 16 possible > combiations of the 4 items. Processor 0 will start with none of the > first 4 items. Processor 15 will start with all of them, and the other > processors will start with a different subset of the items. It may > seem like solving the problem for 36 items is not much different than > 40, but it requires 1/16th of the work. When each processor is done, > it knows the best solution including its assigned items from among the > first 4 items. To find the overall best solution you just need to > compare the 16 solutions and pick the one best. > > A possible improvement is to divide up the problem into more parts and > farm them out to the processors as they become available. This would > work better if you don't have a power of 2 number of processors. It > also would reduce the tendancy for some processors to finish early and > sit idle while one or two take longer to finish their portion of the > work. > > Don > > On Mar 28, 9:51 am, Arun Vishwanathan wrote: > > @Don: I am not clear with your explanation. Please can you give me an > > example? > > > > > > > > > > > > On Wed, Mar 28, 2012 at 6:19 AM, Don wrote: > > > If you have n processors, start with the n possible ways to select > > > from log2 n items. Assign each processor to find a solution based on > > > the resulting subset of remaining items. Each processor should be able > > > to work fairly independently, and when they are done, they can compare > > > results and find the best one. > > > Don > > > > > On Mar 27, 10:47 pm, Arun Vishwanathan wrote: > > > > Hi all, > > > > > > I am planning to implement a parallel version of the 0-1 knapsack > > > problem. > > > > I tried reading up a bit and there are few suggestions here and > there. > > > > However I would like to know if anyone has an idea or links that I > cud > > > > refer for this? The main problem in parallelizing a DP algorithm is > the > > > > dependencies due to recursion? Is there an effective strategy for > this?? > > > > Using shared memory or message passing approach? > > > > > > Arun > > > > > -- > > > 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. > > > > -- > > "People often say that motivation doesn't last. Well, neither does > bathing > > - that's why we recommend it daily."- 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?hl=en. > > -- "People often say that motivation doesn't last. Well, neither does bathing - that's why we recommend it daily." -- 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.
[algogeeks] Re: need suggestions
Let's say that you have 16 processors. You are trying to solve the 0-1 knapsack problem for 40 items. Each item i has size S[i], and you need to find the subset of items which sums as close to T as possible without exceeding T. Pick four of items. There are 16 possible combinations of those items: (none of those 4 items included) 0001 (only item #1 included) ... (all four items included) You will essentially ask each of the 16 processors to solve the knapsack problem for 36 items, starting with one of the 16 possible combiations of the 4 items. Processor 0 will start with none of the first 4 items. Processor 15 will start with all of them, and the other processors will start with a different subset of the items. It may seem like solving the problem for 36 items is not much different than 40, but it requires 1/16th of the work. When each processor is done, it knows the best solution including its assigned items from among the first 4 items. To find the overall best solution you just need to compare the 16 solutions and pick the one best. A possible improvement is to divide up the problem into more parts and farm them out to the processors as they become available. This would work better if you don't have a power of 2 number of processors. It also would reduce the tendancy for some processors to finish early and sit idle while one or two take longer to finish their portion of the work. Don On Mar 28, 9:51 am, Arun Vishwanathan wrote: > @Don: I am not clear with your explanation. Please can you give me an > example? > > > > > > On Wed, Mar 28, 2012 at 6:19 AM, Don wrote: > > If you have n processors, start with the n possible ways to select > > from log2 n items. Assign each processor to find a solution based on > > the resulting subset of remaining items. Each processor should be able > > to work fairly independently, and when they are done, they can compare > > results and find the best one. > > Don > > > On Mar 27, 10:47 pm, Arun Vishwanathan wrote: > > > Hi all, > > > > I am planning to implement a parallel version of the 0-1 knapsack > > problem. > > > I tried reading up a bit and there are few suggestions here and there. > > > However I would like to know if anyone has an idea or links that I cud > > > refer for this? The main problem in parallelizing a DP algorithm is the > > > dependencies due to recursion? Is there an effective strategy for this?? > > > Using shared memory or message passing approach? > > > > Arun > > > -- > > 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. > > -- > "People often say that motivation doesn't last. Well, neither does bathing > - that's why we recommend it daily."- 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?hl=en.
Re: [algogeeks] Re: need suggestions
@Don: I am not clear with your explanation. Please can you give me an example? On Wed, Mar 28, 2012 at 6:19 AM, Don wrote: > If you have n processors, start with the n possible ways to select > from log2 n items. Assign each processor to find a solution based on > the resulting subset of remaining items. Each processor should be able > to work fairly independently, and when they are done, they can compare > results and find the best one. > Don > > On Mar 27, 10:47 pm, Arun Vishwanathan wrote: > > Hi all, > > > > I am planning to implement a parallel version of the 0-1 knapsack > problem. > > I tried reading up a bit and there are few suggestions here and there. > > However I would like to know if anyone has an idea or links that I cud > > refer for this? The main problem in parallelizing a DP algorithm is the > > dependencies due to recursion? Is there an effective strategy for this?? > > Using shared memory or message passing approach? > > > > Arun > > -- > 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. > > -- "People often say that motivation doesn't last. Well, neither does bathing - that's why we recommend it daily." -- 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.
[algogeeks] Re: need suggestions
If you have n processors, start with the n possible ways to select from log2 n items. Assign each processor to find a solution based on the resulting subset of remaining items. Each processor should be able to work fairly independently, and when they are done, they can compare results and find the best one. Don On Mar 27, 10:47 pm, Arun Vishwanathan wrote: > Hi all, > > I am planning to implement a parallel version of the 0-1 knapsack problem. > I tried reading up a bit and there are few suggestions here and there. > However I would like to know if anyone has an idea or links that I cud > refer for this? The main problem in parallelizing a DP algorithm is the > dependencies due to recursion? Is there an effective strategy for this?? > Using shared memory or message passing approach? > > Arun -- 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.
