[algogeeks] Re: In place sorting
Use inplace merge algorithms along with merge sort. http://www.logiccoder.com/Downloads/krnrd20.pdf -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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: In place sorting
hi , this is not a research kind of problem i expect a simple answer. On Wed, Dec 29, 2010 at 2:33 PM, juver++ avpostni...@gmail.com wrote: Use inplace merge algorithms along with merge sort. http://www.logiccoder.com/Downloads/krnrd20.pdf -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@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: In place sorting
please visit this blog http://code-forum.blogspot.com/2010/12/in-place-merge-sort.html to see a simple and straight solution to this problem.however if first array does not have enough space then also it can be done inplace and still lots of research is going on for this. On Dec 29, 2:25 pm, monty 1987 1986mo...@gmail.com wrote: hi , this is not a research kind of problem i expect a simple answer. On Wed, Dec 29, 2010 at 2:33 PM, juver++ avpostni...@gmail.com wrote: Use inplace merge algorithms along with merge sort. http://www.logiccoder.com/Downloads/krnrd20.pdf -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@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: In place sorting
@vishal thanx On Wed, Dec 29, 2010 at 3:39 PM, vishal raja vishal.ge...@gmail.com wrote: Perform simple merging taking the ends of the list. So You compare the last elements of both the list which ever is larger you copy that at the end of the first array and so on. you got to maintain three pointer , two for the lists and the third one for the position it should be placed. time complexity will be O(m+n) On Wed, Dec 29, 2010 at 2:55 PM, monty 1987 1986mo...@gmail.com wrote: hi , this is not a research kind of problem i expect a simple answer. On Wed, Dec 29, 2010 at 2:33 PM, juver++ avpostni...@gmail.com wrote: Use inplace merge algorithms along with merge sort. http://www.logiccoder.com/Downloads/krnrd20.pdf -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@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] combinations problem
you are given a string.It may have repeated characters.each character has it's own weight.find combination of characters whose sum value is equal to given value. ex: given string 'abcbacbabcc' weight of each character a-5,b-4,c-6. character combination which gives sum 15 is 'aaa' -- Thank You -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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: combinations problem
Is'nt this just a knapsack problem! On Dec 29, 3:45 pm, rajeev kumar rajeevprasa...@gmail.com wrote: you are given a string.It may have repeated characters.each character has it's own weight.find combination of characters whose sum value is equal to given value. ex: given string 'abcbacbabcc' weight of each character a-5,b-4,c-6. character combination which gives sum 15 is 'aaa' -- Thank You -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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: combinations problem
String gives no of occurrences of each character.no of times you select a character should be less than the no of times it appears in the string. ex: given string 'abcbacbabcc' has 3 a's, 4b's, 4 c's. resulting string should have a less than 3 times,b less than 4 times and c less than 4 times. On Wed, Dec 29, 2010 at 4:25 PM, vishal raja vishal.ge...@gmail.com wrote: What's the relation with the given string. I could'nt get you completely. On Wed, Dec 29, 2010 at 4:18 PM, suhash suhash.venkat...@gmail.comwrote: Is'nt this just a knapsack problem! On Dec 29, 3:45 pm, rajeev kumar rajeevprasa...@gmail.com wrote: you are given a string.It may have repeated characters.each character has it's own weight.find combination of characters whose sum value is equal to given value. ex: given string 'abcbacbabcc' weight of each character a-5,b-4,c-6. character combination which gives sum 15 is 'aaa' -- Thank You -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thank You Rajeev Kumar -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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: combinations problem
It's a knapsack problem with bounds. Solve it using DP - for each state keep number of used characters and preserve to exceed the bounds. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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: combinations problem
@juver++ can you elaborate this sentence 'It's a knapsack problem with bounds. Solve it using DP' or send me any link which has good explanation. On Wed, Dec 29, 2010 at 4:52 PM, vishal raja vishal.ge...@gmail.com wrote: i think we don't need to store the total no. of occurance of any character. we can think of it as a classic knapSack, We have n ( size of the string) items, does'nt matter if they repeat or not . We don't have to keep a track how many of a char we have used as we have only options in this array , just take every index item as different item, that will automatcally do this. On Wed, Dec 29, 2010 at 4:46 PM, juver++ avpostni...@gmail.com wrote: It's a knapsack problem with bounds. Solve it using DP - for each state keep number of used characters and preserve to exceed the bounds. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thank You Rajeev Kumar -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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: combinations problem
Yes, it's true. But we should process DP in the following order not to take one element more than once. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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: combinations problem
@juver, ofcourse , and that's not a big deal. On Wed, Dec 29, 2010 at 5:11 PM, juver++ avpostni...@gmail.com wrote: Yes, it's true. But we should process DP in the following order not to take one element more than once. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@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: combinations problem
dp[i][j] - true, if there is a way to have sum j after processing the first i elements, and false otherwise. so transitions wil be: dp[i][j] = dp[i - 1][j] OR dp[i - 1][j - weight[i]], (OR means logical or),first term means that we don't want to use i-th character, second - we use it, so the sum decreases. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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: combinations problem
It's not a big problem when you use 2D matrix instead of 1D for the DP :) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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] Strings search problem
Given set of words, find an area of the text where these words are as close to each other as possible. Distance is measured on number of words. e.g. for words [rat”, “jat”, “pat”] and text “rat stop the pat blah blah jat by pat jat tra la la” such area is “cat by mat bat” -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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] sudhir mishra wants to chat
--- sudhir mishra wants to stay in better touch using some of Google's coolest new products. If you already have Gmail or Google Talk, visit: http://mail.google.com/mail/b-62d5befb93-c4270e4073-gZW-XtMwbOw3w3XU9CHGZ6uR5ZQ You'll need to click this link to be able to chat with sudhir mishra. To get Gmail - a free email account from Google with over 2,800 megabytes of storage - and chat with sudhir mishra, visit: http://mail.google.com/mail/a-62d5befb93-c4270e4073-gZW-XtMwbOw3w3XU9CHGZ6uR5ZQ Gmail offers: - Instant messaging right inside Gmail - Powerful spam protection - Built-in search for finding your messages and a helpful way of organizing emails into conversations - No pop-up ads or untargeted banners - just text ads and related information that are relevant to the content of your messages All this, and its yours for free. But wait, there's more! By opening a Gmail account, you also get access to Google Talk, Google's instant messaging service: http://www.google.com/talk/ Google Talk offers: - Web-based chat that you can use anywhere, without a download - A contact list that's synchronized with your Gmail account - Free, high quality PC-to-PC voice calls when you download the Google Talk client We're working hard to add new features and make improvements, so we might also ask for your comments and suggestions periodically. We appreciate your help in making our products even better! Thanks, The Google Team To learn more about Gmail and Google Talk, visit: http://mail.google.com/mail/help/about.html http://www.google.com/talk/about.html (If clicking the URLs in this message does not work, copy and paste them into the address bar of your browser). -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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] Divide an array into two equal subsets
But the same solution I've given above can give you the solution for this problem . In the formed table of P[i][j] , you can take another variable attached to it as count[i][j] for how many items we have selected yet. So you gotta find , the max. value of j which has count = 50. count[i][j] = count[i-1][j] if P(i-1,j) ==1 count[i][j] = count[i-1][j-a[i]] if P(i-1,j-a[i]) ==1 else count[i][j] = 0 On Thu, Dec 30, 2010 at 11:42 AM, vishal raja vishal.ge...@gmail.comwrote: yeah, My bad. Missed that. On Wed, Dec 29, 2010 at 10:52 PM, Wladimir Tavares wladimir...@gmail.com wrote: Sum up all the number and divide by 2 Using the algorithm subset problem to find a number close to median Wladimir Araujo Tavares *Federal University of Ceará * On Wed, Dec 29, 2010 at 2:07 PM, Ankur Khurana ankur.kkhur...@gmail.comwrote: How will you divide and array of approx 100 elements into two sub sets of 50 each such that the difference between both the subsets is the minimum possible one . . Thanks in advance . Ankur -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@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] Divide an array into two equal subsets
Thanks everybody for wonderful support and special thanks to Vishal raja. . But i was bit apprehensive about your last solution . . i will test it :) and let you know as well . Thanks . . . . On Thu, Dec 30, 2010 at 11:52 AM, vishal raja vishal.ge...@gmail.com wrote: But the same solution I've given above can give you the solution for this problem . In the formed table of P[i][j] , you can take another variable attached to it as count[i][j] for how many items we have selected yet. So you gotta find , the max. value of j which has count = 50. count[i][j] = count[i-1][j] if P(i-1,j) ==1 count[i][j] = count[i-1][j-a[i]] if P(i-1,j-a[i]) ==1 else count[i][j] = 0 On Thu, Dec 30, 2010 at 11:42 AM, vishal raja vishal.ge...@gmail.com wrote: yeah, My bad. Missed that. On Wed, Dec 29, 2010 at 10:52 PM, Wladimir Tavares wladimir...@gmail.com wrote: Sum up all the number and divide by 2 Using the algorithm subset problem to find a number close to median Wladimir Araujo Tavares Federal University of Ceará On Wed, Dec 29, 2010 at 2:07 PM, Ankur Khurana ankur.kkhur...@gmail.com wrote: How will you divide and array of approx 100 elements into two sub sets of 50 each such that the difference between both the subsets is the minimum possible one . . Thanks in advance . Ankur -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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 algoge...@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 algoge...@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 algoge...@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.
