Re: [algogeeks] HOW TO CALCULATE THA size of union
I THINK...
D 10
C 10
B 10
A 20
SORRY I AM NOT SURE WITH THIS.
On Fri, Dec 7, 2012 at 4:12 PM, zerobyzero narayan.shiv...@gmail.comwrote:
what will be the size of union A ,B,C and D. also please explain the logic.
* union A{*
* long int y[5];*
* union B{*
*double g;*
*union C{*
* int k;*
* union D{*
*char ch;*
*int x[5];*
* }s;*
*}a;*
* }b;*
*}*p;*
--
--
Re: [algogeeks] BitWise Operations - For finding next multiple
Let me give an example. For 17 next multiple of number 5 is 20. For 20 next multiple of number 5 is 25. And give solution for this proeblem also: For 17 next nearest multiple of number 5 is 20. For 20 next nearest multiple of number 5 is 20. *VIHARRI P L V* On Thu, Sep 13, 2012 at 7:09 PM, bharat b bagana.bharatku...@gmail.comwrote: @vihari: what is n? On Thu, Sep 13, 2012 at 6:32 PM, VIHARRI viharri@gmail.com wrote: hey for finding next multiple of a number x using bitwise : ( n + x -1 ) ~(x-1) but not working for all numbers Could some one please explain me. -- 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/-/7C_Nw4RoxmEJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Some adobe interview questions.
@aditya : I am wondering how many times 7 has occurred. Is it 1? Or is
it 0?
Please take a moment before posting your solution, and think whether
it is write or wrong!
On Jul 6, 12:11 am, aditya kumar aditya.kumar130...@gmail.com wrote:
Q3. ans:7000 i guess this is also a correct answer and no unique soln as
such
On Wed, Jul 6, 2011 at 12:37 AM, aditya kumar
aditya.kumar130...@gmail.comwrote:
boolean palindromeCheck(String string)
{
len=string.length();
if((string.length()1))
{
if((string.charAt(0)==string.charAt(len-1)))
{
str=;
str=str+string.substring(1,(len-1));
palindromeCheck(str);
}
else
{
flag=false;
}
}
return flag;
}
THis also works fine if you dont want to use pointer
On Tue, Jul 5, 2011 at 9:37 PM, Azhar Hussain azhar...@gmail.com wrote:
For Q4: I think this is the optimal code
int recurPalin(char *start, char *end)
{
if (end start)
return true;
if (*start != *end)
return false;
return recurPalin(start+1, end-1);
}
-
Azhar.
On Tue, Jul 5, 2011 at 12:21 PM, vikas mehta...@gmail.com wrote:
My program for Q4.
// recursively find if a given string is palindrome
bool IsPalindrome(string s, int start, int start2, bool flag)
{
bool flag1 = flag;
if (start = 0 start2 (s.Length))
{
char c1 = s[start];
char c2 = s[start2];
if (c1.Equals(c2))
{
if (start == 0 start2 == s.Length - 1) { flag =
true; }
if (IsPalindrome(s, start - 1, start2 + 1, flag))
{
flag1 = true;
}
}
}
return flag1;
}
while calling
if (s.Length % 2 != 0)
{
p.IsPalindrome(s, s.Length / 2 - 1, s.Length / 2 + 1,
false);
}
else
{
p.IsPalindrome(s, s.Length / 2 - 1, s.Length / 2, false);
}
--
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/-/I6SVTB0o-uUJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Sorting Array
There is one way in which we can do O(n). Convert the numbers in base 'n'. [ O(n) ]. Now, there are 2-digit numbers, each digit ranging from 0 to n-1. You can call count-sort 2 times (for each digit), so, complexity is O(n +n) =O(n). On Jun 27, 12:22 am, Dan dant...@aol.com wrote: Your question is good for a classroom style discussion/debate. However, in the real world, there is no simple answer. There are lots of sorting algorithms. Each one has it's pros cons and no single sorting algorithm is best, especially when not much is known about the data to be sorted. In your case about all that we really know is that there are no negative numbers involved. I don't think that helps very much (any?). Then... you need to consider the programming language and computer system used for the implementation. Yes. They do matter. Sometimes, they matter a LOT. Don't assume that an O(x) algorithm is better than an O(y) algorithm just because x is less than y. Dan :-) On Jun 26, 12:14 am, ross jagadish1...@gmail.com wrote: Given a sequence of numbers in the range of 1-N^2, what is the most efficient way to sort the numbers (better than NlgN).. Can counting sort be used here? Is an O(N) solution possible.. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: output plzz
This happens because 'd' is automatically cast into type 'size_t'
which is basically unsigned int type.
So, it compares with TOTAL_ELEMENTS. Explicitly cast it into
int, if you want it to work!
On Jun 25, 3:23 pm, harshit pahuja hpahuja.mn...@gmail.com wrote:
#includestdio.h
#define TOTAL_ELEMENTS (sizeof(array) / sizeof(array[0]))
int array[] = {23,34,12,17,204,99,16};
int main()
{
int d;
for(d=-1;d = (TOTAL_ELEMENTS-2);d++)
printf(%d\n,array[d+1]);
return 0;
}
y der is nothing in the output .
-
Regards -
HARSHIT PAHUJA
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: finding vlaue of nCr
The answer fits in 64 bit range.
The calculations done are of the form D = (A*B) / C. Here {A,B,C,D}
can be represented are 64 bit integers.
But we cannot say that A*B will be a 64 bit integer and will cause
overflows.
To avoid this,
Let's say G=GCD(A,C). Then the above can be written as D = ((A/G) *
B)/ (C/G).
Now, C/G will divide B.
So, our calculation becomes, D= A/G; D= D * (B/(C/G));
You can that maximum value here is from the set {A/G , B/(C/G) , D}.
All of which are 64-bit integers.
C function :
typedef unsigned long long ULL
ULL bin(ULL n,ULL k)
{
if(nk) return 0;
if(kn-k) k=n-k;
ULL ans=1;
for(ULL i=1;i=k;i++)
{
ULL d=gcd(p,i);
ans/=d;
ans*=(n-i+1)/(i/d);
}
return ans;
}
On Jun 21, 10:57 pm, kartik sachan kartik.sac...@gmail.com wrote:
hey anika here n=1 and n=0 so its 1 only
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: DE Shaw Q
The ordering of coins matter for this problem. For ex. 1 2 and 2 1 have different results. So, i don't think that there would be a direct formula for this problem. We will have to traverse all the heaps of coins determining whether the current player is in winning or losing position. On Jun 15, 6:24 pm, sunny agrawal sunny816.i...@gmail.com wrote: @Nitish n=2 heap 1 = 2 heap 2 = 3 Xor = 1 still player one can win :) On Wed, Jun 15, 2011 at 6:49 PM, sunny agrawal sunny816.i...@gmail.comwrote: @immanuel ohh, i read the Question wrong. :( i was thinking player1 is starting from least numbered heap and player 2 from highest no heap On Wed, Jun 15, 2011 at 6:36 PM, immanuel kingston kingston.imman...@gmail.com wrote: Player 1 will take 1 coin from heap 1 Player 2 has to take the other coin from heap1. Player 1 will take both the coins in heap 2. Thanks, Immanuel On Wed, Jun 15, 2011 at 6:33 PM, sunny agrawal sunny816.i...@gmail.comwrote: check out this case n = 2 both heaps having 2 coins player 2 will win i think On Wed, Jun 15, 2011 at 6:26 PM, immanuel kingston kingston.imman...@gmail.com wrote: Yes. I am wrong. As per the example, Player 2 will win if he plays efficiently. Let me put my solution this way, If all the the heaps are of size 1 the Player 1 can win always. Thanks, Immanuel On Wed, Jun 15, 2011 at 5:36 PM, sunny agrawal sunny816.i...@gmail.com wrote: consider the case. n = 2; heap 1 - no of coins 1 heap 2 - no of coins 2 On Wed, Jun 15, 2011 at 5:34 PM, sunny agrawal sunny816.i...@gmail.com wrote: i think u r wrong what if heap size -1 is 0 i think one should pick atleast one coin else game will draw On Wed, Jun 15, 2011 at 5:17 PM, immanuel kingston kingston.imman...@gmail.com wrote: First Player can always win. For each heap Pick heap-size - 1 coins if this is not the n-1th heap Pick all coins from the heap if this the n-1th heap. Please correct me if i am wrong. Thanks, Immanuel On Wed, Jun 15, 2011 at 3:13 PM, Piyush Sinha ecstasy.piy...@gmail.com wrote: *There are n heaps of coin(numbered from 0 to n-1) with atleast 1 coin in each heap. There are 2 players. First player can pick any no. of coins from the least numbered heap, then the second player can pick any no. of coins from the least numbered heap. Unless it is emptied, the player cant move on to the next heap. The player who picks the last coin wins. Design an algorithm for predicting the winner.* -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926* -- 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. -- Sunny Aggrawal B-Tech IV year,CSI Indian Institute Of Technology,Roorkee -- Sunny Aggrawal B-Tech IV year,CSI Indian Institute Of Technology,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. -- Sunny Aggrawal B-Tech IV year,CSI Indian Institute Of Technology,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] Re: Finding shortest path in 4-ary tree
Sorry, i confused val with weight of the edge.
BFS would be a better option.
On Jun 14, 5:31 pm, L prnk.bhatna...@gmail.com wrote:
Any graph algorithm would work.
If val is positive then use Dijkstra's algorithm, otherwise use
Bellman Ford.
On Jun 14, 5:07 pm, Raghavan its...@gmail.com wrote:
Hi,
How to find the shortest path in a 4-ary tree in an optimal way?
Node tree{
Node *left,*right,*top,*bottom;
int val;
};
Let the above given be the tree structure.
--
Thanks and regards,
Raghavan.K.L
http://in.linkedin.com/in/raghavankl
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Finding shortest path in 4-ary tree
Any graph algorithm would work.
If val is positive then use Dijkstra's algorithm, otherwise use
Bellman Ford.
On Jun 14, 5:07 pm, Raghavan its...@gmail.com wrote:
Hi,
How to find the shortest path in a 4-ary tree in an optimal way?
Node tree{
Node *left,*right,*top,*bottom;
int val;
};
Let the above given be the tree structure.
--
Thanks and regards,
Raghavan.K.L
http://in.linkedin.com/in/raghavankl
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: searching a number in circular sorted array
Use ternary search to find the minimum number. (In this case 1) Then you have two sorted arrays, one ascending and one descending. Now, you can apply binary search. First, check the number with the last element and the first element and chose the appropriate array for searching. Time complexity: O(log n) Space complexity: O(1). On Jun 10, 9:06 pm, coder dumca coder.du...@gmail.com wrote: hi frndz given an array which is circularly sorted like 6 ,7 ,8 ,1 ,2 ,3 ,4 ,5 search a given number. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Puzzle
Ah! sorry. This combination is not possible. It will be 10,10,10,10,10,4,2,0. So, the answer is 11. On May 27, 10:10 pm, L prnk.bhatna...@gmail.com wrote: The worst case will occur when 5 teams have the same number of wins. As only 4 can qualify, one team with the same number of points will not be able to qualify. Team. Wins 1. 11 2. 11 3. 11 4. 11 5. 11 6. 1 7. 0 8. 0 In this scenario, a team with 11 points will not be able to qualify. So, to ensure that it is in the finals a team should win 12 matches. On May 27, 6:06 pm, Rishabh Maurya poofiefoo...@gmail.com wrote: suppose bottom 4 teams have won least matches and upper 4 teams have won equal number of matches ... 1 - x 2 - x 3 - x 4 - x 5 - 6 6 - 4 7 - 2 8 - 0 total matches are 56 and let upper four teams have won x matches each so x = (56-(6+4+2+0))/4 x = 11 so in this way to ensure qualification to semi finals team must win 11 matches ... -- 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] Sort the data from a big file.
A merge sort would be helpful i guess... it can also happen in parallel and IIRC databases use them internally. Please correct me if im wrong. Regards, Abhilash On Mon, Dec 21, 2009 at 7:06 PM, dinesh bansal bansal...@gmail.com wrote: On Mon, Dec 21, 2009 at 6:47 PM, Linus Probert linus.prob...@gmail.comwrote: If the numbers are unique you could use a bitmap-sort this way you could easily read just parts of the file at a time. If they aren't unique it gets a bit trickier. /L dinesh bansal wrote: Hi All, Suppose I have a big file (~100M) containing integer data. I want to sort this file. The problem is I don't want to load the complete file data into main memory in one shot. I mean I can read the file in batches and sort the batch and save it in another file but cannot store the entire file contents in main memory. Can somebody help me with algorithm or pseudo code? Thanks in advance. -- 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. Hi Linus, Thanks for the reply. But yes we cannot guarantee that data value are unique. -- Dinesh Bansal 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 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: what is total number of permutation
Hi,
Although, I cannot give you a complete solution right now..I will give you
the following relations (I am not sure If they are correct.discussions
welcome)
T(0, x) = 1
T(x, 0) = 1
T(1, x) = (x+1)
T(x, 1) = (x+1)
T(n, m) = Sum[i=0..n] { T(n-i, m-2) * (i+1) }
If you are looking for a program, then you can code this up...If you are
looking for a closed form solution, this needs to be tidied up.
--~--~-~--~~~---~--~~
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: need help for graph problem ...
Hi,
I guess he is going by the assumption that the queries will be large
enough that precomputing the all-pairs shortest paths is better.
Anyways..mukesh..this is what you need..
In the place of your output
while(cin.get(c) c!='\n')
{
cin.unget();
cint1t2;
printf(From %d to %d :\n,t1,t2);
printf(\n);
printf(Total cost : %d\n,pathcost[t1-1][t2-1]);
printf(Path :);
i=0;
j=t1-1;
k=t2-1;
t=t2-1;
printf(%d,(j+1));
while(j!=k i3)
{
while(j!=pre[j][t])
{
t=pre[j][t];
}
printf(--%d,(t+1));
j = t;
t = k;
i++;
}
printf(\n);
getchar();
}
printf(\n);
All the best [:)]
--~--~-~--~~~---~--~~
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: height of ternary tree
I guess it was a slight difference in terminology...you must have then phrased the question as almost complete rather than a complete tree since you are allowing the last level to be incomplete. Anyways, If the last level is going to be incomplete, then the observe this.. sum of the nodes is 1+3+3^2+3^3+...+3^(h-1)+x with x=3^h This series upon summation gives The usual stuff... 3^(h-1)(1+1/3+(1/3)^2+...+(1/3)^(h-1)) = 3^(h-1)*(1-(1/3)^h)/(1-(1/3))=(3^(h)-1)/2 (3^(h)-1)/2+x = N Now given N we need h so (3^(h)-1)+2x = 2N Now we substitute that 1=x=3^(h) this gives (3^(h)+1)=2N=(3^(h+1)-1) So the answer that we are looking for is ceil(Log_base_3(2N)) In case you are not satisfied with the proof..check out ceils of Log_base_3(1(2))=1 Log_base_3(2(2))=2 Log_base_3(3(2))=2 Log_base_3(4(2))=2 Log_base_3(5(2))=3 Log_base_3(6(2))=3 Log_base_3(7(2))=3 Log_base_3(8(2))=3 Log_base_3(9(2))=3 Log_base_3(12(2))=3 Log_base_3(13(2))=3 Log_base_4(14(2))=4 --~--~-~--~~~---~--~~ 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: Pumping lemma. Where I go wrong?
Read the post again... The adversary then chooses the split up, that is, the part of the string you've given him that loop you can only choose the string 'w' (=n), the adversary can only _CHOOSE X, Y and Z_ but ofcourse the adversary is restricted by the fact that he had chosen a 'n' earlier and therefore would have to split the string into x, y and z such that |xy|=n and |y|0 Once he gives you the split up, you can pump y as many times as you want and the string has to be in the given language. --~--~-~--~~~---~--~~ 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 graph problem
DFS --~--~-~--~~~---~--~~ 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: prime or not
well...its simple as given in the article.. note that the numbers are all decimal numbers (not binary..in case misled by just 0 and 1 in the number) therefore if you have have k copies of 001 and k%3 == 0, then the sum of the digits is divisible by 3 hence the number is divisible by 3 - The Standard Test(The only digit is 1 and it occurs k times). For the numbers such that k%3 0, observe that the number mod k 9s has the value of k1s. Since k9s is also divisible by k1s the original number k*001* should also be divisible by k1s. This property holds good for all k%30. --~--~-~--~~~---~--~~ 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: prime or not
In case you are wondering about the part of the proof for k%30, it goes like this, the given number can be written as 1 + 1000 + 100 + 10 +..and so on now if for a given k, if we choose the string of k 1s and try to find the modulus with each of the terms in the above expression, for all the terms less that ...1 (k times) will be the numbers themselves, for the rest of the terms, this will give 1(000)*00 and 1(000)*0 as the remainders. Consider any number as 1 followed by m zeros, the remainder when divided by k1s would be 1 followed by (m%k) zeroes. Now, there is a beautiful property, consider the sequence 0,3,6,9,12,15,18 (all the multiples of 3) and try to take mod k (assuming k%3 0 and therefore k is only going to intersect at the point 3k). The series is 0,3,6...k-(k%3), k+(k%3), , 2k-(2k%3), 2k+(2k%3)...3k This is valid since k%3 and 2k%3 are going to be non zero since k % 30. Now note that when taking mod k, the sequence of remainders after k - (k%3) will be offset by either 1 or 2 . If it is offset by 1 then after 2k%3 it will be offset by 2, If by 2 after k-(k%3) then by 1 after 2k%3. Therefore the sequence 0,3,6,9...2k under modulus k (k%30) produces all the numbers from 0..k-1. This completes the proof, since the set of numbers with 1 followed by 0 to k-1 zeroes when added will give 111..1 k times. Therefore the number 1 + 1000 + 100 + 10 +.. (till 1 (3k)* ) will be divisible by 111..1 ( k times). --~--~-~--~~~---~--~~ 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] Fwd: [algogeeks] prime or not
Oooh...I almost forgot to add this.. notice the relation between the proof for part (ii) and the discrete logarithm problem. The proof is no mere coincidence. This is the reason behind using primes in encryption schemes that rely on the hardness of the discrete logarithm problem. This will ensure that given b^k mod p (since p is prime , p%b is definitely not zero) k has uniform probability because if p were not prime we would not be getting the remainders the equal number of times and hence the probability would be biased making it easier to crack. --~--~-~--~~~---~--~~ 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: BST represented in array
Now in the case of non complete BSTs it may run into trouble...I never handled them. It will work for complete BSTs though as it is. Refer to a previous thread in algogeeks where i had posted the thread inplace sorting and look at the solution by atamurad for the explanation. --~--~-~--~~~---~--~~ 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: universal hashing question
Well... I think a hash function is chosen only once for each run of the program and not for each time a value is hashed. Thereby you dont have such issues at all. --~--~-~--~~~---~--~~ 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: RR*=R* ?
sorry RR* = R+ is the valid assumption --~--~-~--~~~---~--~~ 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: Pigeon Hole Principle
Yes...the proof is correct and this is what stone had suggested in his earlier post. Consider one red sector in the inner disk in each of the 200 different positions, it will match against exactly 100 sectors in the outer disk since there are 100 of the red sectors in the outer disk. Similarly for a white disk also, therefore there are a total of 200*100matching events and hence by PHP it is true that atleast one rotation must have 100 events. --~--~-~--~~~---~--~~ 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: BST represented in array
An unique BST does exist for such an array if you assume the root to be 1, then automatically you will be able to fix the left and right children of the root and so 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Pigeon Hole Principle
@alfredo: I dint get this part: 1) Lets say that we have the outer circle painted in the following manner: 1 red(C1), 1 white(C2), 1 red(C3), etc. We call this sections (RWR) 2) Then if we have that the inner circle is painted in the same way we finish. 3) if not then lets say that we have a least one section in the inner circle that is painted 1 white(c1) 1 red(c2) 1 white(c3) or 1 red, 1 white, 1 red. We call this sections (wrw or rwr) 4) we rotate the inner circle so C1 = c1 Say we have RRRR in the outer circle If the inner circle is WRRRW (we have two matches here) The solution would be RRWWR (with 6=4 matches) Plz clarify if i am misinterpreting your 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: BST represented in array
#includestdio.h
#includestdlib.h
#includemath.h
#includestring.h
#define MAXN 2000
int a[MAXN];
int cnt = 0;
int log2n;
int n;
void populatetestcase(int i)
{
if(i*2=n) populatetestcase(i*2);
a=++cnt;
if(i*2+1=n) populatetestcase(i*2+1);
}
int calc_x(int i)
{
return (int)log2l((double)i);
}
int calc_m1(int i)
{
return 1 (log2n-calc_x(i)+1);
}
int calc_m2(int i)
{
return i - (1calc_x(i));
}
int main()
{
int i,j,temp,p;
n=(17)-1;
log2n = calc_x(n);
populatetestcase(1);
for(i=1; i=n; i++) {
p= calc_m1(i)*calc_m2(i) + calc_m1(i)/2;
if((pi a[p]a)|| (pi a[p]a))
continue;
j=i;
while(p!=i)
{
temp = a[j];
a[j] = a[p];
a[p] = temp;
p = calc_m1(p)*calc_m2(p) + calc_m1(p)/2;
}
}
for(i=1; i=n; i++)
{
printf(%d ,a);
}
system(PAUSE);
return 0;
}
--~--~-~--~~~---~--~~
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: BST represented in array
yes...but you can sort without constant space using the posted algorithm --~--~-~--~~~---~--~~ 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: Pigeon Hole Principle
yes...but that does not mean that you can assume that the 100 reds and 100 whites are contiguous blocks.It just says that the outer disk has a sum of the 100 reds and 100 whites and does not say that they are contiguous. --~--~-~--~~~---~--~~ 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: BST represented in array
for(i=1; i=n; i++) {
p= calc_m1(i)*calc_m2(i) + calc_m1(i)/2;
if((pi a[p]a)|| (pi a[p]a))
continue;
j=i;
while(p!=i)
{
temp = a[j];
a[j] = a[p];
a[p] = temp;
p = calc_m1(p)*calc_m2(p) + calc_m1(p)/2;
}
}
Isnt this constant space (assuming that the array a is given already).
Since calc_m1 and calc_m2 are non recursive?
--~--~-~--~~~---~--~~
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: BST represented in array
i am sorry that is a[i] = ++cnt I made a mistake when pasting the code... --~--~-~--~~~---~--~~ 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: count the 1 bits in integer
The standard link http://graphics.stanford.edu/~seander/bithacks.html --~--~-~--~~~---~--~~ 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: find the closest common ancestor of node u and v?
Find the longest common prefix in the path from the root to nodes u and v --~--~-~--~~~---~--~~ 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: help making regular expression
A DFA is possible I guess which is interesting, see if the following DFA works, since the existence of the DFA relates to the existence of a Regular Expression Describing the language State/Input 01 q00 q10 q01 q10 q20 q11 q20 q30 q21 q30 q40 q31 q40 q00 q41 q01 q11 q00 q11 q21 q10 q21 q31 q20 q31 q41 q30 q41 q01 q40 The final state is q00. In this DFA the first subscript denotes the number of zeros % 5 and the second describes the number of ones % 2 --~--~-~--~~~---~--~~ 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: help making regular expression
If the DFA works then it can be converted to a regular expression using standard techniques like the one described in http://www.cs.colostate.edu/~whitley/CS301/L3.pdf --~--~-~--~~~---~--~~ 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: Inplace sorting
To make things more easier just assume a complete binary search tree --~--~-~--~~~---~--~~ 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: linear programming
the LP: v1 = 40 v2 = 30 v3 = 20 v1 + v2 + v3 = 60 v1*2 + v2*1 + v3*3 = 100 Maximize: v1*1000 + v2*1200 + v3*12000 Here v1, v2 and v3 are the volumes of the materials 1, 2 and 3 to be taken. --~--~-~--~~~---~--~~ 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: Inplace sorting
The question is not to print out a sorted array which we can easily do by inorder traversal. The question is to store the sorted array in the same array with constant extra space. --~--~-~--~~~---~--~~ 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: Inplace sorting
I agree with you completely but for the problem that I posted it is enough that we have O(n) in accessing the elements in order. Your solution does better by calculating every element in O(1) time. The key now is to do the actual sorting with this method --~--~-~--~~~---~--~~ 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: To find a rectangle of max sum
Another variant...(or rather wanted to say in my previous post) How do you find a maximum square of all ones in a binary matrix of 0s and 1s? --~--~-~--~~~---~--~~ 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: Largest Bound rectangle in a bar graph
I give a try to start at an O(mn) algorithm (where m is the size of the longest bar) Maxrect[height][width] = --~--~-~--~~~---~--~~ 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: Largest Bound rectangle in a bar graph
A shot at an O(nlgn) algorithm. Do a sweep line from top to bottom. Only look at the events when a new bar is introduced (this is accomplished by sorting the bars based on height). When a new bar arises, if there exist values immediately to the left and right of the bar just merge them into a new sum. This algorithm takes O(nlgn) --~--~-~--~~~---~--~~ 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: how to tell honest people
yes..thats the reasoning that i had too but let us see if anyone else sees some thing fishy in our reasoning --~--~-~--~~~---~--~~ 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: Interesting Probability Question
why is it 1 - (area of triangle)/(area of Sq.)? why do we need a square since what would happen is that the 4th point can be anywhere in the space but the area of the triangle is bounded. The probability of choosing a point outside the triangle would be 1 (bound - not exact by reasoning as in (3)) and that would lead to a probability of 1. If the bound reasoning is correct then we would have a probability of 1 to get a quadrialetral when choosing random points in a plane. --~--~-~--~~~---~--~~ 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: integers n1,n2 such that n1+n2 = x
On 2/14/07, [EMAIL PROTECTED] [EMAIL PROTECTED] wrote:
Hello,
There is a problem in the algorithm book I'm trying to digest, that
I'd like to discuss a bit. So, first thing first, let me state the
problem :
find(A, x)
sort(A)
i = 1
j = n
while (A[i]+A[j] != x)
{
if(A[i]+A[j]x)
j--;
else
i++
}
if (A[i]+A[j]==x)
return EXISTS
else
return NOT EXISTS
--~--~-~--~~~---~--~~
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
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: Permutation with a twist ??
permutation (List resultSoFar, List remainingElements)
{
if(length(remainingElements)=0)
return;
for i = 1 to length(remainingElements)
{
print resultSoFar+remainingElements[i];
permutation (resultSoFar+remainingElements[i],
remainingElements-remainingElements[i]);
}
}
--~--~-~--~~~---~--~~
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: Permutation with a twist ??
yes..i agree with rajiv..you seem to be generating combinations rather than permutations..the algo that i have given generates permutations --~--~-~--~~~---~--~~ 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: puzzle - Weighing marbles
Split the marbles into sets of 4 each
Compare the first and second sets
If both the sets are equal (the problem is in third set)
{
choose 2 of the marbles in the third set
compare with 2 marbles from the first set(which we know are good)
if comparision is equal
{
compare one of the remaining 2 marbles in the third set with a good marble
if comparison is equal
culprit is the uncompared marble in the third set
else
culprit is the last chosen marble in the third set
}
else
{
compare one of the chosen 2 marbles in the third set with a good marble
if comparison is equal
culprit is the uncompared marble in the chosen 2 of the third set
else
culprit is the last chosen marble in the third set
}
}
else
{
choose one of the marbles from the first pan and shift to second pan
remove the other 3 marbles from the second pan and put 3 from the third pan
If the comparison value changes (now , previous or vice versa)
{
one of the transferred 2 marbles is the culprit
found by comparing one of the marble with a standard one (from third set)
}
else
{
If comparison value is equal
{
one of the three marbles from second pan was the culprit (we
know heavier or lighter now ...from the first comparison)
can be determined by comparing two of the marbles
if equal
third guy is the culprit
else
the (heavier or ligher guy) as determined by the first comparison
}
else (comparison values are same)
{
one of the three unshifted marbles from the first pan is the culprit
can be found in a strategy similar to the previous cases
}
}
--~--~-~--~~~---~--~~
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: please help me solve the exercise 14.1-8 of introduction to algorithm
Hi,
You can try a similar technique...
Start at an arbitrary endpoint,
Set the number of open chords to zero,
Set the number of intersections to zero
Traverse the endpoints along the circle in one direction (made
possible by sorting radially)
{
If the endpoint is one that closes an already open chord then (have a flag)
number of intersections += number of open chords
number of open chords -= 1
else
number of open chords += 1
}
Hope this helps...
-karthik
--~--~-~--~~~---~--~~
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: Array moving left
You could use a B-Tree or even a simple binary tree to index into the array, but the space will be doubled (it is justified if you store some other object in the array other than integers). On 11/17/06, Nik [EMAIL PROTECTED] wrote: Hi, I have an array in which elements are present . The number of elements n = 10^6 . Now if i delete an element in the array, i want to update the array by moving all the elements to the left. It is very slow considering the size of element and i want to access the array with new updated indexes (it needn't be o(1) it can be atmost O(logn)) ex: 4 3 2 100 arr[2]=2; once i access the index i delete the element, So the new array should be 4 3 100, arr[2] should be now 100 etc. Can someone suggest me a good way to solve this problem Reg Nik --~--~-~--~~~---~--~~ 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] Fwd: Graph Partitioning
-- Forwarded message --
From: Karthik Singaram L [EMAIL PROTECTED]
Date: Nov 12, 2006 4:58 PM
Subject: Graph Partitioning
To: algogeeks@googlegroups.com
Hi,
I have been faced with this problem for weeks and could not find a
good solution. can someone help?
Given a graph whose nodes are bit vectors of length n (the graph
contains all 2^n nodes), the edges are defined to be connecting all
the pairs of nodes which differ only at one bit position (Hamming
distance = 1 between n1 and n2 means n1n2 is an edge).
The problem is to produce a partition k (say a power of 2), such
that total the number of outgoing edges from the partition are
minimized and the partitioning is load balanced (each partition has
roughly the same number of nodes)
The approaches that I have tried:
(i) A naive partitioning by simply masking of the last lg(k) bits
and assigning to one partition
Load balanced but many outgoing links from each partition
(ii) Assuming that I find seed nodes and grow from them by adding
the nodes in the increasing order of hamming distance I can reduce the
outgoing edges but I am not able to find correct seed nodes.
Assume that n is very large and the way the input output is going
to be tested is through a query interface that asks the placement of
node x and the output is the partition number.
An approximate algorithm would be really helpful
Ex: for n=4 and k=2
{,0001,0010, 0100, 1000, 0011, 0101}
{, 1110, 1101, 1011, 0111, 1100, 1010}
--~--~-~--~~~---~--~~
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: NP complete Partition problem.
I am not sure but an arbit way to do this would be to find
(totalsum/k) and do a bin packing for each of these , of course we
would be left with a few elements, we can put them in the bins with
max.slack space...It would be approximately correct I guess though not
sure.
Hope it helps
karthik
On 11/12/06, [EMAIL PROTECTED] [EMAIL PROTECTED] wrote:
Can someone please give me a algorithm/pseudo code for the following
problem?
Given an arrangement S of non-negative numbers {s1,s2,s3sn} and an
integer k.
Partition S into k ranges, so as to minimize the maximum sum over all
the ranges.
e.g Optimally S={1,2,3,4,5,6,7,8,9} partitioned into k=3 ranges will be
{1,2,3,4,5}, {6,7}, {8,9}
--~--~-~--~~~---~--~~
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] Graph Partitioning
Hi,
I have been faced with this problem for weeks and could not find a
good solution. can someone help?
Given a graph whose nodes are bit vectors of length n (the graph
contains all 2^n nodes), the edges are defined to be connecting all
the pairs of nodes which differ only at one bit position (Hamming
distance = 1 between n1 and n2 means n1n2 is an edge).
The problem is to produce a partition k (say a power of 2), such
that total the number of outgoing edges from the partition are
minimized and the partitioning is load balanced (each partition has
roughly the same number of nodes)
The approaches that I have tried:
(i) A naive partitioning by simply masking of the last lg(k) bits
and assigning to one partition
Load balanced but many outgoing links from each partition
(ii) Assuming that I find seed nodes and grow from them by adding
the nodes in the increasing order of hamming distance I can reduce the
outgoing edges but I am not able to find correct seed nodes.
Assume that n is very large and the way the input output is going
to be tested is through a query interface that asks the placement of
node x and the output is the partition number.
An approximate algorithm would be really helpful
Ex: for n=4 and k=2
{,0001,0010, 0100, 1000, 0011, 0101}
{, 1110, 1101, 1011, 0111, 1100, 1010}
--~--~-~--~~~---~--~~
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: PAIR of shortest paths...
I am not sure If I got the question right 1 4 0 3 1 2 3 1 1 0 2 2 0 3 3 2 0 2 1 2 Isn't the answer that camarade 1 talks to camarade 0 who inturn talks to 2. Isnt this shortest path algorithm? isnt Djikstra O(VlogV) which seems feasible for the problem rite? On 10/30/06, Pradeep Muthukrishnan [EMAIL PROTECTED] wrote: I dont see how Djikstra can be used here? On 10/30/06, Dhyanesh (ધયાનેશ) [EMAIL PROTECTED] wrote: Djikstra's or any other single-source shortest path algorithm should be good enough I guess. -Dhyanesh On 10/30/06, vijay [EMAIL PROTECTED] wrote: Anyone know how to solve this problem... http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=3502 ... I thk its a toughie... --~--~-~--~~~---~--~~ 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: Permuatation containing given element
/* Assume inp is the given array*/static int bitmap[N][N];int lengths[N];int currentBitmap = -1;int active = 1;int lastPos;for(i=0;iN;i++){ if(inp[i]==1) { currentBitmap++;
active=1; lastPos=i; } if(active==1) { if(bitmap[currentBitmap][inp[i]]==1) { active=0; lengths[currentBitmap]=(i-pos); } else bitmap[currentBitmap][inp[i]]=1;
}}pos = findMax(lengths);print(lengths[pos]);
--~--~-~--~~~---~--~~
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: isomorphism
Let us say we call the following with the roots of both the treesalgo: checkIsomorphism (node1, node2){ if(node1==NULL node2==NULL) return 1; if(node1==NULL) return 0; if(node2==NULL) return 0;
child11=node1-left; child12=node1-right; child21=node2-left; child22=node2-right; if((child11==NULL child21==NULL) || (child11-value==child21-value))
{ if((child12==NULL child 22==NULL) || (child12-value==child22-value) { if((child11==NULL child12==NULL) || (child11-value==child12-value)) {
if((checkIsomorphism(child11, child21) checkIsomorphism(child12, child22)) || (checkIsomorphism(child11, child22) checkIsomorphism(child12, child21)) return 1;
else return 0; } else { if(checkIsomorphism (child11, child21) checkIsomorphism(child12, child22)) return 1;
else return 0; } } else { return 0; } } else { if((child11==NULL child22==NULL) || (child11-value == child22-value))
{ if(checkIsomorphism(child11, child22) checkIsomorphism(child12, child21)) return 1; } else return 0; }}
On 10/25/06, None [EMAIL PROTECTED] wrote:
Hello, how can I compare two trees that only have ints forisomorphism...can someone show me a simple algorithm to do 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 [EMAIL PROTECTED] For more options, visit this group at http://groups-beta.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: k connectivity
Hmmm.. Interesting Just in case someone does want to use BFS and does not really care about the time complexity, then you could do BFS to get all the Paths ( do not remove them as soon as you get them ) For example in the graph in the previous discussion, BFS would give S37F, S345F and S267F now we would have to find out the cardinality of the maximum maximal set of disjoint paths from the set obtained. In this case this would be 2 for the set S345F and S267F so we would get the result. The complexity would now be O(k(n^3+mn^2)(n+m)^2) On 4/25/06, forest [EMAIL PROTECTED] wrote: there is an example of BFS fail: - - - 2 6 - - - -- 7- - - - - S / -- - - - - - /F - - - 3- - - - 4 - -- - - 5 - -- - - - going form S to F. k = 2. BFS finds path S37F, as it is shortest. After removing this path there is no other path from S to F. But choosing paths another way you could get 2. About restrictions on vertexes - it is rather well known trick. You double each vertex and get 2 vertexes V' and V''. Make all the graph directed. There is an edge from V' to V'' with capacity equal to vertex initial capacity. All in-edges come to V' all out-edges go from V''. --~--~-~--~~~---~--~~ 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: k connectivity
of course the time complexity could be substantially reduced using the flow model of the problem.l\ On 4/26/06, Karthik Singaram L [EMAIL PROTECTED] wrote: Hmmm.. Interesting Just in case someone does want to use BFS and does not really care about the time complexity, then you could do BFS to get all the Paths ( do not remove them as soon as you get them ) For example in the graph in the previous discussion, BFS would give S37F, S345F and S267F now we would have to find out the cardinality of the maximum maximal set of disjoint paths from the set obtained. In this case this would be 2 for the set S345F and S267F so we would get the result. The complexity would now be O(k(n^3+mn^2)(n+m)^2) On 4/25/06, forest [EMAIL PROTECTED] wrote: there is an example of BFS fail: - - - 2 6 - - - -- 7- - - - - S / -- - - - - - /F - - - 3- - - - 4 - -- - - 5 - -- - - - going form S to F. k = 2. BFS finds path S37F, as it is shortest. After removing this path there is no other path from S to F. But choosing paths another way you could get 2. About restrictions on vertexes - it is rather well known trick. You double each vertex and get 2 vertexes V' and V''. Make all the graph directed. There is an edge from V' to V'' with capacity equal to vertex initial capacity. All in-edges come to V' all out-edges go from V''. --~--~-~--~~~---~--~~ 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: Chord Intersection
Try this variation In the previous algorithm if i am correct the complexity is O(n), that itself shows that an important step is missing somewhere. well this is my guess about the algorithm. check if it works. I do not think this is exactly the standard Bentley-Ottmann Algorithm The precondition would be in going from a point in the circle in a clockwise direction, we must get the start point of a chird first and then only get the corresponding end point. This can be done by swapping the start and enp points appropriately in O(n) 1 ) Radially sort the all the points of each chord (start and end both ). 2 ) Start with the first start point. Insert start point into a Sorted List SL1 Insert corresponding end point into a Sorted List SL2 Have tot=0, done[1..n]=0 3 ) Till all points are done: a ) If its a start point then Insert start point into a Sorted List SL1 Insert corresponding end point into a Sorted List SL2 Find the position of corresponding end point in SL2 say pos tot = tot + pos set done for this point 1 else if it is an end point of a start point processed then Remove the start point from SL1 and end point from SL2 set done for this point 1 4 ) Answer is tot The searching in the sorted list can be done using binary search and therefore the resulting complexity would be O(nlogn) On 4/26/06, pramod [EMAIL PROTECTED] wrote: I don't think this will work. Suppose we have two chords which are parallel and both on the one side of the circle. i.e., say draw a diameter parallel to X and say the chords are above this parallel to each other. In that case, your answer will be 1 but they are not intersecting at all. I think your statement if you get another start point it means there is an intersection is not correct. --~--~-~--~~~---~--~~ 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: optimal assignnment of program to tapes.
This is the problem of dividing a set into two such that the sum of their differences is minimum.This can be solved using dynamic programming as follows: algo: 1. Create an array of size L say Arr[L] and initialize to zeroes 2. Put Arr[0]=1 3. For each program Pi Scan the array Arr from the right and if Arr[j]=1 then set Arr[j+Li]=1 4. From the right choose the first j such that Arr[j]=1 that will be the Length in S1 and the remaining will be Length in S2 --~--~-~--~~~---~--~~ 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: An interesting problem from Code4bill second round
Exactly correct!!! But for the proof and solution to be complete, we need to analyze this for 7 the answer you have is dp[3]=3*dp[2]+1=3*[4]+1 Now can you see that for dp[2], the number of steps would be 000 010 011 That would be only 3 steps so dp[2] is only 3 . Am i correct? Regards karthik
[algogeeks] Re: An interesting problem from Code4bill second round
I solved this problem ( A very very interesting DP solution I guess )The key to the solution is First try to Prove that the last bit can be set using only 15 onesand you will get the solution.Keep thinking!!! ( A clue :- use Mathematical Induction for the Proof and the DP follows)-karthik
