Re: [algogeeks] Most Optimal Palindrome?
You don't need to reverse anything. You reverse half the number and then compare positions, why not just compare things straight away? Also note that your solution is not n/2. Should the length be n it would be at least n operations. n/2 to reverse half the string and then n/2 comparisons. However, your method is depedent on the number of digits in a number and a number n does not have n digits in it, it will be approximately log n. See here for more information http://math.stackexchange.com/questions/231742/proof-how-many-digits-does-a-number-have-lfloor-log-10-n-rfloor-1 On 12 October 2014 21:06, Rishav Mishra rishav.mish...@gmail.com wrote: Hi everyone, I was recently asked a question to find the most optimal solution to finding if a given number 'n' is a palindrome or not. I suggested reversing the first half of the number and comparing it with the second half, giving complexity O (n/2). He still seemed unsatisfied and wanted me to further optimize it. Any clues on how to optimize this simple question further!? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks] Re: I am developing a new algorithm constructing Suffix Array and I want some knowledge on genome
Almost certainly yes, but that website also gives the links to the files used in the benchmark. So you can just check yourself. On 8 August 2014 10:23, wtx...@gmail.com wtx...@gmail.com wrote: Here is Google Suffix array testing result website. https://sites.google.com/site/yuta256/sais I want to know if the testing corpus contains DNA bio information? It has a file named chr22.dna. Is it chromosome 22 DNA? Weng On Thursday, August 7, 2014 6:26:19 PM UTC-7, wtx...@gmail.com wrote: I am developing a new algorithm constructing Suffix Array that is not based on KA, AS-IS or Skew algorithms. Its performance depends on Max(LCPs) (the largest of longest common prefix) of the suffix array. It will work perfectly for 8-bit character string without any code change. It needs some refine to deal with genome code. I want to know some special knowledge about genome DNA testing code. I know nothing about DNA sequence and biology. 1. Which are the best books about genome DNA sequence processing suitable for me who is developing a new algorithm constructing suffix array and want the algorithm better workable for DNA analyses. 2. I want to know if there is any algorithm constructing Suffix Array whose performance depends on Max(LCPs)? 3. Genome DNA testing file contains only 4 characters: A,C,G and T. Is it right? I found another char U in RNA. Does the file still contain 4 characters? 4. If the number of chars in a file is limited to 4, and all repeatable patterns are known, I can specially design some technical refinement to improve my algorithm performance. I want know, in addition to 1 char, 2 chars, 3 chars and 4 chars repentance, 5 chars or more repeatable sequence are common? And if common, the largest common chars repentance contains how many different chars? 1 char repentance: ... 2 char repentance: ACACACACACACACA... Thank you. Weng -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks] Re: I am developing a new algorithm constructing Suffix Array and I want some knowledge on genome
It's just a plain text file, use whatever text editor you like On 8 August 2014 10:42, wtx...@gmail.com wtx...@gmail.com wrote: *I downloaded the file chr22.dna. I don't know what software should be used to browse the contents and view its data pattern. This file is really what I need to view its data pattern.* *Please help tell me what **software should be used to browse the contents.* *Weng* *Can't Open .DNA Files ?*You need to clean your Windows Registry and repair the Broken Windows File Associations. RegCure is the tool that automates this tedious task... *[image: Warning]There is a 97% chance your computer has registry problems.* If you can't open/run .DNA files chances are you are experiencing Registry problems. To prevent further corruption of registry error pile ups that slow down your PC, it is *highly recommended* that this errors should be fixed immediately. Not repairing this kind of errors can lead to system crashes, blue screens, and hardware failure.. Don't waste any more time, use the RegCure http://www.filedocs.net/download_RegCure.php tool and your computer will be humming in less than 2 minutes. (This version includes all the latest security fixes and updates.) [image: Free Download Now!] http://www.filedocs.net/download_RegCure.php File size: 4.9MB, Download time: 1min (Cable/DSL) - [image: 12] *E*asily Open/Repair .DNA files! On Thursday, August 7, 2014 6:26:19 PM UTC-7, wtx...@gmail.com wrote: I am developing a new algorithm constructing Suffix Array that is not based on KA, AS-IS or Skew algorithms. Its performance depends on Max(LCPs) (the largest of longest common prefix) of the suffix array. It will work perfectly for 8-bit character string without any code change. It needs some refine to deal with genome code. I want to know some special knowledge about genome DNA testing code. I know nothing about DNA sequence and biology. 1. Which are the best books about genome DNA sequence processing suitable for me who is developing a new algorithm constructing suffix array and want the algorithm better workable for DNA analyses. 2. I want to know if there is any algorithm constructing Suffix Array whose performance depends on Max(LCPs)? 3. Genome DNA testing file contains only 4 characters: A,C,G and T. Is it right? I found another char U in RNA. Does the file still contain 4 characters? 4. If the number of chars in a file is limited to 4, and all repeatable patterns are known, I can specially design some technical refinement to improve my algorithm performance. I want know, in addition to 1 char, 2 chars, 3 chars and 4 chars repentance, 5 chars or more repeatable sequence are common? And if common, the largest common chars repentance contains how many different chars? 1 char repentance: ... 2 char repentance: ACACACACACACACA... Thank you. Weng -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks] Re: Implement lastindexofastring(String s1,String s2)
What I suggested is optimal and doesn't require you to reverse the strings. It's not hard to see that it takes O(n + m) which cannot be improved on. Additionally it works for any other search algorithm than KMP. On 7 April 2014 20:41, Dan dant...@aol.com wrote: Depends on what language you are using??? Fortran has this capability built directly into it's standard Index() routine ( ie. it does what you might call a 'backwards' search). I imagine other languages have a similar capability. If not, and the strings are not huge memory hogs... or if you are ok with overwriting your original string, s1 in the process: Invert both strings.ie rearrange them such that the last letter of each string becomes the first, etc., etc. Then use your languages normal INDEXED type of search. Otherwise, you'll just have to do an Indexed search repeatedly to find the last occurrence... or... write your own special Index function. I'm not sure what the fastest search algorithm is for that. I seem to remember reading up on it a long time ago. It's not a brute force method if I recall correctly. Dan :-) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks] Implement lastindexofastring(String s1,String s2)
You barely have to modify the algorithm. Just store the index of the most recent occurrence instead of reporting it, then report whatever you have stored right at the end. On 2 April 2014 19:25, pawan yadav pawan1991ya...@gmail.com wrote: Hi All, How can we do the following problem in efficient way : Implement lastindexofastring(String s1,String s2) . If s2 is present multiple times return the last index of s2 in s1 , else return -1. Is KMP applicable for this problem? If yes, then how can we modify KMP algo? Thanks, Pawan. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks]
Because then it's not a random shuffle? If you randomly shuffle something the order you currently have should be just as likely as any other On 28 January 2013 12:29, shady sinv...@gmail.com wrote: Why do we use Fisher Yates algorithmhttp://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#The_modern_algorithm when in the worst case there is no shuffle at all ? we can modify it by generating random number not inclusive of the element that we are about to swap -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out.
Re: [algogeeks] Re: Minimum sum of Array
How is it a huge improvement? Your O(SN) is the same time as the dynamic programming solution for 0-1 knapsack isn't it? On 8 January 2013 14:44, Don dondod...@gmail.com wrote: Yes, that is true. However, trying to find the optimal partition is equivalent to the 0-1 knapsack problem, which is exponential time. So S*N is a huge improvement over that. Does someone have a better solution? Don On Jan 7, 10:49 am, Nikhil Karnwal sunnyk12...@gmail.com wrote: @ Don but ur's solution complexity is O(S*N) which is large in case of large N and large numbers. Like in case of s=100 and N=10^5. Correct me if I am wrong. Nikhil Karnwal On Mon, Jan 7, 2013 at 9:04 PM, Don dondod...@gmail.com wrote: Note that you don't need to store the entire P matrix. You really just need the last column. Don On Jan 7, 10:29 am, Don dondod...@gmail.com wrote: You want to partition the array A into to subsets S1 and S2 such that you minimize |Sum(S1)-Sum(S2)|. The optimal sum for the subsets is S=SUM(A)/2 Use DP to build a matrix P: P[i][j] = 1 if some subset of {A[0]..A[i]} has a sum of j, 0 otherwise Now find a value of i such that P[n][i] = 1 which minimizes S-i. The minimum sum is 2S-2i. Don On Jan 5, 12:58 pm, mukesh tiwari mukeshtiwari.ii...@gmail.com wrote: Hello All! I have a given array of numbers and I have to change the sign of numbers to find out the minimum sum. The minimum sum will be 0 or greater than 0. Here is couple of test cases 1. [ 1 , 2 , 3 , 2 , 4 ]. Changing the sign [ -1 , -2 , -3 , 2 , 4 ] so minimum sum will be 0. 2. [ 3 , 5 , 7 , 11 , 13 ]. Changing the sign [ -3 , -5 , 7 , -11 , 13 ] so minimum sum is 1. So technically this problem boils down to divide the set into two subset and find out the minimum difference. I though of DP but the number of element in array could 10^5 so could some one please tell me how to solve this problem ? I didn't assume that number will be positive because it was not given in the problem. Regards Mukesh Tiwari -- -- --
Re: [algogeeks] Re: Printing all inversions in an array
That statement is only very superficially similar. Counting them is saying how many of them there are, it doesn't necessarily require you to look at/compute each one. So it is not the same as printing them. If you're saying I want to print out each inversion individually then it's going to be n^2 and there's no way around it. If you have some other encoding so you can print something which represents multiple inversions in 1 step, you might be able to get under n^2. On 22 October 2012 12:03, Aamir Khan syst3m.w...@gmail.com wrote: On Monday, October 22, 2012, Dipit Grover wrote: Since the number of inversions are of order n^2 in the worst case, so should be the complexity of printing them apparently. It makes sense to some extent but this is no proof. There has to be a better proof for lower bound of complexity for this algorithm. Because I can state similar statement, Since the number of inversions are of order N^2 in the worst case, so should be the complexity of counting them apparently. But we all know this is not true as we already know O(nlogn) solution. -- 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. -- Aamir Khan | 4th Year | Computer Science Engineering | IIT Roorkee -- 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] all subarray with sum zero
Because you sort the array you may have values such that the indices are in the wrong order e.g your 'end' position is less than your 'start' position. You need to check for this, however if you use an inplace sorting algorithm this becomes easier. Additionally you may have up to O(n^2) occurrences so when you say 'now check for consecutive value which have same value' you should do a binary search for the end position instead. If you do as you said you may take O(n) per search. You want to report the ranges to avoid having to have report each occurrence. On 18 September 2012 05:11, pankajsingh psingh...@gmail.com wrote: it wud give u continuous...subarray...if u want non continuous..question shud be subsequence...and for that u need to all combination O(n^20..which is offcourse bruteforce... -- 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] Contiguous Sub sequence
1. Calculate the sum of every prefix of the array O(n) 2. Store as pairs (sum, index) and sort by sum using a stable sort. Observation: Sum of every factor can be expressed as the difference between the sum of 2 prefixes. 3. for each entry search for the corresponding difference such the index found is greater than original index. Works for any sum, not just 0. Takes O(n log n) On 2 September 2012 14:22, Navin Kumar algorithm.i...@gmail.com wrote: Given an unsorted integer array. Find the contiguous sub sequences whose sum is 0. -- 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/-/pFvfWQjVrnkJ. 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] Contiguous Sub sequence
Your approach sounds like the optimal (and linear) algorithm for the submass finding problem. But if I recall correctly that only works in linear time if the input is entirely positive integers? Maybe I'm being stupid but wont checking that array be quadratic? On 2 September 2012 20:02, Navin Kumar algorithm.i...@gmail.com wrote: @pradip: Finding same element in temp array is little bit tricky. For displaying item from i+1 to j , you have to make sure that there is equal element at i and j index in temp array. How will you ensure it in O(n) time? On Sun, Sep 2, 2012 at 3:16 PM, Pradeep Mishra pradam.prad...@gmail.comwrote: This algorithm is *O(n)*. Given an int[] input array, you can create an int[] tmp array where tmp[i] = tmp[i - 1] + input[i]; Each element of tmp will store the sum of the input up to that element. Now if you check tmp, you'll notice that there might be values that are equal to each other. Let's say that this values are at indexes j an k with j k, then the sum of the input till j is equal to the sum tillk and this means that the sum of the portion of the array between j and k is 0! Specifically the 0 sum subarray will be from index j + 1 to k. - NOTE: if j + 1 == k, then k is 0 and that's it! ;) - NOTE: The algorithm should consider a virtual tmp[-1] = 0; Correct me if i am wrong Thanx -- Pradeep Kumar Mishra IIIT Allahabad B. Tech 3rd Year ( IT ) Another Mail - prad...@gmail.com -- 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.
Re: [algogeeks] Contiguous Sub sequence
No you're correct. I was doubting it would work :P For hashing you would need perfect hashing to ensure O(n) wouldn't you? On 2 September 2012 23:21, atul anand atul.87fri...@gmail.com wrote: @carl : if it would work only for entirely positive integers , then i aux[] array created will never contain 0 or repeated elements... correct me if i am wrong... On 9/2/12, atul anand atul.87fri...@gmail.com wrote: @navin : hashMap can be used to do it in O(n) time. On 9/2/12, Carl Barton odysseus.ulys...@gmail.com wrote: Your approach sounds like the optimal (and linear) algorithm for the submass finding problem. But if I recall correctly that only works in linear time if the input is entirely positive integers? Maybe I'm being stupid but wont checking that array be quadratic? On 2 September 2012 20:02, Navin Kumar algorithm.i...@gmail.com wrote: @pradip: Finding same element in temp array is little bit tricky. For displaying item from i+1 to j , you have to make sure that there is equal element at i and j index in temp array. How will you ensure it in O(n) time? On Sun, Sep 2, 2012 at 3:16 PM, Pradeep Mishra pradam.prad...@gmail.comwrote: This algorithm is *O(n)*. Given an int[] input array, you can create an int[] tmp array where tmp[i] = tmp[i - 1] + input[i]; Each element of tmp will store the sum of the input up to that element. Now if you check tmp, you'll notice that there might be values that are equal to each other. Let's say that this values are at indexes j an k with j k, then the sum of the input till j is equal to the sum tillk and this means that the sum of the portion of the array between j and k is 0! Specifically the 0 sum subarray will be from index j + 1 to k. - NOTE: if j + 1 == k, then k is 0 and that's it! ;) - NOTE: The algorithm should consider a virtual tmp[-1] = 0; Correct me if i am wrong Thanx -- Pradeep Kumar Mishra IIIT Allahabad B. Tech 3rd Year ( IT ) Another Mail - prad...@gmail.com -- 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. -- 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] TRIE problem
There's no reason why a trie or a tree node couldn't be used to 'represent' more than one word. Although you'd take a penalty in the complexity for searching etc. On 31 August 2012 15:33, Navin Kumar algorithm.i...@gmail.com wrote: Can we store multiple words in single TRIE node by using linked list or some other data structure. Based on the some property a node in TRIE will hold all the word with same property. -- 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/-/tvqq-_HUZ8sJ. 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] O(n) solution is there or not!!
Yeah sorry, misread the question then had a quick attempt :) I don't see where you get the lg n from though. I didn't do any binary searches. On 19 August 2012 22:53, pankajsingh psingh...@gmail.com wrote: @carl- got ur point..but complexity is more..suffix array takes o(n^2lgn)..considering string comparisons. complexity to build...i already have o(n^2)..want o(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?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] O(n) solution is there or not!!
I still don't understand. There's far quicker suffix array construction algorithms than O(n^2 log n)? There's O(n) algorithms On 20 August 2012 23:27, pankajsingh psingh...@gmail.com wrote: Thanks.carl and atul.!!.@carl-i got lgn due to string comparison sort while making the suffix array..:) -- 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] O(n) solution is there or not!!
Just calculating the suffix array solves the problem if you do it with the LCP array as well. You don't need to 'use' the suffix array so to speak. On 19 August 2012 21:45, pankajsingh psingh...@gmail.com wrote: Is there any O(n) solution this question...I Cleared all the testcases but my solution is not O(n) and...I think there should be some O(n) solution..by seeing the constraint to this question..I tried to think for Kmp in this ..but didnt workand suffix array method will have more complexity..any suggestion For two strings A and B, we define the similarity of the strings to be the length of the longest prefix common to both strings. For example, the similarity of strings abc and abd is 2, while the similarity of strings aaa and aaab is 3. Calculate the sum of similarities of a string S with each of it's suffixes. *Input:* The first line contains the number of test cases T. Each of the next T lines contains a string each. *Output:* Output T lines containing the answer for the corresponding test case. *Constraints:* 1 = T = 10 The length of each string is at most 10 and contains only lower case characters. -- Pankaj Singh B.Tech in Computer Science and Engineering - lllrd year IIT Roorkee, India -- 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] O(n) solution is there or not!!
Or a suffix tree would work. Pre process it to answer Lowest common ancestor queries. On 19 August 2012 21:51, Carl Barton odysseus.ulys...@gmail.com wrote: Just calculating the suffix array solves the problem if you do it with the LCP array as well. You don't need to 'use' the suffix array so to speak. On 19 August 2012 21:45, pankajsingh psingh...@gmail.com wrote: Is there any O(n) solution this question...I Cleared all the testcases but my solution is not O(n) and...I think there should be some O(n) solution..by seeing the constraint to this question..I tried to think for Kmp in this ..but didnt workand suffix array method will have more complexity..any suggestion For two strings A and B, we define the similarity of the strings to be the length of the longest prefix common to both strings. For example, the similarity of strings abc and abd is 2, while the similarity of strings aaa and aaab is 3. Calculate the sum of similarities of a string S with each of it's suffixes. *Input:* The first line contains the number of test cases T. Each of the next T lines contains a string each. *Output:* Output T lines containing the answer for the corresponding test case. *Constraints:* 1 = T = 10 The length of each string is at most 10 and contains only lower case characters. -- Pankaj Singh B.Tech in Computer Science and Engineering - lllrd year IIT Roorkee, India -- 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] O(n) solution is there or not!!
Oh, I actually read the question totally wrong. I think this idea is linear, but it's late so I'm not sure. 1. Calculate suffix array and lcp array for the text. 2. Calculate the longest common prefix between your text and the first entry in your suffix array and initialise a variable called total with this value and another variable called last. Last is a variable to store the lcp between the text and the last suffix you considered. 3. Now traverse the suffix array using the lcp array. for some point, i, if the lcp between the text and the last entry is lcp[i+1] you can do total = total + lcp[i+1] if the lcp between the text and the last entry is lcp[i+1] you can do total = total + lcp[i-1] if the lcp between the text and the last entry is = lcp[i+1] you need to do some more work and try and extend the match from position lcp[i+1] I think that should be linear though? correctme if i'm wrong. On 19 August 2012 22:23, pankajsingh psingh...@gmail.com wrote: @Carl- I didnt got ur point completely abt Lcp array..can you demonstrate on the below example... Example for ababaa answer shud be -11 suffix array wud be:- a aa abaa ababaa baa and Lcp array would be then 0 1 1 3 0 ..correct if wrong..whats next... -- 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: Number Theory (Power of 3 )
@Dave Yours only works for a certain subset of all possible powers or 3 doesn't it? So WgpShashank's would be more general? On 5 December 2011 14:30, Dave dave_and_da...@juno.com wrote: @WgpShashank: Yours is an O(log n) solution. Mine is O(1). Dave On Dec 5, 6:21 am, WgpShashank shashank7andr...@gmail.com wrote: @SAMMM have a look * *solution is to keep dividing the number by 3, i.e, do n = n/3 iteratively. In any iteration, if n%3 becomes non-zero and n is not 1 then n is not a power of 3, otherwise n is a power of 3 check it out ?http://codepad.org/863ptoBE Thanks Shashank Computer Science BIT Mesrahttp:// www.facebook.com/wgpshashankhttp://shashank7s.blogspot.com/ -- 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: Number Theory (Power of 3 )
Ah I see, in which case could you not generalise your solution for all integers? By taking into account the size of words on the computer for example? On 5 December 2011 15:09, Dave dave_and_da...@juno.com wrote: @Carl: Yes, as coded, my algorithm is for 32-bit integers. But the original poster asked for a solution using bit manipulation, and modulus and division are arithmetic operations, not bit operations. Dave On Dec 5, 8:56 am, Carl Barton odysseus.ulys...@gmail.com wrote: @Dave Yours only works for a certain subset of all possible powers or 3 doesn't it? So WgpShashank's would be more general? On 5 December 2011 14:30, Dave dave_and_da...@juno.com wrote: @WgpShashank: Yours is an O(log n) solution. Mine is O(1). Dave On Dec 5, 6:21 am, WgpShashank shashank7andr...@gmail.com wrote: @SAMMM have a look * *solution is to keep dividing the number by 3, i.e, do n = n/3 iteratively. In any iteration, if n%3 becomes non-zero and n is not 1 then n is not a power of 3, otherwise n is a power of 3 check it out ?http://codepad.org/863ptoBE Thanks Shashank Computer Science BIT Mesrahttp:// www.facebook.com/wgpshashankhttp://shashank7s.blogspot.com/ -- 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.
Re: [algogeeks] Re: Number Theory (Power of 3 )
Sorry, I was being a bit vague. I meant what would the time complexity be then? As I understand your Constant time is Dependant on the constant pre computation you do, which is no longer the case when you generalise On 5 December 2011 16:14, Dave dave_and_da...@juno.com wrote: @Carl: Of course. For any given word size, extend the tables of powers of 2 and of 3 and change the for loop limit. Dave On Dec 5, 9:36 am, Carl Barton odysseus.ulys...@gmail.com wrote: Ah I see, in which case could you not generalise your solution for all integers? By taking into account the size of words on the computer for example? On 5 December 2011 15:09, Dave dave_and_da...@juno.com wrote: @Carl: Yes, as coded, my algorithm is for 32-bit integers. But the original poster asked for a solution using bit manipulation, and modulus and division are arithmetic operations, not bit operations. Dave On Dec 5, 8:56 am, Carl Barton odysseus.ulys...@gmail.com wrote: @Dave Yours only works for a certain subset of all possible powers or 3 doesn't it? So WgpShashank's would be more general? On 5 December 2011 14:30, Dave dave_and_da...@juno.com wrote: @WgpShashank: Yours is an O(log n) solution. Mine is O(1). Dave On Dec 5, 6:21 am, WgpShashank shashank7andr...@gmail.com wrote: @SAMMM have a look * *solution is to keep dividing the number by 3, i.e, do n = n/3 iteratively. In any iteration, if n%3 becomes non-zero and n is not 1 then n is not a power of 3, otherwise n is a power of 3 check it out ?http://codepad.org/863ptoBE Thanks Shashank Computer Science BIT Mesrahttp:// www.facebook.com/wgpshashankhttp://shashank7s.blogspot.com/ -- 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. -- 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: Algm
Heapsort and any other comparison sort have a lower bound of O(nlogn). Radix sort gets around this as it isn't a comparative sorting algorithm. It instead groups numbers by their significant digits (keeping original order), normally by count sort as mentioned above. Applying this for each significant digit will get you a sorted list in O(n) time. On 15/11/2011, Vijay Khandar vijaykhand...@gmail.com wrote: How it is Radix sort, why not Heapsort, plz explain me in detail.. On Nov 14, 3:36 pm, Ankur Garg ankurga...@gmail.com wrote: Radix Sort On Mon, Nov 14, 2011 at 1:57 PM, Vijay Khandar vijaykhand...@gmail.comwrote: Which is the sorting algm sorts the integers [1...n^3] in O(n). a)Heapsort b)Quicksort c)Mergesort d)Radix sort please tell anyone. Vijay. -- 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.
Re: [algogeeks] Algm
Bit confused by your n^3. Could you clarify? In the mean time Radix is an O(n) sorting algorithm. Where n is the length of the array. On 14/11/2011, Vijay Khandar vijaykhand...@gmail.com wrote: Which is the sorting algm sorts the integers [1...n^3] in O(n). a)Heapsort b)Quicksort c)Mergesort d)Radix sort please tell anyone. Vijay. -- 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] Algo for in-place Stack Reversal.
An in place algorithm is one which only uses a constant amount of extra memory. So recursion is a problem as it will use an implicit stack of size O(n) which is linear extra memory, not constant. On 7 October 2011 15:16, .itoa nitm...@gmail.com wrote: But , let's say if we do by recursion , then could you explain the way it would work ? And this in-place keyword is not clear to me. Does it mean we can't use buffer / temporary variables or something else? -- 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/-/IW6-aiJabGAJ. 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]
Depends which quarter you're measuring. Bricks aren't a uniform cuboid so wont be 1kg per quarter On 16 August 2011 12:16, sukran dhawan sukrandha...@gmail.com wrote: which college are u from? -- Forwarded message -- From: ravinder s ravinderr...@gmail.com Date: Tue, Aug 16, 2011 at 4:15 PM Subject: [algogeeks] To: algogeeks@googlegroups.com a brick is 4kg.If you make the brick 1/4 then how much will be its weight.? -- 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.
Re: [algogeeks] Re: island puzzle
It's been posted quite a few times recently. Just check the mailing list. On 30 May 2011 18:46, himanshu kansal himanshukansal...@gmail.com wrote: guys wake up On Fri, May 27, 2011 at 9:24 PM, himanshu kansal himanshukansal...@gmail.com wrote: a king has two sons eric and bob.he wants to divide his islands the islands are in a queue.eric being elder gets the first chancethey both can pick d island alternatively from beginning or end of the queue only.design an algo so tht eric gets the max. piece of land. i hv solved it if the no of islands are even bt nt getting any clue whn no of islands are odd in the odd casei think bob vl hv an advantage ovr ericbut how to develop strategy for eric(if no of islands are odd) -- Regards Himanshu Kansal MCS-DU -- 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] Test Cases
Don't really get the question On 10 May 2011 09:08, Akshata Sharma akshatasharm...@gmail.com wrote: write test cases for the division '/' operator.. -- 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: Sartaj Sahni ebook
Haha I was just joking around. No harm done. On 24 April 2011 11:37, D.N.Vishwakarma@IITR deok...@gmail.com wrote: @KK I have shared a link of sartaj sahni ebook wth you On Sun, Apr 24, 2011 at 4:06 PM, KK kunalkapadi...@gmail.com wrote: @ Carl Barton: I also know that site... i want a shared link u stupid... -- 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. -- **With Regards Deoki Nandan Vishwakarma IITR MCA Mathematics Department* * -- 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] Sartaj Sahni ebook
No problem. http://www.amazon.co.uk/Data-Structures-Algorithms-Applications-Java/dp/0071169008/ref=sr_1_3?ie=UTF8qid=1303586345sr=8-3 On 23 April 2011 18:41, KK kunalkapadi...@gmail.com wrote: Please give link to: Data Structures,Algorithms and Applications by Sartaj Sahni... or directly mail to me. -- 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] [brain teaser ] Math Prime number puzzle 15april
What do you mean by 'Whether it is true'? On 15 April 2011 09:41, Lavesh Rawat lavesh.ra...@gmail.com wrote: * Puzzle * * * *If 'a' is a prime number, then prove, that a*a+26 is NOT a prime number (whether it is true).* *Update Your Answers at* : Click Herehttp://dailybrainteaser.blogspot.com/2011/04/math-prime-number-puzzle-15april.html?lavesh=lavesh 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.
Re: [algogeeks] [brain teaser] 12april
Greater than, On 12 April 2011 10:25, Lavesh Rawat lavesh.ra...@gmail.com wrote: Mathematical Puzzle What mathematical symbol can be placed between 5 and 9, to get a number greater than 5 and smaller than 9? *Update Your Answers at* : Click Herehttp://dailybrainteaser.blogspot.com/2011/04/mathematical-puzzle-12april.html?lavesh=lavesh 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.
Re: [algogeeks] Re: Sort array with two subparts sorted
That's linear space, not constant space. Vaibhav's seems good for constant space solution On 12 April 2011 13:17, sravanreddy001 sravanreddy...@gmail.com wrote: Yes.. merge sort. O(n) to find the starting of 2nd sub-array. and O(n) for the merge process (similar to last step in merge sort) O(n) On Apr 12, 2:37 pm, Akash Agrawal akash.agrawa...@gmail.com wrote: Given an array with two subparts sorted. How will you make a final sorted array. i/p: 1, 5, 7, 9, 11, 23, 2, 3, 8, 9, 21 o/p: 1, 2, 3, 5, 7, 8, 9, 9, 11, 21, 23 Regards, Akash Agrawalhttp://tech-queries.blogspot.com/ -- 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: Sort array with two subparts sorted
quick sort is worst case O(n^2) On 12 April 2011 18:17, Akash Agrawal akash.agrawa...@gmail.com wrote: since we are bubbling up, it's again is a O(n^2). Is there anything possible like O(n) in constant space. I tried on swapping values but mees it somewhere... here are intermediate steps in my approach. 1, 5, 7, 9, 11, 2, 3, 8, 9, 21 1, 2, 7, 9, 11, *5*, 3, 8, 9, 21 1, 2, 3, 9, 11, *5, 7*, 8, 9, 21 1, 2, 3, 5, 11, 9, 7, 8, 9, 21 1, 2, 3, 5, 7, 9, 11, 8, 9, 21 1, 2, 3, 5, 7, 8, 11, 9, 9, 21 1, 2, 3, 5, 7, 8, 9, 11, 9, 21 1, 2, 3, 5, 7, 8, 9, 9, 11, 21 Regards, Akash Agrawal http://tech-queries.blogspot.com/ On Tue, Apr 12, 2011 at 10:23 PM, powerideas arpitbhatnagarm...@gmail.com wrote: say we hav array {101,102,103,104(ptr1),1,2,3,4(ptr2)} 1.take end of 1 st array in ptr1end of 2nd array in ptr2 2.IF (ptr1ptr2) bubble up ptr1 to ptr2; ptr2-- ptr1-- ELSE ptr2--; 1.compare last element of both arrays ie 104 4 since 1044 bubble up 104 to end since it will be greater than whole 2 nd array so {101,102,103(ptr1),1,2,3,4(ptr2),104} moving on ex 2 : {1,3,5,7(ptr1),2,4,6,8(ptr2)} 78 so ptr2-- {1,3,5,7(pr1),2,4,6(ptr2), 8} {1,3,5(ptr1),2,4,6(ptr2),7,8} moving on.. -- 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.
Re: [algogeeks] Re: Sort array with two subparts sorted
Very interesting link! As we only need to perform one merge we should be able to modify it to run in O(n) time? In a similar style as a strand sort? On 12 April 2011 22:55, hary rathor harry.rat...@gmail.com wrote: http://thomas.baudel.name/Visualisation/VisuTri/inplacestablesort.html take a glance on this merge sort this is Inplace and also stable -- 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] website feedback
Either way, it's a pretty boring idea. On 9 April 2011 16:06, hary rathor harry.rat...@gmail.com wrote: is it not some kind of fishing page ? -- 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] website feedback
So it will post to other people that I would love to do something? 2011/4/8 Seçkin Can Şahin seckincansa...@gmail.com I developed a website/facebookapp. I would appreciate it if you could give feedback about it. http://apps.facebook.com/wouldloveto/ -- 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: 28march
The question is to find the minimum number of races, so there is only one answer On 7 April 2011 06:40, Manish Pathak pathak@gmail.com wrote: There are two answers 11 and 7 On Thu, Mar 31, 2011 at 12:23 PM, Abhishek Sharma jkabhishe...@gmail.comwrote: @sourabh: could u please elaborate how u came to that conclusion. Dave's logic seems to be right.. On Thu, Mar 31, 2011 at 11:00 AM, sourabh jakhar sourabhjak...@gmail.com wrote: answer is 6 races On Mon, Mar 28, 2011 at 11:53 PM, Dave dave_and_da...@juno.com wrote: 7 races. For the first five races, divide the horses into groups of five and record the win, place, and show finishers of each race. For the sixth race, run the winners of the first five races. Now, only six horses remain in contention for the fastest three: The winner of the sixth race and the place and show horses of his first race, The place horse in the sixth race and the place horse in his first race. The show horse in the sixth race. Three of these horses are known to be faster than all other horses. The winner of the sixth race is known to be the fastest horse. Run the other five contenders in race 7 and choose the fastest two. Dave On Mar 28, 2:54 am, Lavesh Rawat lavesh.ra...@gmail.com wrote: *Horse Race Problem Solution* * *Ok, so there are 25 horses and the race track only allows 5 horses to race at a given time. Given that there is no stop watch available your task is to determine the fastest 3 horses. Assume that each horses speed is constant in different races, what is the minimum number of races to determine the fastest 3? Update Your Answers at : Click Here http://dailybrainteaser.blogspot.com/2011/03/28march.html?lavesh=lavesh 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. -- SOURABH JAKHAR,(CSE)(3 year) ROOM NO 167 , TILAK,HOSTEL 'MNNIT ALLAHABAD The Law of Win says, Let's not do it your way or my way; let's do it the best way. -- 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. -- Thanks and Regards, Manish Pathak ** TimesJobs.com Mo. 9015687266 http://manishpathak-mobile.blogspot.com/ -- 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] [brain teaser ] 7april
As the fire burns it will spread to the east but burn out in the west, so he can move to the west of the island? On 7 April 2011 08:57, your name last name ac08...@gmail.com wrote: * Survive Fire in Island Puzzle * Answer: The Man can escape the fire if he goes to the west corner of the island... as the wind is blowing from the west , no fire will reach the west corner -- 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] i am new
Yes On 6 April 2011 11:36, a_SillyGuy ammukumar...@gmail.com wrote: hi , i've recently joined this group in a mood to master the algorithms. Will someone tell ,weather i will be benifitted by this group or not. ??? -- 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:
Haha On 3 April 2011 15:28, Arpit Sood soodfi...@gmail.com wrote: assignment problem ? haha On Sun, Apr 3, 2011 at 7:16 PM, Dr. Deepak Garg dr.gar...@gmail.comwrote: Beta, puchna hi tha, to mujhse puchte! Anyways, you will get the solution in tomorrow's lecture @1pm. I have gone through your profile. See me in my cabin after the class. Make sure that you attend tomorrow's lecture. For now, study dynamic programming.. On Apr 3, 6:03 pm, SANDEEP AAMIN sandeep.aa...@gmail.com wrote: hey guys please help me to solve this QUESTION : input a number C , an output all of the ways that a group of ascending positive numbers can be summed to give C. for e.g if C=6,the output should be 1+2+3 1+5 2+4 [solve using dynamic programming] please tell me about this.. -- 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, Arpit Sood -- 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] minimizes the average completion-time
Correct me but isn't this just a process scheduling problem and your solution is a shortest processing time schedule? It's a well research problem and there's plenty of papers on this if you google. On 1 April 2011 13:14, snehal jain learner@gmail.com wrote: Suppose you are given a collection of n tasks that need to be scheduled. With each task, you are given its duration. Specifically, task i takes ti units of time to execute. Suppose with each task we also have a release time ri, and that a task may not be started before its release time. Furthermore, tasks may be preempted, in that a scheduled task can be interrupted and later resumed, and this can happen repeatedly. Design an algorithm that finds a schedule that minimizes the average completion-time in this new situation. My solution Store thetasks in increasing order of their release time. And schedule the tasks according to shortest remaining timefirst. any comments? -- 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] Are U a Student Must Read this Frwd This Please If u Like We R student like You TOO
Your link doesn't work and all the links on the top bar appear to lead to do nothing. Doesn't give a brilliant impression. On 30 March 2011 09:22, ArPiT BhAtNaGaR arpitbhatnagarm...@gmail.comwrote: NIT JAIPUR PRESENTS YOU KAMPUSATTACK.COM http://ampusattack.com/ Biggest Social Platform For Students by Students - Enjoy Spiced up Social Networking With Hot Features! - Get Connected To Constillation Of Young Brains Like You! - Access share useful collection of Ebooks,Notes, Ppt's,Codes,Programs. etc.. - Find Lot Of Humor Fun Inside! - Chat With Spicy Kampus Messenger with new people , Play Amazing Games. *! STAND OUT FROM CROWD !* With Our Useful Resources You Will Never Be Same As Rest Of Crowd - GD 's With Pro's Con's. - INTERVIEW preprations by personal experience of people. - PLACEMENT PAPERS - *College Previous Papers* - *Info About Latest **Technologies Gadgets.* - *Project Ideas help.* - *INTERNSHIP TRANING GUIDANCE.* *! BE CONNECTED AND UPDATED!* - *Connect With Your Pal's , Senior's Alumni's.* - *Exchange Idea's With People Across Kampuses.* *! EXCLUSIVE EXPERT ZONE !* - STEP OUT from other's with our *INDUSTRIAL GUINDANCE* from Adobe , Microsoft, NTPC, BPCL ,Accenture. - Field Experts Career Consultant Inside. Register Today! *WWW.KAMPUSATTACK.COM* http://www.kampusattack.com/ -- Arpit Bhatnagar (MNIT JAIPUR) -- 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] [brain teaser ] 29march
Agreed, 122 On 29 March 2011 14:19, Kunal Yadav kunalyada...@gmail.com wrote: 122 1, 2, 5, 14, 41, x Whats x ?? -- Regards Kunal Yadav (http://algoritmus.in/) -- 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: How to check whether a language isTuring Complete?
Somewhat; HTML, CSS and SQL aren't programming languages anyway, they're markup, style sheets and query languages respectively. TXL would be an example of a programming language which isn't turing complete but can still do something. Being able to compute something doesn't make it turing complete, being able to compute anything which it is possible to compute is what makes it turing complete. On 28 March 2011 17:42, Karthik Jayaprakash howtechstuffwo...@gmail.comwrote: Thanks for your reply. I understood lot better than I was previously. So summing up your answers, A language is turing complete, if we can write infinite loops and primitive recursive function. Some of the non turing complete languages that I came across are HTML, CSS, SQL... From this can I assume, that a language is turing complete, if it computes something, rather than just trying to display a interface, or pull records. Coz languages like HTML CSS doesnt do anything to compute something, it just transforms one way of representation to another(HTML - browser readable code), where as C,C++ can compute something and can represent large mathematical problems. Am I right Pardon me if my question is stupid... Thanks.. On Mar 27, 4:07 pm, Wladimir Tavares wladimir...@gmail.com wrote: Theoretically, a language is Turing-complete if it computes all partial recursive functions, ie functions that include all the basic functions and is closed under composition, primitive recursion and minimization. Basic Functions zero () = 0 succ (x) = x +1 proj_i (x1, x2,..., xn) = xi Composition Let f1, f2, f3, fn eg partial recursive functions then h is defined by a composition iff h (x1,..., xn) = g (f1 (x1, .., xn), f2 (x1, ... , xn ),..., fn (x1,..., xn)) The notion of computability is established by Churh-Turing thesis. I believe our general computability is a very difficult task:) Wladimir Araujo Tavares *Federal University of Ceará * On Sun, Mar 27, 2011 at 3:56 PM, Carl Barton odysseus.ulys...@gmail.com wrote: To elaborate why; if your language suffers from the halting problem then it's pretty safe to say it's turing complete and infinite loops would allow you to achieve that. On 27 March 2011 19:03, Carl Barton odysseus.ulys...@gmail.com wrote: If you're not concerned about being that formal then having conditional branching statements and being able to write infinite loops would be a pretty good indication. On 27 March 2011 14:38, Karthik Jayaprakash howtechstuffwo...@gmail.comwrote: Hi, Thanks for replying. I am aware of that. But is there a practical way of checking it On Mar 26, 7:40 pm, Carl Barton odysseus.ulys...@gmail.com wrote: If it can simulate a universal turing machine then it is turing complete On 26 March 2011 22:34, Karthik Jayaprakash howtechstuffwo...@gmail.comwrote: Hi, Is there a way to check that if a language is Turing complete? Thanks. -- 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. -- 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: How to check whether a language isTuring Complete?
If you're not concerned about being that formal then having conditional branching statements and being able to write infinite loops would be a pretty good indication. On 27 March 2011 14:38, Karthik Jayaprakash howtechstuffwo...@gmail.comwrote: Hi, Thanks for replying. I am aware of that. But is there a practical way of checking it On Mar 26, 7:40 pm, Carl Barton odysseus.ulys...@gmail.com wrote: If it can simulate a universal turing machine then it is turing complete On 26 March 2011 22:34, Karthik Jayaprakash howtechstuffwo...@gmail.com wrote: Hi, Is there a way to check that if a language is Turing complete? Thanks. -- 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.
Re: [algogeeks] Re: How to check whether a language isTuring Complete?
To elaborate why; if your language suffers from the halting problem then it's pretty safe to say it's turing complete and infinite loops would allow you to achieve that. On 27 March 2011 19:03, Carl Barton odysseus.ulys...@gmail.com wrote: If you're not concerned about being that formal then having conditional branching statements and being able to write infinite loops would be a pretty good indication. On 27 March 2011 14:38, Karthik Jayaprakash howtechstuffwo...@gmail.comwrote: Hi, Thanks for replying. I am aware of that. But is there a practical way of checking it On Mar 26, 7:40 pm, Carl Barton odysseus.ulys...@gmail.com wrote: If it can simulate a universal turing machine then it is turing complete On 26 March 2011 22:34, Karthik Jayaprakash howtechstuffwo...@gmail.comwrote: Hi, Is there a way to check that if a language is Turing complete? Thanks. -- 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.
Re: [algogeeks] How to check whether a language isTuring Complete?
If it can simulate a universal turing machine then it is turing complete On 26 March 2011 22:34, Karthik Jayaprakash howtechstuffwo...@gmail.comwrote: Hi, Is there a way to check that if a language is Turing complete? Thanks. -- 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] Merge K Sorted Array In to Single Array
k sorted array can be merged in linear time I believe. If we have K arrays FIRST, SECOND, ., Up to K and we keep k counters (i, j, , up to k), one for each list Simply check if FIRST[i] SECOND[j], ., Up to K Put the smallest in the merged list and increment the counter of the list it came from, keep doing this until you've read each array once and you will have a sorted list On 25 March 2011 08:06, bittu shashank7andr...@gmail.com wrote: Given k sorted arrays each of length n, construct a single merged and sorted array.focus on running time and space complexity my soln. 1st basic soln..simple merge sort all whet we does in merging 2 sorted array it too complex for big K 2nd i have approach using min-heap as well but not able to figure the working code ..dono why? lets c what others think Approach Exactness of The Solution matters here Thanks Shashank -- 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] Thinktionary -- The social dictionary!
So, what is this? 2011/3/24 Seçkin Can Şahin seckincansa...@gmail.com Hi guys, I developed this website. Might be interesting for you! http://www.thinktionary.net Have fun! Seckin John -- 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] friend's finder
Are their any requirements on performance? On 22 March 2011 13:05, snehal jain learner@gmail.com wrote: If you want to search for a friend on Facebook, what are the possible strategies that you could use. You are a programmer and can also access Facebook’s Social Graph API. Make your own assumptions. How could you make it a ‘Friend Finder’ app? -- 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] How to print numbers from 1 to 100 without loop , without recursion , without #define statements , without goto statement
@kumar Your example is still recursion On 16 March 2011 16:46, kumar anurag anurag.it.jo...@gmail.com wrote: ok guys... On Wed, Mar 16, 2011 at 9:54 PM, himanshu kansal himanshukansal...@gmail.com wrote: class arr {static int i; public: arr() { couti++; } }; int arr::i=1; int main() { arr a[100]; } On Wed, Mar 16, 2011 at 9:47 PM, kumar anurag anurag.it.jo...@gmail.comwrote: using two different functions calling one another ? like fun1() { fun2() } fun2() { fun1(); } On Wed, Mar 16, 2011 at 9:39 PM, D.N.Vishwakarma@IITR deok...@gmail.com wrote: * * -- *With Regards Deoki Nandan Vishwakarma IITR MCA Mathematics Department * -- 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. -- Kumar Anurag -- 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. -- Kumar Anurag -- 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] Brainfuck compiler
Just out of interest. What are you planning to write in brainfuck? On 15 March 2011 14:58, Natansh Verma natansh.ve...@gmail.com wrote: I don't know about Windows 7, but there is an interpreter online, in case you want one. http://brainfuck.tk/ On Tue, Mar 15, 2011 at 5:15 PM, cegprakash cegprak...@gmail.com wrote: do anyone knows a brainfuck compiler for windows 7? I need a link to download it. I'm new to this group. Hope you guyz will help. -- 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.
Re: [algogeeks] Brainfuck compiler
Ahhh I see. Thanks On 15 March 2011 16:11, Ankur Khurana ankur.kkhur...@gmail.com wrote: @carl : may be this : https://www.spoj.pl/problems/SBSTR1/ On Tue, Mar 15, 2011 at 9:35 PM, kumar anurag anurag.it.jo...@gmail.comwrote: I used a prgram of c which converts brainfuck program to C progaram which u can compile using gcc On Tue, Mar 15, 2011 at 9:12 PM, Carl Barton odysseus.ulys...@gmail.comwrote: Just out of interest. What are you planning to write in brainfuck? On 15 March 2011 14:58, Natansh Verma natansh.ve...@gmail.com wrote: I don't know about Windows 7, but there is an interpreter online, in case you want one. http://brainfuck.tk/ On Tue, Mar 15, 2011 at 5:15 PM, cegprakash cegprak...@gmail.comwrote: do anyone knows a brainfuck compiler for windows 7? I need a link to download it. I'm new to this group. Hope you guyz will help. -- 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. -- Kumar Anurag -- 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.
Re: [algogeeks] Re: Serialization in BT
If it's in array representation the simplest way is just serialise the array? Linked i'd agree with snehal On 9 January 2011 11:54, juver++ avpostni...@gmail.com wrote: And this: http://www.cs.usfca.edu/~galles/cs245/lecture/lecture9.pdfhttp://www.cs.usfca.edu/%7Egalles/cs245/lecture/lecture9.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: 1s and 0s
Could be modelled as a deterministic finite statemachine to be checked in linear time. On 22 December 2010 07:47, snehal jain learner@gmail.com wrote: @above nice approach :) On Wed, Dec 22, 2010 at 1:06 PM, juver++ avpostni...@gmail.com wrote: Use bits manipulation tricks. 1. There is a way to remove a group of consecutive 1's from the right: A = n (n + 1). Then check if A==0 then OK. 2. Second approach: B=n+1, check if B (B-1) (this checks if B is a power of 2, so it contains only 1 set bit) is zero then OK. -- 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] Re: 1s and 0s
This is simply a decision problem is it not? the above sorting would require n log n for comparison sorting where as a decision could be simply done in linear time and space. Please correct me if i'm wrong On 22 December 2010 19:17, Anand anandut2...@gmail.com wrote: http://anandtechblog.blogspot.com/2010/12/sort-array-containing-1s-and-0s.html On Wed, Dec 22, 2010 at 6:47 AM, Carl Barton odysseus.ulys...@gmail.comwrote: Could be modelled as a deterministic finite statemachine to be checked in linear time. On 22 December 2010 07:47, snehal jain learner@gmail.com wrote: @above nice approach :) On Wed, Dec 22, 2010 at 1:06 PM, juver++ avpostni...@gmail.com wrote: Use bits manipulation tricks. 1. There is a way to remove a group of consecutive 1's from the right: A = n (n + 1). Then check if A==0 then OK. 2. Second approach: B=n+1, check if B (B-1) (this checks if B is a power of 2, so it contains only 1 set bit) is zero then OK. -- 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.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.