[algogeeks] Puzzle Digest Of The Week 9May - 13May
*Hi* *Puzzle Digest Of The Week 9May - 13May* * http://dailybrainteaser.ablogspot.com/2011/05/fun-math-puzzle-13-may.html?lavesh=lavesh * * * *http://dailybrainteaser.blogspot.com/2011/05/who-is-shortest-12-may.html?** lavesh=lavesh* * * *http://dailybrainteaser.blogspot.com/2011/05/fun-teaser-11-may.html?** lavesh=lavesh* * * *http://dailybrainteaser.blogspot.com/2011/05/maths-trick-teaser-9-may.html? **lavesh=lavesh* * * * http://dailybrainteaser.blogspot.com/2011/05/number-sequence-puzzle-9-may.html ?**lavesh=lavesh* * * *Please subscribe and follow this blog to show your liking to the blog.* -- 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: Inversion Count
@all i have posted the solution of same problem few times back , search in group thread i used BST using that inversion count can be calculated in O(nlogn) if you found any error on that then let me know Thanks Shashank CSE,BIT Mesra -- 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] Google Q
not clear, can u elaborate.. Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Fri, May 13, 2011 at 7:15 PM, Bhavesh agrawal agr.bhav...@gmail.comwrote: This problem can be solved using 2 heaps and the median can always be accessed in O(1) time ,the first node. -- 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] Puzzle
Each team plays a total of 14 matches. Top 50% teams(4 out of 8) qualify for the semis. Thus, u must win more than 50% matches to be sure to get into semis. Thus, 8 is the answer. On Fri, May 13, 2011 at 12:14 AM, amit amitjaspal...@gmail.com wrote: Consider a series in which 8 teams are participating. each team plays twice with all other teams. 4 of them will go to the semi final.How many matches should a team win, so that it will ensure that it will go to semi finals.? -- 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.
[algogeeks] Re: Google Q
@Ashish: The idea is to keep two heaps, a max-heap of the smallest half of the elements and a min-heap of the largest elements. You insert incoming elements into the appropriate heap. If the result is that the number of elements in the two heaps differs by more than 1, then you move the top element from the longer heap into the other one, thereby equalzing the number of elements. Thus, inserting an element is an O(log n) operation. To get the median, it is the top element of the longer heap, or, if the heaps are of equal length, it is the average of the two top elements. This is O(1). Dave On May 14, 8:34 am, Ashish Goel ashg...@gmail.com wrote: not clear, can u elaborate.. Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Fri, May 13, 2011 at 7:15 PM, Bhavesh agrawal agr.bhav...@gmail.comwrote: This problem can be solved using 2 heaps and the median can always be accessed in O(1) time ,the first node. -- 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.- 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: Google Q
Will not a balanced binary tree do the job ? if we will pick the root each time for the median. On Sat, May 14, 2011 at 9:10 PM, Dave dave_and_da...@juno.com wrote: @Ashish: The idea is to keep two heaps, a max-heap of the smallest half of the elements and a min-heap of the largest elements. You insert incoming elements into the appropriate heap. If the result is that the number of elements in the two heaps differs by more than 1, then you move the top element from the longer heap into the other one, thereby equalzing the number of elements. Thus, inserting an element is an O(log n) operation. To get the median, it is the top element of the longer heap, or, if the heaps are of equal length, it is the average of the two top elements. This is O(1). Dave On May 14, 8:34 am, Ashish Goel ashg...@gmail.com wrote: not clear, can u elaborate.. Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Fri, May 13, 2011 at 7:15 PM, Bhavesh agrawal agr.bhav...@gmail.com wrote: This problem can be solved using 2 heaps and the median can always be accessed in O(1) time ,the first node. -- 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.- 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. -- regards, chinna. -- 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] first fit bin packing
i think we can use heaps for this problem..bring to the root which has capacity to hold and pick the root each time. If the root cannot accomodate then no other node will be able to accomodate. On Sat, May 14, 2011 at 1:26 AM, MK stardust...@gmail.com wrote: Consider the first fit strategy for online bin packing. So if you have N bins numbered 1, 2, 3..N and you are given value V, you scan them from left to right and insert V into the first bin that currently has enough capacity. In the naieve case, N insertions will take O(N^2) time. How can this be done in NlogN time? -- 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. -- regards, chinna. -- 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: A* search
After expanding B, the border is with G (25) Node G is the smallest of the border. You finish the algorithm when the node G is the smallest of the border not when he enters the boundary Yes, we finish with G=25, but we still have G=35 first. This is all right, since I understand now that a consistent heuristic (as the one in my example graph) only guarantees when a node is EXPANDED, the optimal path to it has already been found. So supposed we have another node after G, we when next expand G, we would already have G = 25. The statement about consistent heuristic in the book (Russll Norvig): ...to ensure that the optimal path to any repeated state is always the first one followed. made me thought that we should always have G=25 first whenever we have a consistent heuristic, this is just my misrepresentation. thanks for your reply. wenduan. Wladimir Araujo Tavares Federal University of Ceará On Fri, May 13, 2011 at 6:14 PM, xuwenduan xuwend...@gmail.com wrote: I have an answer for my own question: I think I've misunderstood the statement in the book, which says: ...to ensure that the optimal path to any repeated state is always the first one followed. in the above example, we haven't actually started to follow (expand) G yet, so the statement about consistency is still valid. wenduan On May 13, 7:56 pm, eric xuwend...@gmail.com wrote: Hi All, A* search with consistent heuristics is supposed to ensure that an optimal path to a repeated state is always the first path generated, but consider the following example: /---4---A(h=15)--30--\ S(h=18) G (h=0) \ ---5---B(h=17)--20--/ where S and G are the start and goal nodes respectively, in this case G is a repeated state which is also the goal state, but carry out A* on the above graph, we get: Expand S: get children A (f = 4 + 15 = 19) and B (f = 5 + 17 = 22), and A has a smaller f value, we next expand A Expand A: get child G (f = 34 + 0 = 34) at this point we obviously have a sub-optimal path to G with cost 34 the optimal cost of 5 + 20 = 25? Is this just a special case where the goal is also a repeated state or am I missing something here? Thanks in advance. e. -- 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. -- 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: Google Q
@Pacific: A balanced binary tree is commonly defined as a binary tree in which the height of the two subtrees of every node never differ by more than 1. Thus, there could be more nodes in one subtree than in the other. E.g., a balanced binary tree with 11 nodes could have 7 nodes in the left subtree and only 3 nodes in the right subtree. Thus, the root would not be the median. An additional condition is needed: the number of nodes in the left subtree differs by at most one from the number of nodes in the right subtree. In fact, given that the heap structure is a balanced binary tree structure with implicit pointers to the left and right subtrees, the two-heap algorithm I described results in a balanced binary tree satisfying this additional condition, with an implicit root node equal to the median. Dave On May 14, 11:55 am, pacific :-) pacific4...@gmail.com wrote: Will not a balanced binary tree do the job ? if we will pick the root each time for the median. On Sat, May 14, 2011 at 9:10 PM, Dave dave_and_da...@juno.com wrote: @Ashish: The idea is to keep two heaps, a max-heap of the smallest half of the elements and a min-heap of the largest elements. You insert incoming elements into the appropriate heap. If the result is that the number of elements in the two heaps differs by more than 1, then you move the top element from the longer heap into the other one, thereby equalzing the number of elements. Thus, inserting an element is an O(log n) operation. To get the median, it is the top element of the longer heap, or, if the heaps are of equal length, it is the average of the two top elements. This is O(1). Dave On May 14, 8:34 am, Ashish Goel ashg...@gmail.com wrote: not clear, can u elaborate.. Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Fri, May 13, 2011 at 7:15 PM, Bhavesh agrawal agr.bhav...@gmail.com wrote: This problem can be solved using 2 heaps and the median can always be accessed in O(1) time ,the first node. -- 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.-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. -- regards, chinna.- 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: MATHS TRICK TEASER 9 may
superb answer by dave On Sun, May 15, 2011 at 8:27 AM, Amol Sharma amolsharm...@gmail.com wrote: like utkarsh answer -- Amol Sharma Second Year Student Computer Science and Engineering MNNIT Allahabad On Wed, May 11, 2011 at 12:58 AM, Dave dave_and_da...@juno.com wrote: 19 = XIX in Roman Numerals. Take 1 = I away and you have XX = 20. Dave On May 10, 2:09 am, Lavesh Rawat lavesh.ra...@gmail.com wrote: *MATHS TRICK TEASER * * * ** *Prove that taking away 1 from 19 makes 20. * *Update Your Answers at* : Click Here http://dailybrainteaser.blogspot.com/2011/05/maths-trick-teaser-9-may... Solution: Will be updated after 1 day -- Never explain yourself. Your friends don’t need it and your enemies won’t believe it . -- 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. -- 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.
