Re: [algogeeks] Technology for Graphical User Interface on Linux
Not the right forum.. But you can try Qt if licensing isn't a concern. Or GTK+. On Mon, Oct 6, 2014 at 8:03 PM, sagar sindwani sindwani.sa...@gmail.com wrote: Hi all, I am looking for a good tool or language to create graphical user interface in linux environment. Java can be used to achieve the purpose, Can you please let me know any other technology for such purpose. Thanks Sagar -- 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.
[algogeeks] finding anagrams in a list of words
Hi all, I am stuck with a question for a long time...can someone provide the best algorithm for this.. Question).. find all the anagrams in a list of words. The algorithm should be efficient as the list can be very large. -- 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/-/c4cSIMcBYLEJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] How to design snake and ladder game using OOPS
Hi can any one help me, in how to answer these type of questions. Like how do you design Snake and Ladder game, or a Chess Game. What classes you will use, which methods and variables will be private/ public. Its not about coding, its about designing. Please 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.
Re: [algogeeks] Re: Reading Huge input from the terminal in least time.
If you're working on Linux then there's asynchronous I/O functions that do well.. http://www.gnu.org/s/libc/manual/html_node/Asynchronous-I_002fO.html#Asynchronous-I_002fO http://www.gnu.org/s/libc/manual/html_node/Asynchronous-I_002fO.html#Asynchronous-I_002fOWindows might have similar functionality. On Thu, Apr 21, 2011 at 6:41 AM, Gary Drocella gdroc...@gmail.com wrote: You could just use a pseudo-random number generator to fill in the array. You may also want to consider the data type (each unsigned int would be 4 bytes, where a unsigned char would be 1 byte). Or, If it's truly necessary to read this much data from the console... You could use unix pipes, (cat file.out | ./myprog) pipes in unix shells will redirect from the standard i/o... The format of the file.out should be input0 input1 input2 ... inputn where I guess in your case n = 10^6 That should work, but I don't code in c++ (only c) On Apr 19, 10:11 pm, shubham shubh2...@gmail.com wrote: Hello Geeks, Suppose we have a 2-d array arr[1000][1000] capable of storing 10^6 elements in it. Input is supplied one row at a time. Then what is the best possible way to read this much data in the least amount of time as scanf() or cin takes a lot of time? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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: An interesting question
If the diagonal elements of the matrix are all 0s, then you'd have to set every element in the matrix to 0 (i.e. O(N^2) operations ). I don't think, therefore, that we can do better than O(N^2). The best we can do is to perhaps, make it output sensitive. On Sun, Feb 27, 2011 at 6:14 PM, pacific pacific pacific4...@gmail.comwrote: 1. do operation on all the values in each column and store it in the first row of each column 2. do operation on all the values in each row and store it in the first column of each row. (when writing at a[0][0] do operation with the value computed at 1.) 3. Now to find out the value at a[i][j] ,you need to do a[i][0] a[0][j] On Sun, Feb 27, 2011 at 12:03 PM, Rajnish rajnish.i...@gmail.com wrote: 1.) Traverse the whole matrix and replace each 0 value with -1. 2.) Traverse the matrix again,all the 1 values are replaced with 0 in the row and column of the index where a -1 value is found. 3.) Set all -1 values to zero and we have the output array. time complexity: O(n^2) space complexity: O(1) On Feb 27, 2:29 am, gaurav gupta 1989.gau...@googlemail.com wrote: A NxN binary matrix is given. If a row contains a 0 all element in the row will be set to 0 and if a column contains a 0 all element of the column will be set to 0. You have to do it in O(1) space. example : input array : 1 0 1 1 0 0 1 1 1 0 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 result array : 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 1 0 Thanks Regards, Gaurav Gupta -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- regards, chinna. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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 print path of a node
Like Adam says, the complexity will depend upon what your input looks like, as also, what exactly is the problem. If you are required to do a search for the keys first, then it's going to be really expensive. If on the other hand, you already have the two pointers, and if you do have the parent pointers, then it can be done in O(d) on the depth of the tree (worst case O(n)). On the other hand, if the example that you gave is *the *tree, then the path from the nth node (the node with key = n) in the tree can be quite simply be determined in O(log n) time - both because the tree is balanced, and because the indices are integer positions and one simply do integer division by 2 right up to key=1 to discover the path to the root. On Wed, Sep 8, 2010 at 12:31 AM, Adam wangyanadam1...@gmail.com wrote: What do you input into the algorithm corresponding to the specific node? A pointer pointing to the node or just the key value of that node used for query? These two situations are totally different in which the former one can be handled in O(d) time complexity and the other one will be O(2^d) complex, where d is the depth of the specific node. On Sep 6, 11:08 pm, Debajyoti Sarma sarma.debajy...@gmail.com wrote: How to print the path from root to a specific node in a binary tree?? I want to store the path in a array[] of node*. can it b done in O(n) or less? Remember it's not BST. 1 / \ 2 3 / \ / \ 4 5 67 / \/ \ / \ / \ 8 9 10 11 12 13 14 15 path of 6 will b 1,3,6. path of 9 will be 1,2,5,11 -- 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] There is an array of odd and even numbers. Now, sort them in such a way that the top portion of the array contains odd numbers, bottom portion contains even numbers
Rohit's approach put into a typical c++ construct...
inline is_odd(int x)
{
return ((x 1) == 1);
}
struct new_compare {
bool operator () (int i, int j) {
bool b_i_odd = is_odd(i);
bool b_j_odd = is_odd(j);
if ((b_i_odd b_j_odd) || (!b_i_odd !b_j_odd))
return (i j);
else if (b_i_odd !b_j_odd)
return 1;
else
return 0;
}
};
std::vectorint array_to_sort;
std::sort( array_to_sort.begin(), array_to_sort.end(), new_compare );
Of course, everything written above can be stated as a C program, or an
algorithm.
The sort( ) function can be replaced with any in-place sorting algorithm,
the new_compare class with either a function ptr, or a simple in-place
check.
On Tue, Jun 22, 2010 at 11:10 PM, Naveen Kumar
naveenkumarve...@gmail.comwrote:
Hi Rohit,
Can you explain your approach a bit more?
On Sun, Jun 20, 2010 at 2:48 PM, Rohit Saraf
rohit.kumar.sa...@gmail.com wrote:
Why not just change the definition of when one number is bigger than
another
and do normal sort ?
I guess that is better and simpler.
--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer Science and Engineering
IIT Bombay
http://www.cse.iitb.ac.in/~rohitfeb14
On Sun, Jun 20, 2010 at 7:52 AM, Anurag Sharma anuragvic...@gmail.com
wrote:
Keep 2 pointers 'start' and 'end' and make them point to start and
beginning of the array.
Now keep decresing end pointer until an odd element is found
Keep increasing the start pointer until an even element is found
swap the elements at start and end
Continue the above 3 steps till startend
Now the start/end points to a border element which divides the array in
2
parts, 1st have having all odd numbers and 2nd half with all even
numbers.
Now use any inplace sorting algorithm to sort in descending order the
portion containing all odd numbers and in increasing order the portion
containing all even numbers.
Hope its clear.
Anurag Sharma
On Sun, Jun 20, 2010 at 2:15 AM, vijay auvija...@gmail.com wrote:
There is an array of odd and even numbers. Now, sort them in such a
way that the top portion of the array contains odd numbers, bottom
portion contains even numbers. The odd numbers are to be sorted in
descending order and the even numbers in ascending order. You are not
allowed to use any extra array and it has to use a conventional
sorting mechanism and should not do any pre or post processing
--
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.
--
Cheers
Naveen Kumar
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.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] concatenation of 2 circular linked lists
Concatenation of two lists without traversing even one of the lists
completely requires a pointer to the last element of the first list (first,
as in the one that is to be attached in front of the other list). This is
only possible if either, there's a *last *pointer for the lists, or the list
is a double-linked list (besides being a circular list) where each node
stores pointers to both the previous and the next nodes.
Concatenation in a doubly-linked circular list is a simple exchange of
pointers as illustrated below
list Concat(list1, list2)
{
last1 = list1.head.prev
last2 = list2.head.prev
last1.next = list2.head
last2.next = list1.head
list1.head.prev = last2
list2.head.prev = last1
return list1
}
Depending upon your implementation, there would have to be checks for NULL
pointers. Also, one may use pointer swapping to achieve the effect in, for
example, a C implementation.
Freeing up a list on the other hand requires a full traversal, no matter
what kind of list it is. That's because each node was allocated separately
(that would be the whole point of having a dynamically created list).
thanks,
mayur
On Fri, Jun 11, 2010 at 1:23 PM, Raj N rajn...@gmail.com wrote:
Hi,
I came across this statement that using circular lists, concatenation
can be done without traversing either list. The same case with freeing
the entire list.
Can someone elaborate on this ?
--
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: binary nos
A more theoretical answer to the question can be the following: Let's try to construct a tree for all such possible sequences. Level 0 = 0 or 1 Level 1 = 01 0 Level 2 =0 1 0 01 Level 3 = 0 1 0 0 1 0 10 Simple observation will tell you that for every 0 in a position, the next position can have either 0 or 1, but for a 1 in the position, the next bit *has *to be a 0. -- (1) Let us call the function N0(p) to be the number of 0s at level (position) p in the sequence; N1(p) to be the number of 1s at level p. The total number of nodes at level p is then N(p) = N0(p) + N1(p). It is also clear from statement (1) that N0(p) = N0(p-1) + N1(p-1)--- (2) and N1(p) = N0(p-1)-- (3) i.e. the number of 0s in the next level equal to the number of 0s in the previous level plus the number of 1s in the previous level, whereas the number of 1s is equal to the number of 0s in the previous level. Thus, combining (2) and (3), we have... N(p) = N0(p-1) + N1(p-1) + N0(p-1) --- (4) Now, N0(p-1) + N1(p-1) is really N(p-1) - i.e. the total number of possible sequences of length p. Also, N0(p-1) = N0(p-2) + N1(p-2) = N(p-2) from (2) Therefore, (4) reduces to N(p) = N(p-1) + N(p-2) The above, you would recognize as the generative recursive form of the sequence of fibonacci numbers. thanks, mayur On Fri, Jun 11, 2010 at 2:05 PM, Debajyoti Sarma sarma.debajy...@gmail.comwrote: clarification to all n=1 0,1 no of sequence =2 n=2 00,01,10 no of sequence =3 n=3 000,100,010,001,101 no of sequence =5 n=4 ,1000,0100,0010,0001,1010,0101,1001 no of sequence =8 n=5 0,1,01000,00100,00010,1,10100,10010,10001,01010,01001,00101,10101 no of sequence =13 so its coming in fibo no. no of sequence =fibo(n+2)if you exclude 0 from fibo no no of sequence =fibo(n+3)if you include 0 in fibo no On Fri, Jun 11, 2010 at 1:55 PM, Debajyoti Sarma sarma.debajy...@gmail.com wrote: @Rohit Saraf i understood the question. Superb solution by u. On Thu, Jun 10, 2010 at 8:59 PM, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: write an efficient algo to compute no. of sequences of n binary digits that do not contain 2 1's in a row. eg 111 is invalid whereas 1001001 is valid. HERE the number of sequences comes to be a fibonacci number , precisely fib(n+2). So this prob is equivalent to finding fibonacci numbers -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14http://www.cse.iitb.ac.in/%7Erohitfeb14 On Thu, Jun 10, 2010 at 11:47 AM, Sundeep Singh singh.sund...@gmail.com wrote: @rohit: fibonacci sequence may be the answer to the prob, but I am curious why? I haven't come across any such fib sequence property... On Wed, Jun 9, 2010 at 9:16 PM, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: @junta : are fibonacci sequence is the answer of the prob, it is not used :D -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14http://www.cse.iitb.ac.in/%7Erohitfeb14 On Wed, Jun 9, 2010 at 9:13 PM, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: @debajyoti: read the prob before posting -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14http://www.cse.iitb.ac.in/%7Erohitfeb14 On Wed, Jun 9, 2010 at 2:37 PM, Debajyoti Sarma sarma.debajy...@gmail.com wrote: First 20 fibo no as follows with binary form 0 = 0 1 = 1 1 = 1 2 = 10 3 = 11 5 = 101 8 = 1000 13 = 1101 21 = 10101 34 = 100010 55 = 110111 89 = 1011001 144 = 1001 233 = 11101001 377 = 10001 610 = 1001100010 987 = 011011 1597 = 1100001 2584 = 10111000 4181 = 101010101 Now please explain how fibo no is coming under consideration.Both kind of no is mixed here. On Wed, Jun 9, 2010 at 8:02 AM, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: Fib comes because she wants the number of such sequences -- -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14http://www.cse.iitb.ac.in/%7Erohitfeb14 -- 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
Re: [algogeeks] Re: binary nos
Oh! Forgot to mention that the count of the leaves of the tree, gives the number of possible sequences (as required to be determined by the question) On Fri, Jun 11, 2010 at 10:02 PM, Mayur mayurhem...@gmail.com wrote: A more theoretical answer to the question can be the following: Let's try to construct a tree for all such possible sequences. Level 0 = 0 or 1 Level 1 = 01 0 Level 2 =0 1 0 01 Level 3 = 0 1 0 0 1 0 10 Simple observation will tell you that for every 0 in a position, the next position can have either 0 or 1, but for a 1 in the position, the next bit *has *to be a 0. -- (1) Let us call the function N0(p) to be the number of 0s at level (position) p in the sequence; N1(p) to be the number of 1s at level p. The total number of nodes at level p is then N(p) = N0(p) + N1(p). It is also clear from statement (1) that N0(p) = N0(p-1) + N1(p-1)--- (2) and N1(p) = N0(p-1)-- (3) i.e. the number of 0s in the next level equal to the number of 0s in the previous level plus the number of 1s in the previous level, whereas the number of 1s is equal to the number of 0s in the previous level. Thus, combining (2) and (3), we have... N(p) = N0(p-1) + N1(p-1) + N0(p-1) --- (4) Now, N0(p-1) + N1(p-1) is really N(p-1) - i.e. the total number of possible sequences of length p. Also, N0(p-1) = N0(p-2) + N1(p-2) = N(p-2) from (2) Therefore, (4) reduces to N(p) = N(p-1) + N(p-2) The above, you would recognize as the generative recursive form of the sequence of fibonacci numbers. thanks, mayur On Fri, Jun 11, 2010 at 2:05 PM, Debajyoti Sarma sarma.debajy...@gmail.com wrote: clarification to all n=1 0,1 no of sequence =2 n=2 00,01,10 no of sequence =3 n=3 000,100,010,001,101 no of sequence =5 n=4 ,1000,0100,0010,0001,1010,0101,1001 no of sequence =8 n=5 0,1,01000,00100,00010,1,10100,10010,10001,01010,01001,00101,10101 no of sequence =13 so its coming in fibo no. no of sequence =fibo(n+2)if you exclude 0 from fibo no no of sequence =fibo(n+3)if you include 0 in fibo no On Fri, Jun 11, 2010 at 1:55 PM, Debajyoti Sarma sarma.debajy...@gmail.com wrote: @Rohit Saraf i understood the question. Superb solution by u. On Thu, Jun 10, 2010 at 8:59 PM, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: write an efficient algo to compute no. of sequences of n binary digits that do not contain 2 1's in a row. eg 111 is invalid whereas 1001001 is valid. HERE the number of sequences comes to be a fibonacci number , precisely fib(n+2). So this prob is equivalent to finding fibonacci numbers -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14http://www.cse.iitb.ac.in/%7Erohitfeb14 On Thu, Jun 10, 2010 at 11:47 AM, Sundeep Singh singh.sund...@gmail.com wrote: @rohit: fibonacci sequence may be the answer to the prob, but I am curious why? I haven't come across any such fib sequence property... On Wed, Jun 9, 2010 at 9:16 PM, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: @junta : are fibonacci sequence is the answer of the prob, it is not used :D -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14http://www.cse.iitb.ac.in/%7Erohitfeb14 On Wed, Jun 9, 2010 at 9:13 PM, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: @debajyoti: read the prob before posting -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14http://www.cse.iitb.ac.in/%7Erohitfeb14 On Wed, Jun 9, 2010 at 2:37 PM, Debajyoti Sarma sarma.debajy...@gmail.com wrote: First 20 fibo no as follows with binary form 0 = 0 1 = 1 1 = 1 2 = 10 3 = 11 5 = 101 8 = 1000 13 = 1101 21 = 10101 34 = 100010 55 = 110111 89 = 1011001 144 = 1001 233 = 11101001 377 = 10001 610 = 1001100010 987 = 011011 1597 = 1100001 2584 = 10111000 4181 = 101010101 Now please explain how fibo no is coming under consideration.Both kind of no is mixed here. On Wed, Jun 9, 2010 at 8:02 AM, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: Fib comes because she wants the number of such sequences -- -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14http://www.cse.iitb.ac.in/%7Erohitfeb14 -- You received this message because you are subscribed to the Google
Re: [algogeeks] Re: array question
@Anand Depending upon the sequence of data in the input, an insertion/search into the (unbalanced) BST will take O(n) time causing the overall complexity to shoot up to O(n^2) for each element counted once. Sourav's approach requires a balanced binary search tree. @Divya.. If you know something about the numbers, one could do better. For example, if you knew that they're all positive short integers, Anand's original approach (of using an array indexed by the numbers themselves) will be great (for a storage cost of about 64KB). This is sometimes more acceptable, for example, if your original input is like a million integers. On Tue, Jun 8, 2010 at 5:48 AM, Anand anandut2...@gmail.com wrote: @souravsain :Your approach works really well.. Here is the Implementation: http://codepad.org/ricAcQtu On Sun, Jun 6, 2010 at 11:40 AM, souravsain souravs...@gmail.com wrote: @divya:go through the elements and keep inserting them in a BST. While inserting if elements already exists in BST, increase its frequency (Node of BST has element a nd frequency). Also if elemengs is newly inserted then also place it in a seperate array. So this array (say Array M) will become something like 12,5,6. This array will give order of first occurance of numbers. This whole process will take nlogn (BST creation assuming worst case that all elements are uinque in the input array). Once done, scan through each element in array M, find its corrosponding element in BST (logn) which will give the frequency. Fill those many indexes in input array with array M[i]. If all elements are uinque, this will also take nlogn. Else if input array has m distince elements, which will require us to look into BST for m times. hence entire process has time compelxity: O(nlogn + nlogn)= O(2nlogn) Space complexity: O(2n) [1 for BST and 1 for array M, worst case when all elements are unique in inpur array). Let me know your comments if any or any better appraoch as this once may have improvements. On Jun 6, 7:47 pm, divya jain sweetdivya@gmail.com wrote: output willl be 12 12 5 6 6 On 6 June 2010 18:27, souravsain souravs...@gmail.com wrote: @divya: Does your problem require the output to be sorted also? What will be the output required if inout is 12,5,6,12,6? Will it be 12,12,6,6,5 or 12,12,5,6,6,? Sain On Jun 6, 12:01 am, divya sweetdivya@gmail.com wrote: Given an array with some repeating numbers. Like 12,6,5,12,6 output: 12,12,6,6,5 12 shud come before 6 since it is earlier in list. So cant use a dictionary -- 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 algogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.- Hide quoted text - - Show quoted text - -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to 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] Maintaining frequency of millions of user
We have a server hit by millions of users. Sever log files contains the user ids of all of them. How do we find the frequency of login of each user. What will the most efficient way to store the users, and access them to find their frequency(The log files are very huge!!) I thought of using B+ tree indexing with user ids as the key. Leaf nodes will have the pointers to bucket of user ids. One item of bucket will contain user id and frequency of this user. For insertion, search complexity will be ~O(logn) Any potential problem with approach? Are there any better approach to tackle this problem? Not problems really, but opportunities. Here're a few things: 1. They're append-only (no inserts, no deletes). Why then have a B+ tree on the log file itself, which is a structure optimized for both retrieval and inserts? 2. If all that you want to query is the frequency of login of each user, one might ask the following questions: i) How often do you want this frequency data? Is the data required to be updated in real-time? ii) Is it okay to query this data each time your log's rotated? If you require the data as and when it's created (meaning as soon as it is logged), it may be a good idea to change the application receiving the call to explicitly update the frequency, in say, a database. On the other hand, if you want it periodically, you can simply run a script/program that takes the old size of the log file as input, and begins scanning the log from that offset, thus saving you time. The frequency data itself can be stored in a hash file / b+ tree or whatever else you'd like (so that it can be updated). If you still wish to index your log files, search for Write-Once Read-Many (WORM) data structures on the web. Apologies for the non-algorithmic nature of my response, if it isn't apt for the group. On Wed, Dec 9, 2009 at 3:54 PM, Rohit Saraf rohit.kumar.sa...@gmail.comwrote: if you don't know abt fibonacci heaps then check out http://en.wikipedia.org/wiki/Fibonacci_heap Rohit Saraf Sophomore Computer Science and Engineering IIT Bombay -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Terms extraction
If the number of articles to do this is more than one, and if space isn't much of a concern, one might considering constructing a trie structure for the dictionary (this would take an O(nT) worst case time where n is the length of the longest word in the dictionary. However, for subsequent uses with multiple articles, this cost will get amortized. After the trie's constructed, each search would cost O(n) time, for a total search time of O(nW). The total cost with A articles would average out to about O(nT/A) + O(nW). If A=n, then the cost of creating the dictionary trie would amortize down to O(T). On Sun, Jun 15, 2008 at 8:15 AM, billjeff [EMAIL PROTECTED] wrote: W words in article. If we do not sort the words, it will take O(WT); if we sort words in each atilcle, it is O(Wlg(W)+Tlg(W)); or maybe hash is another choice, it takes O(W+T). If T is small, just use O(WT) way. Otherwise, use sort or hash instead. Roy M wrote: Recently need to think of an efficient way to exact terms from an article, and do some processing on it, to make it simple, terms translation 1. Given I have an article of 1000-2000 words, let the number of words be W 2. I have a dictionary which consists of all term, let the number of terms be T 3. For each term appear in the article, translate using the dictionary to replace the term in the article So assuming three cases, a. W T b. W ~ T c. W T What kind of algorithms would be suitable for each of them? --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: I'm stuck with this problem
Google for connected components... you'll probably land up some method using disjoint set structures and depth-first search... On 10/16/07, Muntasir Azam Khan [EMAIL PROTECTED] wrote: On Oct 14, 10:18 am, Legend [EMAIL PROTECTED] wrote: Suppose that I have some data: 12,30 12,45 2,3 7,8 3,9 30, 8 45,54 56,65 Where (a,b) indicates that a is connected to b. I want to get all connected nodes to one point. For instance, the output of the above example should be something like: Group 1 2,3 3,9 Group 2 12,30 12,45 30,8 7,8 Group 3 45,54 Group 4 56,65 The order is not important as long as the whole group stays together. Reason why they are grouped like that: 1. 2 is connected to 3 and 3 is connected to 9 and so we put all the three, i.e. 2,3,9 into one group. 2. 12 is connected to 45 and 12 is also connected to 30 so we put these in the same group but 30 is connected to 8 and 8 is connected to 7 so ultimately we put all these into the same group. 3. 45 and 54 are connected but not related to any other numbers so we put them into another group 4. 56 and 65 are connected but not related to any other numbers so we put them into another group I am unable to figure out an algorithm for this. Can someone guide me? It seems to me that you are looking for all maximally connected subgraphs of a graph. Flood fill should be the easiest/fastest way to solve this one. Hope this helps, Muntasir --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Google Interview Question: find shortest summary containing all key words
Another possibility is to first pre-process the keywords into automaton-like structure (Google for Aho Corasick string matcher), and then use it over the document. This would probably be helpful only if the number of keywords is much smaller than the document itself.. On 9/25/07, daizisheng [EMAIL PROTECTED] wrote: Vishal 写道: Hash table should give you O(1) insertion and search complexity; which is what we need, right? There is no constraint on space complexity, I believe. On 9/24/07, * daizisheng* [EMAIL PROTECTED] mailto:[EMAIL PROTECTED] wrote: the problem is you need a hash table to maintain all the keywords,:) because they do not have to be a single characters, or you can store them in array, but then you need binary search,:) Vishal 写道: How about keeping two pointers - startp and endp. Keep a count of frequencies of keywords between startp and endp, both inclusive. We can use an array / hash table for this. Now, the minimum length substring has to start with a keyword and has to end with a keyword. 1. Initially startp=0 and endp=1. L = infinity 2. Increment endp till you encounter a keyword or it exceeds the total length. Update frequencies. Check if you have all the keywords. (This can be done in O(1) using a bitmap or similar). If it exceeds the total length, QUIT. 3. If the str(startp,endp) contains all keywords and length L, save values of startp and endp. 4. Now, increment startp, till you get a keyword. If the str(startp,endp) still contains all keywords, update saved values of startp and endp. 5. Repeat step 4 till str(startp,endp) does NOT contain all keywords. 6. Goto step 2. The final values of startp and endp should give you the minimum summary. Since both values go from 0 to N-1, its O(N). ~Vishal On 9/24/07, *daizisheng* [EMAIL PROTECTED] mailto:[EMAIL PROTECTED] mailto:[EMAIL PROTECTED] mailto:[EMAIL PROTECTED] wrote: I think hash method is ok, at lease in expectation way it's O(n) why not use it? it's very effeciently I think there should be some worst case O(n) algorithm, but it will be more complex and not as effecient as the above one in practise Sticker 写道: Declare: this question is originally from Google. The original form is: given a document, how to find a shortest summary containing all the key words. After translated, it will be: given a sequence, how to find a shortest substring that contains all the items required. Example: a sequence abaccdefgacel and a set of key words a, c, d and e. The shortest substring contianing all of the key words is accde. Find one of such shortest substrings. In the original question, there is time complexity boundary O(N), where N is the length of the sequence. To me, this problem is rather questionable. So far my solution requires a hash table that gives no conflict and can locate a key word in O(1) time. Otherwise the time complexity will definitely be related to the number of key words. Does anyone have idea for a O(N) algorithm to solve this problem? yes, that's we need. but seems the starter of this thread who did not like hash,:) --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Time complexity
Don't know if the O-notation is also defined for complex functions. Well, if it isn't, here's a possibility: - (please correct me if I am wrong here.. ) For sqrt( x ) to be real, x needs to be 0 = log(log(m)) / log(m) 0 But we also know that log(m) log(log(m)) for all values of m for which log(log(m)) is defined. = log(log(m)) / log(m) 1 Also sqrt(x), for 0x1 is also in the interval (0, 1) = we have a bound on the O( sqrt(blah..blah.blah..) ) = O(1) Thus, the recurrence reduces to T(m) = T(m/2) + O(1) This happens to be a lot easier to solve.. Thanks, mayur On 6/12/07, Phanisekhar B V [EMAIL PROTECTED] wrote: Hi Ray, Can u do this without using Master theorem? I also need to fine the time complexity of problems like: T(m) = 2T(m/2) + O( m^2 * squareroot((log log m) / (log m)) ) basically i need a solution without using master theorem. Regards, Phani On 6/12/07, Ray [EMAIL PROTECTED] wrote: I think it's O(n). Because the order of squareroot((log log m) / (log m)) is less than m's. T(n) = a T (n/b) + f(n) 1. O(n ^(lgb/lga) ) O(f(n)) T(n) = O(n ^(lgb/lga)) 2. O(n ^(lgb/lga) ) = O(f(n)) T(n) = O(lg(n)*f(n)) 3. O(n ^(lgb/lga) ) O(f(n)) T(n) = O(f(n)) The problem fits the 1st situation. So it's O(n). On Jun 12, 4:11 pm, Phanisekhar B V [EMAIL PROTECTED] wrote: Adiran, Yes u r right. Let T(1) = 1. On 6/12/07, Adrian Godong [EMAIL PROTECTED] wrote: You should provide the limit/point where T(m) is constant. Say T(1) = 1, or something else. Only then we can calculate the time complexity. On 6/12/07, Phanisekhar B V [EMAIL PROTECTED] wrote: How can i calculate the time complexity of the following problem? T(m) = 2T(m/2) + O( squareroot((log log m) / (log m)) ) The above problem contains double log and squareroot. Regards, Phani Microsoft MVP https://mvp.support.microsoft.com/profile/Adrian https://mvp.support.microsoft.com/profile/Adrian- Hide quoted text - - Show quoted text - --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Path finding in map
Hi, The input to path-planning algorithms is often a graph (graph, as in, nodes and edges). For a given map, one needs to first construct the graph; one thumb rule is to establish all discrete reachable points (like a cross-road, or an avenue) as vertices. Essentially, starting from your source, create connections to all the points that are reachable. Another heuristic is to eliminate points which are on the same path (line or curve or whatever), and treat only the end points as vertices. Once you have a graph, then based on the optimization criterion (whether it's the total weight of the path, or the number of hops), you decide the appropriate search algorithm (which, as mentioned earlier, includes Dijkstra's algo among others). There are some randomized algorithms for faster path-planning ...google for them if you wish... Thanks, Mayur On 4/19/07, Lukas alkauskas [EMAIL PROTECTED] wrote: I haven't any problems, just i like to know what kinda algos use to create path finding in _city map_, how to define map data, like nodes? (x, y), street have : street start x, start y, and street end x, end y, and homes near street just nodes from street? But how then with streets whom is like half circle, circle or irregularly - shaped shape - i think need more nodes but how to define where i need to put that node in kinda circle form shape, or very smooth street. Maybe any one knows, this kinda information, maybe anyone does any similar project. Please give your suggestions. On 4/19/07, chitta koushik [EMAIL PROTECTED] wrote: Hi, please explain your problem clearly..u have just given the mapthere are many popular alogs...like Travelling salesperson algo,Dijkstra shortest path,Bellmond ford shortest path,All pairs shortest path depending on the problem.. cheers, koushiki chitta On 4/18/07, Lukas alkauskas [EMAIL PROTECTED] wrote: Hello, What suggestions you have for path finding like this? algos, etc. -- You can contact me by : msn messanger: [EMAIL PROTECTED] yahoo messanger: [EMAIL PROTECTED] ICQ: 443443043 Google Talk: [EMAIL PROTECTED] Skype: halfas.online.now IRC: HalFas` (irc2.omnitel.net) Home page: http://www.revidev.com/halfas/ One's leisure project: http://rvision.gamedev.lt/RVengine -- *** 30 years from now it doesn't matter which shoe you wore,which branded jean you wore..what all matters is WHAT YOU HAVE LEARNED AND HOW YOU HAVE USED IT. http://students.iiit.ac.in/~koushik_c -- You can contact me by : msn messanger: [EMAIL PROTECTED] yahoo messanger: [EMAIL PROTECTED] ICQ: 443443043 Google Talk: [EMAIL PROTECTED] Skype: halfas.online.now IRC: HalFas` (irc2.omnitel.net ) Home page: http://www.revidev.com/halfas/ One's leisure project: http://rvision.gamedev.lt/RVengine --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Reading a PDF file
This isn't exactly the list for this question. However, search (google) for PDF reference... should help you get there.. Thanks, mayur On 4/20/07, chitta koushik [EMAIL PROTECTED] wrote: Hi, I want to read a PDF file contents and want to print that in a text file...i.e if a PDF file contains abcd i want to read that and store in text file.. i think we can face problem in knowing how much bytes the PDF header has and etcdoes any know that please help thanks in anticipation... cheers, koushik chitta -- *** 30 years from now it doesn't matter which shoe you wore,which branded jean you wore..what all matters is WHAT YOU HAVE LEARNED AND HOW YOU HAVE USED IT. http://students.iiit.ac.in/~koushik_c --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: a data structure for phone directory
A good hash organization may also do well. (http://www.cse.yorku.ca/~oz/hash.html). One needs to decide on the criterion on which to measure the goodness. A trie would also be a good solution, provided the implementation is done the right way... http://en.wikipedia.org/wiki/Patricia_trie You could also concoct a data-structure that combines the trie and the b-tree approach (insertions would be expensive). Thanks mayur On 2/14/07, Karthik Singaram L [EMAIL PROTECTED] wrote: It does depend on the size of the problem you have in mind. Tries can be expensive for names depending on the sparseness of the data set, you may waste a lot of pointers. If you use B-Trees they may be good in such cases. B-trees are generally a bit better when it comes to data stored in a disk with the index alone being cached in memory. --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: time complexity of algorithms
1.) If you're talking about search using a tree with each node having degree 4, then the best-case complexity is indeed O(1). Why, the first node (the root) could be the one that you're looking for. 3.) Yes indeed. Since, your tree doesn't seem to have any branching logic (like a BST does), the complexity would be O(n). On 12/16/06, programming [EMAIL PROTECTED] wrote: Hi all, i have 3 short questions that i would like answered. 1) What is the best case complexity for a tree of degree(4). I said B(n) = n. Is it B(n)=1? I think it is the first case 2) Also, is the average case for a doubly circular queue A(n)=n+1/2 3) Lastly, is the worst-case of a search tree to degree 4 W(n)=n Cheers, Peri --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups-beta.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: doubt boss...
When you declare an array int a[3] or whatever, it only says you asked for 3 locations (of type int) to belong to your program. In other words, you asked for 3 locations saying that a is an array variable which can be used to access 3 locations legitimately. However, here's what happens internally. When you say a[i], the compiler actually converts it into a pointer and says *(a+i). (Don't believe me? try out 2[a] instead of a[2].. because both get converted to *(a+2)... ). Ok. So, when _you_ make a reference to say a[5] - the compiler converts it into *(a+5). Now, the compiler DOES NOT know if _you_ own that location... A pointer is a free (and shameless) guy... so it can be made to point any location. And the compiler doesn't stop that.. so, a[5] is valid as far as the compiler is concerned. However, the the operating system doesn't always like it, and if you (i.e. the program) doesn't OWN the location, it pukes out (like a SEG fault, in Linux). If you're on windows - then I donno what happens... On the more serious side of it -- a[5] is a valid reference because a is treated as a pointer variable, and (a+5) is a valid (well, not always) address in the memory. Therefore, theoretically, you CAN access a[5] using a pointer variable as a. However, the memory location may belong to some other variable in your program - in which case the data could get corrupted, or it may belong to another program (multi-programming) and the operating system should deny access causing your program to fail at run-time. On 5/26/06, Sriram narasimhan [EMAIL PROTECTED] wrote: hi guys, i wrote a program for arrays and i declared only a[3]. but my array accepts a[5]=10; statements and other statements...how is that possible..arrays are considered as continuous memory of same datatype isnt it...but the array a[3] becomes discontinuous... wat could be the possible reasons for the working of such statements... Sriram.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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Best Algorithm to find a Prime Number
Hi, If you are looking for primality testing, google for the paper Prime is in P. The original paper's by three IIT-Kanpur people. The papers that followed up give the best algorithms for checking primality. If you are looking for prime number generation, look out for sieve methods - especiialy generalized sieves. On 4/29/06, B. P. TBC [EMAIL PROTECTED] wrote:This algorithm (in Pascal) returns True, if x is a prime number, and returns False, if x isn't prime.function Prime(x: word): boolean;var i: word; v: boolean;Begin v := False; if x=1 then v := True; for i:=2 to round(sqrt(x)) do Begin if x mod i = 0 then v := True; End; Prime := not v;End; --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Finding the k largest/smallest elements in the array !
Donno if it's the right thing to comment here, but some of you might want to consider what Meggido did for solving some geometric problems - it's called parametric search... do google for it - it's very very interesting. His algorithm simulates a parallel algorithm on a serial system, still achieving a nice reduction in the total time complexity.On 4/25/06, Mukul Gandhi [EMAIL PROTECTED] wrote:I think you are right. Thanks for your comments..Regards, Mukul --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: I guess, It is a tough one!!! Lets see who solves this
I donno if it's so tough... Maybe I'm wrong.! Or I may have missed on something. Here's my attempt.
We have a0 = a1 = ... = an
and b0 = b1 = ... = bn
Therfore, the largest ai + bj would be (an + bn)
1: count - 0
2: i - n, j - n
2: while count n
3: select ai + bj.
4: if a(i-1)
b(j-1) // ofcourse, the boundary conditions are
missing - easy to put them..
5: then j - j -1
6: else i - i-1
7: count - count + 1
i.e. the next largest ai+bj, after an+bn would either be a(n-1)+bn, or
an+b(n-1). Choose to use the one which maximizes the sum. It's a simple
greedy algorithm.
On 4/3/06, aamir [EMAIL PROTECTED] wrote:
Two sets {ao,a1,a2,..an} and {b0,b1,b2,...bn} having integers inincreasing order (Sorted arrays of size n).We have to select n largest numbers from the set {ai+bj} ( This set isthe sum of two numbers one taken from set A and one taken from set
B.Itis obvious that this set is n^2 in size).Our task is to get n largestnumbers in O(n.log(n)).It can also be solved in O(n).So second step of this problem is todevelop algo in O(n).PLEASE DONT WRITE COMPLETE CODE JUST BRIEFLY EXPLAIN THE
ALGO.Coz it iseasier for everybody to understand.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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: WOW!!! see the real image of muhammad
And to add to Adak's philiosophy - this list is strictly (forgive my impudence) for technical discussion (and in my personal opinion, it is just plain evil to attempt to cause sparks by hurting others' religious sentiments). Please keep such topics for lists that allow religious propaganda.On 3/9/06, adak [EMAIL PROTECTED] wrote: You can't possibly see the real image of Mohammad - or Jesus, or Moses,or Buddha, etc.There simply were no photographs, made, for any of them. No accuratedrawings or paintings either that I have heard of. All of these came about afterward. Usually, a very long time after he and his immediatefollowers, were gone from this world.I think it's very important to separate the image that may be made,from the prophet himself, and from his message to us. No image can begin to describe the importance of their message, to millions ofpeople, for hundreds of years.For the same reason, no image, can diminish these prophets. A meremortal may be seen to look ridiculous in a cartoony drawing, but these men were prophets, consecrated by God. That which God has raised up, nodrawing will diminish.In any case, the cartoons seem a reflection of sociology, not religion.If many members of a group choose to bomb and shoot others, it will --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Return visible lines
Nice. This is called the upper-envelope problem in computational geometry. The solution requires an understanding of what are called duality transforms. What we do is this: - A line like y = ax - b in the normal (primal) circumstances is mapped to a point (a,b) in a dual plane. Symmetrically, a point (f, g) is mapped to a line y = fx - g. The property of this transformation is that if in the primal plane, a point P lies above a line L, then the dual D(P), which is a line, lies below the dual D(L) which is a point. Using this property, you convert all the lines to the respective points. Then you find the convex hull using any of the standard O(nlogn) techniques (Graham's scan, etc.). Now, the lower-chain of the convex hull is the set of edges which represent points in the primal plane which lie above every other line. So you use the lower-chain vertices of the convex hull, and map them back to the primal plane as lines. Take the pair-wise intersection points, in the same order, and then you get your upper envelope. sincerely, mayur On 2/23/06, kool_guy [EMAIL PROTECTED] wrote: You are given n nonvertical lines in the plane, labeled L1, L2, ...,Ln,with the ith line specified by the equation Y = AiX + Bi.We will makethe assumption that no three of the lines all meet at a single point. We say line Li is uppermost at a given x-coordinate Xo if itsy-coordinateat Xo is greater than the y-coordinates of all other lines at Xo:AiXo + Bi AjXo + Bj for all j!=i.We say line Li is visible if there is somex-coordinate at which it is uppermost-intuitively, some portion of itcan be seenif you look down from y = infinity.Give an algorithm that takes n lines as input and in O(n log n) time --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: BEST SORTING TECHNIQUE
Look at introspective sorting - a rather old algorithm. And look at the book Programming Pearls - (J. Bentley). There is a chapter on Data structures programs. And apologies if you already knew about both things (in which case, the above two sentences would sound offensive). sincerely, mayur On 2/13/06, Gene [EMAIL PROTECTED] wrote: I wonder what part of Wikipedia you're talking about.The following isa nice discussionhttp://en.wikipedia.org/wiki/Sort_algorithmIt says that Quicksort requires the smallest number of comparisons for average data (provided you don't make bad pivot choices), but it alsoexplains that this is not always a good definition of best.
[algogeeks] Re: Automaton
How about the language consisting of all the odd numbers. The binary of all odd numbers would be
(0+1)*1, which is regular. I don't think, in base 3, you could
represent it in a regular _expression_. I am not good at proofs - maybe
you can try and get it.
enjoy madi
mayurOn 1/17/06, pramod [EMAIL PROTECTED] wrote:
I have simple problem involving finite automaton.Let 'A' be some (infinite) language which is a subset of naturalnumbers.Let B(A) the the language over the alphabet {0,1} such that B(A)contains all (and only) the members of A in binary form.
Similarly let C(A) contain all (and only) the members of A in base 3.For example, let A = { 3 , 5 } thenB(A) = { 11, 101 } and C(A) = { 10, 12 }. Here I used finite A but A isactually infinite.
Now the problem is to find an A such that B(A) is regular language (anNFA exists for this) but C(A) is not regular.Thanks
[algogeeks] Re: FSM generation
Google for Aho-Corasick string matching.On 1/6/06, rajiv krishnan [EMAIL PROTECTED] wrote: i want an algo for designing a finite automata detecting multiple patterns in an input string
[algogeeks] Re: Hard mathematical function
Gene probably meant a hash function. Encryption functions may not necessarily be completely mathematical - since many of them operate on bits (components of the real information). Saravana - do a Google search on one-way functions. Also, take a look at this link http://www.wisdom.weizmann.ac.il/~oded/frag.html which has fragments from one of the most celebrated cryptography book - there's a chapter on one-way function which is available in postscript. good luck mayur On 12/24/05, Gene [EMAIL PROTECTED] wrote: Any encription algorithm y = E(x) takes a string x to a new string y,which is easy to compute.The inverse function x = E^-1(y) is amathematical function that is extremely hard to compute (if theencription algorithm is any good)but very easy to verify. I.e. ifyou give me x for a given y, I'll just compute E(x) and verify thatit's equal to y.
[algogeeks] Re: towers of hannoi
Hi,
On these same lines there are a lot of variants - could someone show me
how to solve them. (I tried for a short time but lost my patience
soon).
Variant 1. Directional TOH - the discs can be moved in only one
direction - src-aux, aux-dest, dest-sec. How many moves
are required to move N discs from src to dest.
Variant 2. Both the src and dest towers have discs - alternating in
colour. Red-Blue-Red-Blue- .. and the size constraint still exists. How
would you transfer all the Red discs to the src tower and the Blue
discs to the dest tower, without ever placing a larger disc above a
smaller disc.
That's it for now. Thanks for the help.
mayurOn 11/25/05, pramod [EMAIL PROTECTED] wrote:
I heard of this problem before and this is the solution I remember:Suppose there are 'n' disks then we know the number of movementsneeded are f(n) = 2*f(n-1)+1 = 2n – 1.Now let's see the pattern of movements for different 'n'. The
disk that is moved is printed out.n = 1 1n = 2 1 2 1n = 3 1 2 1 3 1 2 1n = 4 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1We note that the n'th disk will be moved only once and that too tothe right. But the (1…n-1) group is moved twice and hence (n-1)th
disk is moved twice, similarly (n-2)th disk is moved 4 times etc.So we have disk 1 moved 2^(n-1) times and disk 2 moved 2^(n-2) times… disk n moved 2^0 times.We also observe that n'th disk is moved only after the (1…n-1)
group is moved and then this group is moved again. So n'th disk willbe in the middle of the all the disks moved. Similarly, (n-1)th diskwill be in the middle of both groups to the left and right of n'thdisk etc. Take the example of n=4, and we have 4, at the middle and 3
at the middle of list to the left of 4 and in the middle of the list tothe right of 4.So nth disk is moved at step 2^(n-1)(n-1)th disk is moved at steps 2^(n-2) and 2^(n-1)+2^(n-2)(n-2)th disk is moved at steps 2^(n-3), 2^(n-2)+2^(n-3),
2^(n-1)+2^(n-3), 2^(n-1)+2^(n-2)+2^(n-3)etcWhich put in another way,nth disk is moved at step 2^(n-1)(n-1)th disk is moved at steps 2^(n-2)*1, 2^(n-2)*3(n-2)th disk is moved at steps 2^(n-3)*1, 2^(n-3)*3, 2^(n-3)*5,
2^(n-3)*7etcAnd hence this:At k'th step disk 'l+1' is moved where 'l' is the largestnumber such that 2^l divides k.Now the question is where the disk is moved. Since there are only three
towers, we can denote the movement to be either to the left or to theright. Also observe that n'th disk which is the largest is moved tothe right if we want final solution to be from A to B, the n'th diskis moved from A to B which is to the right. If we wanted to move the
whole group to the left say from A to C, the n'th disk would havebeen moved to the left. Now in order to solve (1…n) group problemwe'll move n'th disk to right but before that the sub problem ofmoving (1…n-1) from A to C needs to be solved, applying same argument
we move (n-1)th disk left, similarly (n-2)th right etc. Observe thatafter (1…n-1) is solved and n'th disk moved, we need to solve(1…n-1) again but this time from disk C to B which is to the leftagain and hence (n-1)th disk will be moved to the left again. So the
result is that d'th disk is moved right if (n-d) is even and movedleft if (n-d) is odd.The pseudo code looks like this:for (int I = 0; I 2^n-2; ++I ){Find 'k' such that 2^(k-1) divides I.
Direction to be moved : right if (n-k) is even else leftMove disk 'k' to the direction above}To find the greatest m such that 2^(m-1) divides given 'i', note thatmth digit of 'i' is 1 and all the 1 ... (m-1) digits of 'i' are 0.
Hence 2^(m-1) = i (~i + 1).
