[algogeeks] Re: question at K10
void change()
{
printf(10); while(1) {}
}
On Feb 15, 10:17 am, Balaji S balaji.ceg...@gmail.com wrote:
Insert only one line in the function change() so that the output of the
program is 10.
You are not allowed to use exit(). You are not allowed to edit the function
main() or to
pass the parameter to change()
void change()
{
// Code here}
int main()
{
int i=5;
change();
printf(“%d” ,i);
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
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: question at K10
A semicolon is valid in the middle of a line in C or C++.
For instance, no one says that
for(i = 0; i 10; ++i)
is three lines of code.
Don
On Feb 15, 11:31 am, jalaj jaiswal jalaj.jaiswa...@gmail.com wrote:
after termination of semicolon , that will be considered a separate line i
guess
On Tue, Feb 15, 2011 at 10:59 PM, Don dondod...@gmail.com wrote:
void change()
{
printf(10); while(1) {}
}
On Feb 15, 10:17 am, Balaji S balaji.ceg...@gmail.com wrote:
Insert only one line in the function change() so that the output of the
program is 10.
You are not allowed to use exit(). You are not allowed to edit the
function
main() or to
pass the parameter to change()
void change()
{
// Code here}
int main()
{
int i=5;
change();
printf(“%d” ,i);
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
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
With Regards,
*Jalaj Jaiswal* (+919019947895)
Software developer, Cisco Systems
B.Tech IIIT ALLAHABAD
--
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: Help
Mike Johnson wrote:
Plesae rite a program for me to find prime nummers. It should be recursive
prorgram. What duz that mean?
If u type a nummer like 10 it should say 1 is prime, 2 is prime, 3 is prime,
4 is not prime up to 10.
This iz not homewurk I just thout of it myself. Lol.
/* Sure Mike, Happy to help!
This program implements a blindingly fast O(n^n) algorithm
to find prime numbers, using an elegant recursive method. */
int _(int n, int m, int d, int t)
{
int r;
if (t) return d?1+_(n,m,d-1,d):n?_(n-1,m,m,n):0;
for(r=m!=n; d*(tn); ++t)
r = _(n,_(t,m,0,1),d-1,0)|!_(t,1,t,0);
return r*n;
}
/*--
Print primes up to the requested value
*/
int main(int argc, char* argv[])
{
int max;
scanf(%d, max);
for(int n = 2; n = max; n++)
printf(%d is%s prime\n,n, _(n,1,n,0)?: not);
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
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: General Sorting Header File Adobe
templateclass Iterator, class Compare void sort(Iterator first, Iterator last, Compare cmp); On Feb 16, 5:57 am, bittu shashank7andr...@gmail.com wrote: write header file for sorting general element. it can sort any type of object(int,float,complex number, objects) Thanks Shashank -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Puzzle For Puzzled Minds - Robots
On Feb 16, 12:53 pm, bittu shashank7andr...@gmail.com wrote: Two robots are placed at different points on a straight line of infinite length. When they are first placed down, they each spray out some oil to mark their starting points. You must program each robot to ensure that the robots will eventually crash into each other. A program can consist of the following four instructions: * Go left one space * Go right one space * Skip the next instruction if there is oil in my current spot * Go to a label [Note that a label is a name that refers to a line of your code. For example, you could label the third line of your program surveying. Then, the instruction goto surveying would jump to line 3 and start executing from there on the next cycle.] A robot will carry out one instruction per second. Both robots need not have the same program. Note that you won't know ahead of time which robot is on the left and which is on the right. Thanks Regards Shashank Mani RIGHT // Move off the starting spot Search: RIGHT // Move at speed of 1 space every third turn until you find the other robot's starting spot SKIP NEXT INSTRUCTION IF OIL GOTO Search Fast: RIGHT // Move at speed of 1 space every other turn GOTO Fast Both robots will move to the right, but the one on the left will eventually find the oil left by the other robot and begin moving faster, eventually catching up with the other robot. Don -- 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: Maze labyrinth Solve Puzzle WAP Efficiently
class coord
{
public:
int x;
int y;
};
class SolveMaze
{
public:
SolveMaze() { location.x = location.y = 0; }
bool Explore();
private:
listcoord visited;
coord location;
};
bool Explore()
{
// Determine if we've already been here
if (visited.found(location))
return false;
// Base case, we are at an exit
if (HasLadder()) return true;
// Remember that we have been here
visited.push(location);
// Try all four directions
for(direction = 0; direction 4; ++direction)
{
if (TryMove(direction))
{
coord prev(location); // Copy current location
// Track our current location
switch(direction)
{
case 0: --location.y; break;
case 1: ++location.x; break;
case 2: --location.x; break;
case 3: ++location.y; break;
}
// Explore from new location
if (this-Explore()) return true;
TryMove(3-direction); // Assume 3-direction is opposite move of
direction
// Back out location
location = prev;
}
}
// Remove current location from list
visited.pop();
// No exit found
return false;
}
On Mar 2, 9:05 am, bittu shashank7andr...@gmail.com wrote:
You are in a maze(like a labyrinth), and you open your eyes so you
don't know your position. The maze has walls and you can move only in
up, right, left and down directions. You can escape the maze when you
find a ladder.
The following API is given:
bool TryMove(direction) - returns true when you don't hit a wall;
bool HasLadder() - return true if you found the ladder.
Write a method bool Explore() that returns true if you can escape the
maze, false otherwise. Also, provide test cases.
A Good Explanation Pseudo-code, Algorithmic discussion
needed..Object Oriented is Also Welcome
Thanks Regards
Shahsank
--
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: Tough Problem of Probability ..Surely Will Stuck ..So Think More More
Game 2 is better if p 0.5. P(win game 1) = p P(win game 2) = p^3 + 3(p^2 * (1-p)) To find the solution, solve for p when p^3 + 3(p^2 * (1-p)) p Which simplifies to 3p - 2p^2 1 Which is true when p 0.5 On Mar 1, 5:15 pm, bittu shashank7andr...@gmail.com wrote: You have a basketball hoop and someone says that you can play 1 of 2 games. Game #1: You get one shot to make the hoop. Game #2: You get three shots and you have to make 2 of 3 shots. If p is the probability of making a particular shot, for which values of p should you pick one game or the other? Thanks Regards Shashank -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: brain teaser
They agree on the following plan: The prisoner at the back of the line counts up the number of red hats he sees. If the number is odd, he says Red. If it is even, he says Black. Now the 19th prisoner can count the red hats he sees. He can deduce what color his hat must be to make the total odd or even, as indicated by the previous prisoner. Each prisoner in line must keep track of the current state, odd or even, which changes each time someone behind him indicates having a red hat. Don On Mar 3, 2:18 am, freecoder rajuljain...@gmail.com wrote: You are one of 20 prisoners on death row with the execution date set for tomorrow. Your king is a ruthless man who likes to toy with his people's miseries. He comes to your cell today and tells you: “I’m gonna give you prisoners a chance to go free tomorrow. You will all stand in a row (queue) before the executioner and we will put a hat on your head, either a red or a black one. Of course you will not be able to see the color of your own hat; you will only be able to see the prisoners in front of you with their hats on; you will not be allowed to look back or communicate together in any way (talking, touching.) (The prisoner in the back will be able to see the 19 prisoners in front of him The one in front of him will be able to see 18…) Starting with the last person in the row, the one who can see everybody in front of him, he will be asked a simple question: WHAT IS THE COLOR OF YOUR HAT? He will be only allowed to answer “BLACK” or “RED”. If he says anything else you will ALL be executed immediately. If he guesses the right color of the hat on his head he is set free, otherwise he is put to death. And we move on to the one in front of him and ask him the same question and so on… Well, good luck tomorrow, HA HA HA HA HA HA!” Now since you all can communicate freely during the night, can you find a way to guarantee the freedom of some prisoners tomorrow? How many? -- 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: Maze labyrinth Solve Puzzle WAP Efficiently
The problem with BFS is that you have to remember how to get from
where you are to every other point you have explored.
Of course, the problem with a depth-first search is that in an
unbounded maze, you may never reach a point even if it is very close
to your starting point.
Don
On Mar 3, 1:31 pm, Jammy xujiayiy...@gmail.com wrote:
BFS search the maze
On Mar 2, 11:26 am, Don dondod...@gmail.com wrote:
class coord
{
public:
int x;
int y;
};
class SolveMaze
{
public:
SolveMaze() { location.x = location.y = 0; }
bool Explore();
private:
listcoord visited;
coord location;
};
bool Explore()
{
// Determine if we've already been here
if (visited.found(location))
return false;
// Base case, we are at an exit
if (HasLadder()) return true;
// Remember that we have been here
visited.push(location);
// Try all four directions
for(direction = 0; direction 4; ++direction)
{
if (TryMove(direction))
{
coord prev(location); // Copy current location
// Track our current location
switch(direction)
{
case 0: --location.y; break;
case 1: ++location.x; break;
case 2: --location.x; break;
case 3: ++location.y; break;
}
// Explore from new location
if (this-Explore()) return true;
TryMove(3-direction); // Assume 3-direction is opposite move of
direction
// Back out location
location = prev;
}
}
// Remove current location from list
visited.pop();
// No exit found
return false;
}
On Mar 2, 9:05 am, bittu shashank7andr...@gmail.com wrote:
You are in a maze(like a labyrinth), and you open your eyes so you
don't know your position. The maze has walls and you can move only in
up, right, left and down directions. You can escape the maze when you
find a ladder.
The following API is given:
bool TryMove(direction) - returns true when you don't hit a wall;
bool HasLadder() - return true if you found the ladder.
Write a method bool Explore() that returns true if you can escape the
maze, false otherwise. Also, provide test cases.
A Good Explanation Pseudo-code, Algorithmic discussion
needed..Object Oriented is Also Welcome
Thanks Regards
Shahsank
--
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: A Billion Number Question
This only works if the file is sorted. If the file starts out with values 5,7,6,... and never contains another 7, the result will be 7, which is in the file. On Mar 17, 12:19 pm, arpit.gupta arpitg1...@gmail.com wrote: read the first no. . now ans= first no +1; if now ans is encountered while reading the next nos. add 1 to ans. i.e. ans++; On Mar 17, 2:18 am, bittu shashank7andr...@gmail.com wrote: Given an input file with four billion integers, provide an algorithm to generate an integer which is not contained in the file. Assume you have 1 GB of memory. 2nd Part What if you have only 10 MB of memory? Thank Shashank -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: random number generator
bool uniform()
{
static bool state = true;
state = !state;
return state ^ nonuniform();
}
On Mar 17, 9:24 am, saurabh agrawal saurabh...@gmail.com wrote:
Given a function which returns true 60% time and false 40% time.
Using this function you have to write a function which returns true 50% of
the 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.
[algogeeks] Re: random number generator
There is no upper bound on the runtime of this function.
On Mar 20, 4:33 pm, Jammy xujiayiy...@gmail.com wrote:
clearly the prob. of getting true|false and false|true are equal to
0.6*0.4. Therefore the following code works,
bool uniform(){
bool f1;
bool f2;
do{
f1 = non_uniform();
f2 = non_uniform();
}while(!(f1 ^ f2));
return f1;
}
On Mar 17, 10:24 am, saurabh agrawal saurabh...@gmail.com wrote:
Given a function which returns true 60% time and false 40% time.
Using this function you have to write a function which returns true 50% of
the 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.
[algogeeks] Re: subgraph
The easiest way to represent a weighted graph with N nodes is with an NxN array. However, with 65000 nodes, the memory required would almost certainly be a problem. Here is another way to do it: Use a structure to represent each edge. The struct contains the weight, one node id, and a pointer to an edge struct. Also have an array of edge struct pointers, one for each of the 65000 nodes. For each edge, create and populate two structs and insert one containing node_id2 into the linked list for node_id1 and the other containing node_id1 into the linked list for node_id2. Then you can find all edges from your current location by traversing the linked list. This should take about 15 megabytes of memory, which most computers can handle easily. Don On Mar 24, 11:21 am, snehal jain learner@gmail.com wrote: You have to create a graph in most efficient way from relationship of nodes read from txt file. text file contains information like: node_id weight node_id node_id weight node_id ….. // which means two nodes are connected with some weight. (undirected) There are around 600K such information for about 65000 nodes. Aim is to create a a subgraph for a given node_id. i.e for that node_id find ALL successor nodes with level mentioned i.e form a subgraph for that node. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: predominant colour
Even if N is one? On Mar 24, 12:25 pm, balaji a peshwa.bal...@gmail.com wrote: i think its red On Thu, Mar 24, 2011 at 10:44 PM, snehal jain learner@gmail.com wrote: You are given a blue segment S of length n. There are n points p_i (0 = i n) distributed uniformly at random. You mark in red all the segments connecting points p_i and p_j what would be the predominant colour in S after that? -- 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. -- A.Balaji -- 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: finds a pair of close numbers
// O(n) solution using binning
findClose(int n, double A[n])
{
// Find min and max
min = max = A[0];
for(i = 1; i n; ++i)
{
if (A[i] max) max = A[i];
if (A[i] min) min = A[i];
}
// Set up bins
int bins = n-1;
double binWidth = (max - min) / bins;
double binTable[bins] = {min-1.0};
// Now any two elements falling into same hash bin are close
// In addition, it is necessary to check the adjacent bins to see if
a close value is there
for(i = 0; i n; ++i)
{
// Determine which bin the value falls into
binIndex = (A[i] - min) / binWidth;
// If there is already a value there, the two values are close
if (binTable[binIndex] = min)
{
result = (A[i], binTable[binIndex]);
break;
}
// Check the next lower bin
if ((binIndex 0) and (binTable[binIndex-1] = min))
{
if ((A[i] - binTable[binIndex-1]) binWidth)
{
result = (A[i], binTable[binIndex-1]);
break;
}
}
// Check the next higher bin
if ((binIndex+1 bins) and (binTable[binIndex+1] = min))
{
if ((binTable[binIndex+1] - A[i]) binWidth)
{
result = (A[i], binTable[binIndex+1]);
break;
}
}
// Store value in the bin
binTable[binIndex] = A[i];
}
}
On Apr 1, 7:32 am, snehal jain learner@gmail.com wrote:
For a set S of n real numbers, a pair of elements x, y belong to S,
where x y, are said to be close if
y – x = ( max(S) – min(S) ) / (n-1)
Suppose you are given an unsorted array A[1 : n] of distinct real
numbers. Design an algorithm that finds a pair of close numbers in A
in O(n) time.
my solutions
1. brute force: complexity n2
2. sort the array.
take 2 ptrspt1 and pt2.initially pt1 points to 1st elementand pt2 pts
to 2nd element. check if they are close nos.
case1; if they r closeincrement pt2. and again check. repeat this
until u find close pairs. when pt1and pt2 doesnt pt to close pairat
this point all elements b/w pt1 and pt2 are also close. increment
close_pair_count accordingly, check if element jst b4 pt2 and at pt2
are also close.
case 2: increment both pt1and pt2 and continue
repeat above steps til u reach end of array..
m unable to think linear algo.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.
[algogeeks] Re: Please help in verifying the speed of this algorithm - factorizing or prime finder.
The General Number Field Sieve is the fastest known method of
factoring large numbers, but the elliptic curve method may be faster
in some cases. Either one is much faster than your method.
Don
On Apr 6, 12:58 pm, harish hareeshgn...@gmail.com wrote:
Hi all,
I have developed an algorithm to find factors of a given number. Thus
it also helps in finding if the given number is a prime number. I feel
this is the fastest algorithm for finding factors or prime numbers.
I have put the algorithm
here:http://randomoneness.blogspot.com/2011/04/algorithm-to-find-factors-o...
This one finds if a give number is prime in say time frame of 5*N
(where N is the input number). So I hope I can call this a linear time
algorithm.
Can anybody verify the above for me?
A faster version of algorithm i put here:
Input: A Number (whose factors is to be found)
Output: The two factor of the Number. If the one of the factor found
is 1 then it can be concluded that the
Number is prime.
Integer N, mL, mR, r;
Integer temp1; // used for temporary data storage
mR = mL = square root of (N);
/*Check if perfect square*/
temp1 = mL * mR;
if temp1 equals N then
{
r = 0; //answer is found
End;}
mR = N/mL; (have the value of mL less than mR)
r = N%mL;
while r not equals 0 do
{
mL = mL-1;
r = r+ mR;
temp1 = r/mL;
mR = mR + temp1;
r = r%mL;}
End; //mR and mL has answer
--
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: C puzzle
In fn, ptr is a local variable passed by value. Changing ptr in the
function does not change anything in main.
Don
On Mar 31, 10:35 pm, navin navin.myhr...@gmail.com wrote:
see this c code.
#includestdio.h
void fn (int *ptr)
{
const int val=100;
ptr=val;}
void fn1(int *ptr)
{
*ptr = 100;
}
main()
{
int i=10;
printf(%d , i);
fn(i);
printf(%d , i);
fn1(i);
printf(%d , i);
}
What is the difference between fn and fn1?
I expected the output to be 10 100 100
but it came as 10 10 100.
can anyone explain what happens in fn.
why 100 in fn is not stored in ptr.
--
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: Please help in verifying the speed of this algorithm - factorizing or prime finder.
This link has an online application which factors large numbers using the Elliptic Curve method. http://www.alpertron.com.ar/ECM.HTM Try a value like 12991627363868130524522557049357159496792541860595064869631. On my computer this application factors this number in 15 seconds. Anything relying on trial division would take longer than your computer will last. Don On Apr 7, 9:11 am, harish hareeshgn...@gmail.com wrote: Hi All, I got a reply at another forum; here is the link for thathttp://stackoverflow.com/questions/5581040/i-have-a-new-algorithm-to-... .. Don i believe you are correct. Thanks Harish On Apr 7, 4:56 pm, harish hareeshgn...@gmail.com wrote: Hi Don, I reposting my reply to you to all now.. The GNFS mentioned here is polynomial time as I got to understand from wikipedia. I claim that the above algorithm is linear time. I putting the proof here for correctness and linear time (warning its big and messy). Also this one applies to the algorithm given in the blog:http://randomoneness.blogspot.com/2011/04/algorithm-to-find-factors-o... (The above given is a faster version of the one given in my blog) Analysis of algorithms: In below proof used: Operation A is: While r is smaller than mL then, mL can be decremented by one and the new r can be computed as r + mR. As taking out one mL, means one mR is send to remainder. (first inner while loop) Operation B is: While r is bigger than mL, then mL can be taken out from r and this basically increases mR by one. (2nd inner while loop) Operation C is: Operations A and B can be repeated till, r not equals mL. When we arrive at the results, Operation C is exited. (main while loop) 1. Proof of correctness: If the number is a perfect square root then, the answer is found when square root is found. For more reading on Square root refer:http://en.wikipedia.org/wiki/Square_root Else if the number is not a perfect square, then r is not equal to 0. Hence it enters the while loop. Operation A: While mL is greater than r, then mL is decremented by 1, and r is incremented by mR. The step is correct because, mL * mR means mR added mL times. If one is taken from mL, then mR is added (mL-1) times. So, one mR is added less, when taking one out of mL. This mR is added to r. – (1) Operation B: While mL is less than r, then mR is incremented by 1 and r is decremented by mL. This step is correct because, mL * mR means mL added mR times. If one is added to mR, then mL is added (mR + 1) times in mL*mR. So if mR is incremented by 1, then to equate to N, mL can be taken away from r the remainder. – (2) Operation C: Operation A and B are repeated till mL is equal to r. This leads to the answer because: We start from the approximate square root of the number. As operation A and B, calculates the remainder r, when the factors are mL and mR. Operation A never leads to the answer as, r + mR is always greater than mL, as mL is smaller than mR. Operation B, leads to the answer. If for any case mL is a factor, then, when r is reduced by mL in operation B to mL (r becomes a factor of mL). As Operation A and B are correct (refer 1 and 2), if there is a factor then this leads to r to be zero. And before r becomes zero, r should be equal to mL. At this point the answer is found. 2. Proof that the number of Operations required is linear: Let’s take only the case of numbers which are not perfect squares. The algorithm consists of basic operations, of addition, subtraction and comparison. Let’s see how many times a different while loops are invoked. We take mL as nearest square root. And take mR mL. There for Operation A is invoked only once during one iteration of the Operation C. This is because, by incrementing r by mR, increases r to be greater than mL (mR mL) and hence invalidates the loop condition. The basic number of steps in Operation A is 3: 1. While loop evaluation, 2. decrement mL by 1 and 3. Increment r by mR. Operation B is repeated to find a r which is greater than mL. As mR varies as algorithm progress, its hard to calculate number of time r Operation B is repeated. The basic number of steps in Operation B is 3: 1. while loop evaluation, 2. Increment mR by 1 and 3. Decrement r by mL. However two things are certain, for worst case scenario i.e. N is prime number, mL is reduced to 1 and mR is incremented to N. From this we can conlude that, Operation B is repeated N-sqrt(N) times i.e. Increment mR to N from sqrt(N) and Operation A is repeated till mL becomes 1 i.e from sqrt(N) to 1. Based on this the number of steps required is: Operation B : N – sqrt(N) Operation A : sqrt(N) And the Operation C, which apart from the steps we calculate from Operation A and Operation B, will have 2 basic steps; 1. the main while evaluation, 2. the exit evaluation of one of the while either of Operation
[algogeeks] Re: Permutation of a string
int main(int argc, char* argv[])
{
char string[13];
char tmp[13];
int len, i, j, k, n;
printf(Length of string: );
fgets(string, 13, stdin);
sscanf(string, %d, len);
if (len 12) len = 12;
printf(Enter string: );
fgets(string, len+1, stdin);
string[len] = 0;
n = 1;
for(i = 0; i len; ++i)
n *= i+1;
printf(There are %d permutations\n, n);
for(i = 0; i n; ++i)
{
for(j = 0; j = len; ++j)
tmp[j] = string[j];
k = i;
for(j = 0; j len; ++j)
{
int indx = j + (k % (len-j));
char t=tmp[indx];
tmp[indx] = tmp[j];
tmp[j] = t;
}
printf(%s\n, tmp);
}
return 0;
}
On Apr 8, 1:34 pm, Subhransu subhransu.panigr...@gmail.com wrote:
What could be the efficient algo for finding permutation of string.
Lets say a user enter a string abc.
The output should be 6(3*2*1) along with he combination of them like
abc
bca
cab
bac
acb
cba
*Subhransu Panigrahi
*
*Mobile:* *+91-9840931538*
*Email:* subhransu.panigr...@gmail.com
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Permutation of a string
int main(int argc, char* argv[])
{
char string[13];
char tmp[13];
int len, i, j, k, n=1;
printf(Length of string: );
fgets(string, 13, stdin);
sscanf(string, %d, len);
if (len 12) len = 12;
printf(Enter string: );
fgets(string, len+1, stdin);
string[len] = tmp[len] = 0;
for(i = 2; i = len; ++i)
n *= i;
printf(There are %d permutations\n, n);
for(i = 0; i n; ++i)
{
k = i;
tmp[0] = string[0];
for(j = 1; j len; ++j)
{
int indx = k % (j+1);
k /= (j+1);
tmp[j] = tmp[indx];
tmp[indx] = string[j];
}
printf(%s\n, tmp);
}
return 0;
}
On Apr 8, 1:34 pm, Subhransu subhransu.panigr...@gmail.com wrote:
What could be the efficient algo for finding permutation of string.
Lets say a user enter a string abc.
The output should be 6(3*2*1) along with he combination of them like
abc
bca
cab
bac
acb
cba
*Subhransu Panigrahi
*
*Mobile:* *+91-9840931538*
*Email:* subhransu.panigr...@gmail.com
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: finding n numbers having particular sum
const int setSize = 20;
int set[setSize] =
{ 5,9,1,3,4,2,6,7,11,10,13,15,19,22,25,31,33,37,39,40};
const int sum = 150;
int rec[setSize];
int recCount = 0;
int subset=0;
void search(int *set, int setSize, int sum)
{
int i;
if (sum == 0)
{
printf(Subset %d: {%d, ++subset,rec[0]);
for(i = 1; i recCount; ++i)
printf(,%d, rec[i]);
printf(}\n);
}
else if (sum 0)
{
for(i = 0; i setSize; ++i)
{
rec[recCount++] = set[i];
search(set, i, sum-set[i]);
--recCount;
}
}
}
int main(int argc, char* argv[])
{
search(set, setSize, sum);
return 0;
}
On Apr 18, 6:16 am, kamlesh yadav kamleshlu2...@gmail.com wrote:
given an array of elements (all elements are unique ) , given a sum
s find all the subsets having sum s.
for ex array {5,9,1,3,4,2,6,7,11,10}
sum is 10
possible subsets are {10}, {6,4} ,{7,3} {5,3,2}
{6,3,1} etc. there can be many more.
also find the total number of these subsets
--
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: Basic Algorithms!!
Knuth, The Art of Computer Programming On Apr 19, 4:06 am, Vishnutej mylavarapu.vishnu...@gmail.com wrote: Hello everyone, Wat according to u are the basic algorithms that a programmer should know for sure? If possible just let me know of the resource in which it is best explained. Thanks in advance. -Vishnutej.Mylavarapu -- 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: JigSaw Puzzle
First you need a Piece class to represent one piece of a puzzle. Each piece has four sides, each one with a unique outline which will only connect to one other piece. Edge sides have an edge outline. Each side also has a piece id attribute called adjacent to store the value of the piece it connects to. Piece provides a rotate method which turns the piece 90, 180, or 270 degrees. The Jigsaw class has a number of pieces in the puzzle and a container of pieces. The Solve method uses a map to store the association of edges to pieces. It iterates through the pieces and for each edge, looks to see if its compliment is in the map. If so, it rotates the new piece to the correct orientation and sets the adjacent fields in the two edges to point at each other. If not, it adds the edge to the map. With one pass through the pieces, it should have all the pieces in the correct orientation and connected to all of the adjacent pieces. On Apr 25, 10:00 am, bittu shashank7andr...@gmail.com wrote: 1 .Design The JizSaw Puzzle Object Oriented Design(OOD) 2 Design the data structures and explain an algorithm to solve the puzzle. No Code Needed, A Good Discussion Algorithmic, Complexity Discussion is Sufficient Thanks Shashank -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: sort in minimum cost
I don't understand your example. If the input has only one 3, and the output has more than one, you have not sorted the elements. Do you mean alter the elements to make the array non-decreasing? Don On Apr 25, 4:21 am, snehal jain learner@gmail.com wrote: Given n elements, sort the elements. Here, only one operation is permitted decreaseValue.. Note that you cannot swap the values.. output should be a sorted list.. if input is 4 5 2 1 3 output is 3 3 3.. There can be many answers.. Give the optimum solution with minimum cost. where as cost is the sum of decreased amounts.. -- 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: Stroustrup C++ BOOK
I have the first edition signed by Stroustrup. I know that doesn't help you, but it is kind of cool, at least if you are an Algorithm Geek. Don On Apr 23, 8:31 am, UMESH KUMAR kumar.umesh...@gmail.com wrote: hi. Do you have anybody C++ by Stroustrup e-book please send on group. Thanks and Regards Umesh kumar -- 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: N queen problem in 3D I want guidelines to solve problem
Number the board locations 0..n^3-1. Write a function bool search(int startingLocation, int queensToPlace) If queensToPlace is zero, this is your base case. Output the board and you are done. The function loops over the locations from the startingLocation to the end of the board. If each location is a legal spot to place a queen, put one there and call search recursively starting at your current location+1, placing one fewer queens. Remove the queen from that location and move on to the next. I didn't say much about how to determine is a move is legal. The brute force method of scanning every line for another queen is complicated and slow. A better way is to maintain a mapping from each board location to the rows it belongs to. In a 3D board a location might belong to as many as 13 rows. For each row, keep a count of how many queens are in that row. A move is not legal if any of the rows already contain a queen. When you place a queen you must update (increment) all of the rows for that location, and when you remove it, you must decrement the counts. Don On Apr 27, 3:08 am, ARM1610 ashishrmod...@gmail.com wrote: Hello all, I'm not getting how to solve a 3 d version of n queen problem. The specification are A n*n*n board is given, arrange n*n queens such that not a single queen crosses(kills) any other queen. Use back tracking or divide and conquer. All solutions / suggestions are welcome !! Thanking You in advance !! Regards Ashish VIT Pune -- 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: A SIMPLE C++ PROGRAM.
The code is undefined, meaning that a valid compiler can produce any result that it wants. Multiple side effects between sequence points are not defined. It would be perfectly acceptable for a valid compiler to shoot flying monkeys out of your monitor. And it would serve you right for writing such code. Don On Apr 29, 3:31 am, MANNU manishkr2...@gmail.com wrote: *Can anyone please explain me the output of this program:* int x=1; int y=x++ + ++x + ++x + x++; couty; coutx; -- 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] Run for a google years
What is the shortest single line in a C program which will take more than a google years to execute, but will eventually complete? You are permitted to have code before or after the line, but execution of the code must remain on that line, meaning no function calls, etc. Assume a processor which executes 1 billion operations a second. -- 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: Run for a google years
That would do it if you have a 64-bit type, which most implementations
have, but the standard does not require.
I think that I can make it shorter and cleaner.
int main(int argc, char* argv[])
{
const int n=49;
char a[n]={0};
int p=0;
// This line will run for 10^100 years
for(; p n; p = ++a[p] ? 0 : p + 1);
return 0;
}
The array of 49 bytes provides 392 bits of state, which will take more
than the 2^387 cycles available in a google years.
If the processor takes 9 operations to execute the loop, a value of
n=48 would be sufficient.
Don
On May 7, 12:24 pm, Dave dave_and_da...@juno.com wrote:
@Don: Here is my solution:
unsigned long long int a=1;
unsigned long long int b=0;
unsigned long long int c=0;
unsigned long long int d=0;
unsigned long long int e=0;
unsigned long long int f=0;
unsigned long long int g=0;
unsigned long long int h=0;
/* here is the line /
while(a)if(!++h)if(!++g)if(!++f)if(!++e)if(!++d)if(!++c)if(!++b)++a;
My reasoning is as follows: 1 google years ~= 10^116.5 nanoseconds ~=
2^387. Thus, incrementing an integer of length 387 bits once every
nanosecond should take a google years to overflow. Seven 64-bit
integers provides 448 bits of state.
Dave
On May 6, 11:25 am, Don dondod...@gmail.com wrote:
What is the shortest single line in a C program which will take more
than a google years to execute, but will eventually complete? You are
permitted to have code before or after the line, but execution of the
code must remain on that line, meaning no function calls, etc. Assume
a processor which executes 1 billion operations a second.
--
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: Test Cases
I would add that you should test all combinations of positive and negative operands. You are not clear about the type being divided. If it is a floating point type, you can verify that (a*b) / b = a to an acceptable tolerance for a wide variety of values of a and b. If you are working with integers, the case 4 below is good, given r b. Don On May 10, 11:12 am, Praveen Kumar praveen97...@gmail.com wrote: cases would be: 1. division by 0 raises an appropriate Exception 2. dividing 0 by any number should result in 0 3. dividing any number by 1 should give the same number 4. a = b*q + r i.e a/b should give q On Tue, May 10, 2011 at 7:52 PM, Carl Barton odysseus.ulys...@gmail.comwrote: Don't really get the question On 10 May 2011 09:08, Akshata Sharma akshatasharm...@gmail.com wrote: write test cases for the division '/' operator.. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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: Run for a google years
I don't know that it takes exactly 9 operations. I ran the program on
my 3 GHz computer with n=4. It took 17 seconds. 17*3 billion / 2^32 is
11.87 clock cycles per iteration through the loop. A clock cycle is
not the same as an operation, because many machine operations take
more than one clock cycle. If the computer we are using for this
problem can run one iteration of the loop as a single operation, n=49
would be enough. If it takes 9 operations, n=48 would be enough. So it
depends on the computer, and I don't really have enough information to
say which value of n to use. However, n=49 certainly meets the
requirements of the problem, even if it is excessive.
Don
On May 11, 7:11 am, Aamir Khan ak4u2...@gmail.com wrote:
On Mon, May 9, 2011 at 8:31 PM, Don dondod...@gmail.com wrote:
That would do it if you have a 64-bit type, which most implementations
have, but the standard does not require.
I think that I can make it shorter and cleaner.
int main(int argc, char* argv[])
{
const int n=49;
char a[n]={0};
int p=0;
// This line will run for 10^100 years
for(; p n; p = ++a[p] ? 0 : p + 1);
return 0;
}
The array of 49 bytes provides 392 bits of state, which will take more
than the 2^387 cycles available in a google years.
If the processor takes 9 operations to execute the loop, a value of
n=48 would be sufficient.
Can you elaborate the 9 operations that execution of for loop will take.
Don
On May 7, 12:24 pm, Dave dave_and_da...@juno.com wrote:
@Don: Here is my solution:
unsigned long long int a=1;
unsigned long long int b=0;
unsigned long long int c=0;
unsigned long long int d=0;
unsigned long long int e=0;
unsigned long long int f=0;
unsigned long long int g=0;
unsigned long long int h=0;
/* here is the line /
while(a)if(!++h)if(!++g)if(!++f)if(!++e)if(!++d)if(!++c)if(!++b)++a;
My reasoning is as follows: 1 google years ~= 10^116.5 nanoseconds ~=
2^387. Thus, incrementing an integer of length 387 bits once every
nanosecond should take a google years to overflow. Seven 64-bit
integers provides 448 bits of state.
Dave
On May 6, 11:25 am, Don dondod...@gmail.com wrote:
What is the shortest single line in a C program which will take more
than a google years to execute, but will eventually complete? You are
permitted to have code before or after the line, but execution of the
code must remain on that line, meaning no function calls, etc. Assume
a processor which executes 1 billion operations a second.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Aamir Khan
Indian Institute of Technology Roorkee,
Roorkee, Uttarakhand,
India , 247667
Phone: +91 9557647357
email: aami...@iitr.ernet.in aamir...@iitr.ernet.in
ak4u2...@gmail.com
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Problem
For small numbers, trial division would work. Be sure to only divide by prime numbers. When you find one which divides your target, increment your counter and divide the target by that number as many times as it works. Then go on to the next prime. When the prime squared is larger than the target, you are done. The number of divisors is 2 times the product of the number of times each prime divided the target. For large numbers you need to look into methods for factoring large numbers. You would want to start with a test to determine that the number is composite. If not, it has 2 divisors. Then try to divide the number by small primes. Then use one of the factoring algorithms such as the General Number Field Sieve to find factors. Don On May 11, 8:55 am, Harshit Gangal harshit.gan...@gmail.com wrote: How can we calculate the number of divisors a number have in minimum time or having minimum Time Complexity. -- Harshit Gangal Fourth Year Undergraduate Student Dept. of Computer Science JIIT, Noida , India -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: prim problem
No idea. It would help to tell us what it is intended to do and what
it is actually doing, and maybe include the main function so we can
see how it is called and how the global variables are initialized.
On May 15, 1:45 pm, Edu edu.cv...@gmail.com wrote:
Hi, this should be working, where is the problem?
const int INF=99;
int n=6;
int weights[6][6];
int parent[6];
int idistance[6];
int rec[6];
struct lesst{
bool operator()(const inta,const intb){
return (idistance[a]idistance[b]);
}
};
int prim(int s){
int u,v,i;
priority_queueint,vectorint,lesstQ;
idistance[s]=0;
Q.push(s);
for(i=0;in;++i){
if(i==s)continue;
idistance[i]=INF;
parent[i]=-1;
Q.push(i);
}
while(!Q.empty()){
u=Q.top();
rec[u]=1;
Q.pop();
for(v=0;vn;++v){
if(weights[u][v]==0);
else if(!rec[v] weights[u][v]idistance[v]){
parent[v]=u;
idistance[v]=weights[u][v];
}
}
}
return idistance[s];
}
--
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: how to find a smallest prime bigger than a given number
Yes. Use a sieve. Don On May 17, 11:36 pm, wujin chen wujinchen...@gmail.com wrote: @Dave， thanks for your reply. i know that, i can only check from 6*n - 1 and 6*n + 1.. assume that, n=1 , and we begin from k=1667, the number needed to check is 10001,10003 but to determin 10001 is prime or not costs a lot, right? when the n is huge, it will be not feasible. is there some math principle to solve this problem easily? 2011/5/18 Dave dave_and_da...@juno.com @Wujin: Well, obviously, you don't have to check _every_ number one-by- one. If n 1, you can ignore every even number. Furthermore, if n 3, you can ignore every odd multiple of 3. That means that you need to check only numbers of the form 6*n - 1 and 6*n + 1. Dave On May 17, 9:09 pm, wujin chen wujinchen...@gmail.com wrote: given a number n, compute the smallest prime that is bigger than n. for example, n=8, then the smallest prime that bigger than 8 is 11. i wonder whether there is an effective way, rather than check every number bigger than n one by one. thanks. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: strings
bool interleaved(char *s1, char *s2, char *s3)
{
return (!*s1 !*s2 !*s3) || // Base case, all strings are
empty
(*s1 (*s1 == *s3) interleaved(s1+1,s2,s3+1)) || // First
character of s1 is next in s3
(*s2 (*s2 == *s3) interleaved(s1,s2+1,s3+1));// First
character of s2 is next in s3
}
On May 19, 1:33 pm, Piyush Sinha ecstasy.piy...@gmail.com wrote:
Design an algorithm to find whether a given string is formed by the
interleaving of two given strings or not. e.g. s1= aabccabc s2= dbbabc s3=
aabdbbccababcc Given s1,s2,s3 design an efficient algorithm to find whether
s3 is formed from the interleaving of s1 and s2
--
*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.
[algogeeks] Re: strings
bool interleaved(char *s1, char *s2, char *s3)
{
// Base case, all strings are empty
return (!s1[0] !s2[0] !s3[0]) ||
// First character of s1 is next in s3
(s1[0] (s1[0] == s3[0]) interleaved(s1+1,s2,s3+1)) ||
// First character of s2 is next in s3
(s2[0] (s2[0] == s3[0]) interleaved(s1,s2+1,s3+1));
}
On May 19, 1:33 pm, Piyush Sinha ecstasy.piy...@gmail.com wrote:
Design an algorithm to find whether a given string is formed by the
interleaving of two given strings or not. e.g. s1= aabccabc s2= dbbabc s3=
aabdbbccababcc Given s1,s2,s3 design an efficient algorithm to find whether
s3 is formed from the interleaving of s1 and s2
--
*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.
[algogeeks] Re: strings
This is the same algorithm as my previous solution. Both produce the
correct result, but this one does not have tail recursion, so it will
run faster.
bool interleaved2(char *s1, char *s2, char *s3)
{
while(1)
{
if (!s1[0] !s2[0] !s3[0]) return true;
if (s1[0] == s3[0])
{
if (s2[0] == s3[0])
{
if (interleaved2(s1+1, s2++,s3+1)) return true;
}
else ++s1;
}
else
{
if (s2[0] == s3[0]) ++s2;
else return false;
}
++s3;
}
}
On May 19, 1:33 pm, Piyush Sinha ecstasy.piy...@gmail.com wrote:
Design an algorithm to find whether a given string is formed by the
interleaving of two given strings or not. e.g. s1= aabccabc s2= dbbabc s3=
aabdbbccababcc Given s1,s2,s3 design an efficient algorithm to find whether
s3 is formed from the interleaving of s1 and s2
--
*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.
[algogeeks] Re: strings
There are some things which could be done to make the program run
faster in some cases.
For example, either version of my solution above will take a very long
time to determine that these inputs are not interleaved:
s1 = aa
s2 = aa
s3 =
aaab
Adding code at the beginning to be sure that s3 has the same number of
instances of each character as s1 and s2 would be quick and would make
that case much faster.
Don
On May 20, 10:12 am, Don dondod...@gmail.com wrote:
This is the same algorithm as my previous solution. Both produce the
correct result, but this one does not have tail recursion, so it will
run faster.
bool interleaved2(char *s1, char *s2, char *s3)
{
while(1)
{
if (!s1[0] !s2[0] !s3[0]) return true;
if (s1[0] == s3[0])
{
if (s2[0] == s3[0])
{
if (interleaved2(s1+1, s2++,s3+1)) return true;
}
else ++s1;
}
else
{
if (s2[0] == s3[0]) ++s2;
else return false;
}
++s3;
}
}
On May 19, 1:33 pm, Piyush Sinha ecstasy.piy...@gmail.com wrote:
Design an algorithm to find whether a given string is formed by the
interleaving of two given strings or not. e.g. s1= aabccabc s2= dbbabc s3=
aabdbbccababcc Given s1,s2,s3 design an efficient algorithm to find whether
s3 is formed from the interleaving of s1 and s2
--
*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.
[algogeeks] Re: strings
Your iterative solution does not work in cases where both s1 and s2
have the next character in s3, but only choosing the s2 character next
will result in correct interleaving.
s1 = ab
s2 = axb
s3 = axabb
Your iterative solution will say that these are not interleaved, but
they really are.
Don
On May 20, 2:21 pm, immanuel kingston kingston.imman...@gmail.com
wrote:
A Recursive solution:
int interleaved(char *s1, char *s2, char *s3) {
if (s1 == null s2== null s3==null) return 1;
if (s3==null) return 0;
if (s1 != null *s1 == *s3) return interleaved(s1+1,s2,s3+1);
else if (s2 != null *s2 == *s3) return interleaved(s1, s2+1,s3+1);
return 0;
}
Iterative solution:
int interleaved(char *s1, char *s2, char *s3) {
if (s1 == null s2== null s3==null) return 1;
if (s3==null) return 0;
while (*s3) {
if (s1 != null *s1 == *s3) {
s1++;
}
else if (s2 != null *s2 == *s3) {
s2++;
} else {
return 0;
}
s3++;
}
return (s1 == null) (s2 == null) (s3 == null);
}
Thanks,
Immanuel
On Fri, May 20, 2011 at 8:42 PM, Don dondod...@gmail.com wrote:
This is the same algorithm as my previous solution. Both produce the
correct result, but this one does not have tail recursion, so it will
run faster.
bool interleaved2(char *s1, char *s2, char *s3)
{
while(1)
{
if (!s1[0] !s2[0] !s3[0]) return true;
if (s1[0] == s3[0])
{
if (s2[0] == s3[0])
{
if (interleaved2(s1+1, s2++,s3+1)) return true;
}
else ++s1;
}
else
{
if (s2[0] == s3[0]) ++s2;
else return false;
}
++s3;
}
}
On May 19, 1:33 pm, Piyush Sinha ecstasy.piy...@gmail.com wrote:
Design an algorithm to find whether a given string is formed by the
interleaving of two given strings or not. e.g. s1= aabccabc s2= dbbabc
s3=
aabdbbccababcc Given s1,s2,s3 design an efficient algorithm to find
whether
s3 is formed from the interleaving of s1 and s2
--
*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.
[algogeeks] Find closest point
If I have a big database of points on the surface of the earth, each one represented as a latitude and longitude, provide an efficient algorithm to find the point closest to a requested location. Be sure to consider angle wrap. Don -- 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: Find closest point
I'm more interested in finding a good data structure to store the points so that it is quick to narrow down the search to the points which are fairly close. Think of a database with millions of points, and there is not time to compute a distance to each one. Don On May 24, 8:15 am, sravanreddy001 sravanreddy...@gmail.com wrote: @anshu.. I wanted to say to that.. even though I couldn't think of the trignometic stuff.. thanks.. :) --Sravan. -- 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: Ball Hole science puzzle 24 may
Fill the pipe with water so that the ball floats out. Don On May 24, 2:22 am, Lavesh Rawat lavesh.ra...@gmail.com wrote: Ball Hole science puzzle SOLUTION * * ** *Your last good ping-pong ball fell down into a narrow metal pipe imbedded in concrete one foot deep.How can you get it out undamaged, if all the tools you have are your tennis paddle, your shoe-laces, and your plastic water bottle, which does not fit into the pipe? * *Update Your Answers at* : Click Herehttp://dailybrainteaser.blogspot.com/2011/05/ball-hole-science-puzzle... Solution: Will be updated after 1 day -- Never explain yourself. Your friends don’t need it and your enemies won’t believe it . -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: strings
But checking the count is a good first step. If the count doesn't match the result is false. If the count does match, you need to check further. I found that my test set ran 10x faster if I checked the count first. Don On May 26, 6:11 am, sunny agrawal sunny816.i...@gmail.com wrote: @senthil nopes, it will not work eg. S3 = cba S1 = a S2 = bc count matches but not interleaved On Thu, May 26, 2011 at 2:43 PM, Senthil S senthil2...@gmail.com wrote: Can it be done this way ..Take count of each alphabet for all the three strings and store separately.. Then for each alphabet in the third string, check if its count is equal to the sum of the counts of the corresponding alphabet in the first two strings .. If the counts match for all alphabets then the third string is an interleaving of the first two .. -- 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.
[algogeeks] Re: Puzzle
To solve this, look at an 8x8 grid representing the games played. The diagonal is not used, because teams do not play themselves. Below the diagonal is the first game between each team and above the diagonal is the second game. Assume that teams 1-4 are the ones who will go to the semi-finals. This means that you only need to assign winners in the first 4 rows and first 4 columns. The lower right of the grid can remain empty. Start by assigning team 1-4 as the winner every time they play teams 5-8. That gives teams 1-4 eight wins each. That leaves just 12 games left to assign in the top left quarter of the grid. It is not hard to assign them so that each time wins 3 of the games, meaning that it takes 11 games to assure a spot in the semi-finals. Here is a grid of results for one such outcome: X134 1X24 12X3 423X 1234 1234 1234 1234 Don On May 12, 1:44 pm, amit amitjaspal...@gmail.com wrote: Consider a series in which 8 teams are participating. each team plays twice with all other teams. 4 of them will go to the semi final.How many matches should a team win, so that it will ensure that it will go to semi finals.? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Sudoku verification problem
A data structure could be a mapping from each of the N*N cells to the three regions it belongs to, and then for each region, a set of N bits indicating which values it already contains. Then the validation simply involves iterating over the cells. For each one, if any of the three regions already contain the value of that cell, validation fails. Otherwise, set the bit for that value in the three regions. A more challenging problem: Given an unsolved Sudoku puzzle with some given cells and some unknown cells, either indicate that there is no solution, provide the one unique solution, or report that there are multiple solutions and provide one example. Don On May 28, 1:23 am, Dumanshu duman...@gmail.com wrote: Given a n by n matrix. Suggest an algorithm to verify its correctness given a configuration. User can enter numbers only between 1 to n. I need this in 2 ways - 1. for the n by n matrix, suggest an elegant way for validating it. 2. suggest a data structure for this sudoku so that the structure aids in its verification. thnx for the 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.
[algogeeks] Re: c output
That may be true, but it is not guaranteed. Having multiple side affects between sequence points is undefined by the ANSI standard. Therefore an ANSI-compliant compiler could produce an executable which causes monkeys to fly out of your nose. Don On Jun 1, 11:27 am, anuj agarwal coolbuddy...@gmail.com wrote: This will be same as: b=b+1; b=b+1; a=b*b; Basically, all prefix increment and decrement operators will be executed first. Similarly all postfix operators will be executed at last. Anuj Agarwal Engineering is the art of making what you want from things you can get. On Wed, Jun 1, 2011 at 5:27 PM, Vishal Thanki vishaltha...@gmail.comwrote: you may want to read:http://c-faq.com/expr/seqpoints.html On Wed, Jun 1, 2011 at 5:19 PM, himanshu kansal himanshukansal...@gmail.com wrote: a=++b*++b; if b=3 initially, then a is coming out to be 25.why -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Finding circle areas under dust bins
Assume that the people are more sparse or not uniformly distributed, so that you don't need to cover all of the area to cover all of the people. I would think about something like this: For each pair of two people who are not already within 100 meters of a dustbin, but are within 100 meters of each other, consider the two locations for a dustbin exactly 100 meters from both of them. Count the number of people within 100 meters of each of those locations who are not already within 100 meters of a dustbin. Add a dustbin in the one location which covers the largest number of new people. Repeat until everyone is covered. That is not guaranteed to minimize the number of bins, but it should be close. Don On May 31, 3:54 pm, Logic King crazy.logic.k...@gmail.com wrote: If the number of people is large then putting the dustbin in hexagonal fashion as we do in mobile networks should minimize the number of dustbin ... On Tue, May 31, 2011 at 9:35 AM, ross jagadish1...@gmail.com wrote: -- 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: type 'int' unexpected
You need parentheses around int: sizeof(int)
Don
On Jun 2, 2:41 pm, asit lipu...@gmail.com wrote:
Please consider the following code
// dequeue.cpp : Defines the entry point for the console application.
//
#include stdafx.h
#include iostream
#include deque
#include algorithm
using namespace std;
struct print
{
void operator() (int i)
{
cout i;
}
}myprint;
int _tmain(int argc, _TCHAR* argv[])
{
dequeint first;
dequeint second(4, 100);
dequeint third(second.begin(), second.end());
dequeint fourth = third;
int arr[] = {32, 5, 332, 78, 8};
dequeint fifth(arr, arr+(sizeof(arr)/sizeof int)); //Line 28
coutthird : ;
for_each(third.begin(), third.end(), myprint);
coutendl;
coutfourth : ;
for_each(fourth.begin(), fourth.end(), myprint);
coutendl;
coutfifth : ;
for_each(fifth.begin(), fifth.end(), myprint);
coutendl;
return 0;
}
When I compile the above code it gives the following error.
Line 28 : type 'int' unexpected
--
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: MS Q
Are we drawing a circle on the screen? In addition to Harshal's suggestions, try putting the center off the screen, but have part of the circle on the screen: x=-10 y=-20 r=100 Don On Jun 2, 9:19 am, Ashish Goel ashg...@gmail.com wrote: Given a function to draw a circle with input paramters as co-ordinates of centre of the circle and r is the radius of the circle. How will you test this function, what will be additional non-functional test cases Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 -- 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: c output
An ANSI-compliant compiler is not required to generate an error for undefined code. The code syntax is correct. ANSI doesn't say what the compiler must do for undefined code, which is why it is undefined. The compiler can do anything. It might do what you expect, or it might not. Don On Jun 1, 1:38 pm, richa mahajan m.rich...@gmail.com wrote: if it is undefined by standard den y dont compilers follow it On Wed, Jun 1, 2011 at 11:59 PM, Don dondod...@gmail.com wrote: That may be true, but it is not guaranteed. Having multiple side affects between sequence points is undefined by the ANSI standard. Therefore an ANSI-compliant compiler could produce an executable which causes monkeys to fly out of your nose. Don On Jun 1, 11:27 am, anuj agarwal coolbuddy...@gmail.com wrote: This will be same as: b=b+1; b=b+1; a=b*b; Basically, all prefix increment and decrement operators will be executed first. Similarly all postfix operators will be executed at last. Anuj Agarwal Engineering is the art of making what you want from things you can get. On Wed, Jun 1, 2011 at 5:27 PM, Vishal Thanki vishaltha...@gmail.com wrote: you may want to read:http://c-faq.com/expr/seqpoints.html On Wed, Jun 1, 2011 at 5:19 PM, himanshu kansal himanshukansal...@gmail.com wrote: a=++b*++b; if b=3 initially, then a is coming out to be 25.why -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Million Numbers
Create a range tree, pruning out as needed to stay in the memory constraint. Don On Jun 9, 6:24 am, Dumanshu duman...@gmail.com wrote: Given a file containing roughly 300 million social security numbers(9- digit numbers) find a 9-digit number that isnt there in the file. You have unlimited drive space but only 2mb of RAM. Solution is as follows: In the first step, we build an array of 2^16 integers that is initialized to 0 and for every number in the file we take its 16 most significant bit to index into this array and increment that number. Since there are less than 2^32 numbers in the file there is bound to be one number in the array that is less than 2^16 . This tells us that there is at least one number missing among the possible numbers with those upper bits. In the second pass, we can focus only on the numbers that match this criterion and use a bit-vector of size 2^16 to identify one of the missing numbers. Someone plz explain this solution( may be using some small values numbers) or suggest another approach. -- 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: is it correct??
One line or the other is not correct. The size of an array must be a constant, and you can't read into a const. If you want to do something like this, use malloc: cin x; int *a = (int *)malloc(x*sizeof(int)); You can now use a as if it is an array of size x. Be sure to free the memory before a goes out of scope. Don On Jun 14, 9:39 am, amit amitthecoo...@gmail.com wrote: is such a declaration correct: cinx; int a[x]; -- 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: Intuitive Understanding of XOR Operation
It is important to remember that xor is a bitwise operator, so x ^= y affects the individual bits of x based on the bits in y. Think of xor as a bitwise not-equal operator. The expression a = x ^ y Will set the bits of a to true if the corresponding bits of x and y are not equal. Thus the xor operator is a good way to toggle selected bits in a value. If I want to toggle the 1, 4, and 8 bit in x, I can write x ^= 13. A nice property of xor is that it is self-reversing: a ^= b; // Toggle the bits set in b a ^= b; // Reverse the operation After those two operations, a has the same value it had before. That doesn't seem useful, but imagine that you are writing an application where you allow the user to select a region in an image by clicking on one corner and then drawing a rubber band box which follows the mouse to select the other corner. If you just draw a white line, you obliterate the image, so you would need to copy the pixels which are covered by the box. But if you xor the pixels by some value to draw the box, and xor the pixels again with the same value you end up with the original value of the pixel. The same thing can be used to encrypt data. If you xor each byte by a byte produced by a stream generator based on a secret key, the recipient can repeat the process and get the original data back. Don On Jun 13, 9:18 pm, Navneet Gupta navneetn...@gmail.com wrote: Hello, I would really appreciate if someone can help me get an intuitive understanding of XOR over a range of numbers. I have seen it's usage is a couple of problems where duplicates are involved and though ultimately i can see how it is solving the problem, i still feel like checking the correctness of the solution whenever i come across such solutions. Also would be good if someone can throw some light on what other kinds of problems they have seen which are difficult(time complexity wise) but using XOR gives an elegant and time efficient solution. --Navneet -- 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: Search node in a binary tree
There is no reason to use recursion to search a binary tree. Don On Jul 12, 8:28 am, anonymous procrastination opamp1...@gmail.com wrote: Hello, Suppose you have to search a particular node in a binary tree. The code is quite simple. Pick up any traversal and see if any node matches the value. Doubt I have is that how to pull out of the recursive function at the instant node is found. In iterative algos we use a break. Here I can use a global flag variable. But any other bettr way of doing this? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Search node in a binary tree
// Similar to other suggestions, but without tail recursion.
ptr search(ptr root, int value)
{
ptr result = 0;
while(root !result)
{
result = (root-tag == value) ? root : search(root-left,
value);
root = root-right;
}
return result;
}
On Jul 12, 8:28 am, anonymous procrastination opamp1...@gmail.com
wrote:
Hello,
Suppose you have to search a particular node in a binary tree.
The code is quite simple. Pick up any traversal and see if any node
matches the value.
Doubt I have is that how to pull out of the recursive function at the
instant node is found.
In iterative algos we use a break.
Here I can use a global flag variable. But any other bettr way of
doing this?
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: swapping values in C
Undefined code can do whatever it wants to.
Don
On Jul 12, 3:15 pm, tendua 6fae1ce6347...@gmail.com wrote:
# include stdio.h
void swap(int *a, int *b)
{
*a ^= *b ^= *a ^= *b;
}
int main()
{
int a=45, b= 56;
// a ^= b ^= a ^= b;
swap(a,b);
printf(%d %d,a,b);
}
This code gives output 0, 45
While if we uncomment the line in main function and don't use swap
function, we get correct value. Explain why the same line when used in
swap function gives such output.
--
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: swapping values in C
To make it into valid code, break it into three operations:
void swap(int *a, int *b)
{
*a ^= *b;
*b ^= *a;
*a ^= *b;
}
On Jul 12, 3:25 pm, Dave dave_and_da...@juno.com wrote:
@Tendua: The statement *a ^= *b ^= *a ^= *b violates the sequence
point rule, which says that results are undefined if a variable is
assigned more than one value between sequence points.
Dave
On Jul 12, 3:15 pm, tendua 6fae1ce6347...@gmail.com wrote:
# include stdio.h
void swap(int *a, int *b)
{
*a ^= *b ^= *a ^= *b;
}
int main()
{
int a=45, b= 56;
// a ^= b ^= a ^= b;
swap(a,b);
printf(%d %d,a,b);
}
This code gives output 0, 45
While if we uncomment the line in main function and don't use swap
function, we get correct value. Explain why the same line when used in
swap function gives such output.
--
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: questions related to C
To check for overflow, use condition: if (b (maxuint-a)) return error; Where maxuint is the largest value which can be stored in an unsigned integer. Don On Jul 8, 5:50 am, vikas mehta...@gmail.com wrote: Q1 - write a generic macro to swap two values (int,float,double,pointers as well ) Q2 - Implement your own malloc() and free() function Q3 - Two unsigned ints given a, b you have add these numbers and return the sum ...Make sure in case of overflow return error. -- 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] Poison River
A group of N people start off on one side of a poison river. They have a pair of magic shoes which allow their feet to touch the river without killing them. They can not jump across the river or throw the shoes across the river. Each person must use the shoes exactly once to cross the river. How can the entire group get across the river? For N=3, if the people are named A,B, and C: A wears the shoes and carries B across the river. B wears the shoes to go back across the river. C wears the shoes to carry B across the river. Each person used the shoes once, and all three people ended up on the other side of the river. How can the conditions be met for N=4? N=6? N=7? Don -- 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: Hashing with strings
A string hash function typically takes a string as an argument and returns an integer which can be used as an index into a hash table which allows it to be found quickly. The purpose is to relate a string to something else in an efficient way. For instance, a symbol table which stores variable names and needs to quickly find the type and the value (or the address of the value) could use a hash table to avoid having to search through the whole table. There are many theories on the best hash functions for hashing strings. While two different strings may produce the same hash index, a good hash function should produce a reasonably uniform distribution of results, and should produce different results for similar strings. Any hashing method needs to deal with collisions or how to handle the case where two strings are hashed to the same index. Some schemes use a linked list or binary tree withing the hash bucket, and some use a rehash which stores one of the strings somewhere else. If a hash table becomes too full, it can become much less efficient, particularly if the method of resolving collisions is not well designed. Don On Jul 26, 7:49 am, syl abeygau...@gmail.com wrote: can anyone please tell me how to do hashing with strings..just wanna confirm...and most importantly what is the use of it...i have never used it -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Poison River
No, it might be possible for one person to carry two people. On Jul 26, 12:38 am, sunny agrawal sunny816.i...@gmail.com wrote: For N=3, if the people are named A,B, and C: A wears the shoes and carries B across the river. is there any condition that one can carry only one with him? On Tue, Jul 26, 2011 at 10:02 AM, Someshwar Chandrasekaran somseka...@gmail.com wrote: On Tue, Jul 26, 2011 at 3:19 AM, Don dondod...@gmail.com wrote: How can the conditions be met for N=4? N=6? N=7? I believe this question cannot be solved for any values other than three. The condition of wearing it only once makes it tricky. Regards, B.C.Someshwar -- 'Talk sense to a fool and he calls you foolish.' - Euripides My Blog: somsekaran.wordpress.com -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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.
[algogeeks] Re: Poison River
It is a *pair* of shoes, after all. Don On Jul 26, 2:16 am, subashree sridhar subashreesrid...@gmail.com wrote: i think this problem can be solved easily for any no of ppl if they are crossin the river using one shoe at a time :D :P On Jul 26, 10:38 am, sunny agrawal sunny816.i...@gmail.com wrote: For N=3, if the people are named A,B, and C: A wears the shoes and carries B across the river. is there any condition that one can carry only one with him? On Tue, Jul 26, 2011 at 10:02 AM, Someshwar Chandrasekaran somseka...@gmail.com wrote: On Tue, Jul 26, 2011 at 3:19 AM, Don dondod...@gmail.com wrote: How can the conditions be met for N=4? N=6? N=7? I believe this question cannot be solved for any values other than three. The condition of wearing it only once makes it tricky. Regards, B.C.Someshwar -- 'Talk sense to a fool and he calls you foolish.' - Euripides My Blog: somsekaran.wordpress.com -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Sunny Aggrawal B-Tech IV year,CSI Indian Institute Of Technology,Roorkee- Hide quoted text - - Show quoted text - -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Hashing with strings
Usually a hash function is one-way, meaning that you can't recover the
original string. That is because there are many more possible values
for the string than for the hash index, making the hash function a
many-to-one relationship.
A very common hash function which I believe was mentioned in Knuth was
int hash(char *string)
{
int result = 0;
for(int i = 0; string[i]; ++i)
result = 61*result + string[i];
return result;
}
The result would then be used modulus the table size.
Here is one use for hashing:
If you want to find duplicated words in a large file, you could build
a hash table with words you have encountered in the file. Each time
you encounter a word, you would first search for it to determine if it
is already in the table. If so, you would increment its counter.
Otherwise, you would add it and set the counter to one. Then, when you
are done processing the file, any entries with a counter value of more
than one would be duplicated words. This would be far faster than
searching clear through the file for each word.
Don
On Jul 26, 8:13 am, syl abeygau...@gmail.com wrote:
thanks for the info...i saw a method of using 4 bytes of string
together and then add them and finally take a modulusdoing such a
complex thing ...is thr any way to recover the string back using the
key only.can you give an example where you have seen using hashing
with strings...that would clarify my doubt to more extent...
On Jul 26, 6:07 pm, Don dondod...@gmail.com wrote:
A string hash function typically takes a string as an argument and
returns an integer which can be used as an index into a hash table
which allows it to be found quickly. The purpose is to relate a string
to something else in an efficient way. For instance, a symbol table
which stores variable names and needs to quickly find the type and the
value (or the address of the value) could use a hash table to avoid
having to search through the whole table. There are many theories on
the best hash functions for hashing strings. While two different
strings may produce the same hash index, a good hash function should
produce a reasonably uniform distribution of results, and should
produce different results for similar strings. Any hashing method
needs to deal with collisions or how to handle the case where two
strings are hashed to the same index. Some schemes use a linked list
or binary tree withing the hash bucket, and some use a rehash which
stores one of the strings somewhere else. If a hash table becomes too
full, it can become much less efficient, particularly if the method of
resolving collisions is not well designed.
Don
On Jul 26, 7:49 am, syl abeygau...@gmail.com wrote:
can anyone please tell me how to do hashing with strings..just
wanna confirm...and most importantly what is the use of it...i have
never used it
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: size of self referential structure
A reasonable guess would be 28 bytes. But the size of a structure is
implementation dependent, and therefore, some other result could be
correct as well.
Don
On Jul 26, 7:40 am, Puneet Gautam puneet.nsi...@gmail.com wrote:
#includestdio.h
#includestddef.h
struct node{
int a;
char *b[5];
struct node *link;
};
main()
{
int a;
a=sizeof(struct node);
printf(%d,a);
getchar();
return 0;
}
Whats the output..?
--
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: plz give some efficient method to find out if a point lies inside or outside the triangle?
A point is inside a triangle iff: for each pair of vertices of the triangle, the point is on the same side of the line defined by those points as the third vertex of the triangle. Don On Jul 28, 1:47 pm, tech rascal techrascal...@gmail.com wrote: -- 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: plz give some efficient method to find out if a point lies inside or outside the triangle?
// True if point (x,y) is above line defined by two points
// If line is vertical, above is defined as to the right
bool above(double lx1, double ly1, double lx2, double ly2, double x,
double y)
{
return (lx1 != lx2) ? (y (ly1+(x-lx1)*(ly2-ly1)/(lx2-lx1))) : (x
lx1);
}
// True if point 1 and point 2 are on the same side of the line
defined by l1 and l2
bool sameSide(double lx1, double ly1, double lx2, double ly2, double
px1, double py1, double px2, double py2)
{
return above(lx1, ly1, lx2, ly2, px1, py1) == above(lx1, ly1, lx2,
ly2, px2, py2);
}
// True if point (x,y) is inside triangle
bool pointInTriangle(double x1, double y1, double x2, double y2,
double x3, double y3, double x, double y)
{
return sameSide(x1,y1,x2,y2,x,y,x3,y3)
sameSide(x1,y1,x3,y3,x,y,x2,y2)
sameSide(x2,y2,x3,y3,x,y,x1,y1);
}
--
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
If you fill the upper 5x5 submatrix in any way, the two conditions can be met by setting the last element of each row to the product of the first five elements of that row, and likewise with the columns. The lower right element can be formed using either the product of the last column or last row. They are certain to be the same because either one is the product of all 25 elements of the upper submatrix. So the question comes down to this: How many ways can you fill the upper 5x5 submatrix? As others have said, the answer is 2^((n-1)^2) or 33,545,432. Don On Jul 27, 11:57 pm, vetri natarajananitha...@gmail.com wrote: given a 6x6 matrix with all the elements as either 1 or -1. find the number of ways the elements can b arranged such that 1.the product of all elements of all columns is 1 2.the product of all elements of all rows is 1 can u pls post the answer if u no... -- 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: plz give some efficient method to find out if a point lies inside or outside the triangle?
That should work, but I'd bet that my method is faster.
Don
On Jul 29, 6:02 am, Udit Gupta uditgupta...@gmail.com wrote:
Join the given point with all the vertices of the triangle and calculate the
area of each of the three sub-triangles thus formed
now compare the area of original triangle with the sum of the area of those
3 triangles
if that comes out to be equal, then the point lies inside
otherwise not.
On Fri, Jul 29, 2011 at 1:34 AM, Don dondod...@gmail.com wrote:
// True if point (x,y) is above line defined by two points
// If line is vertical, above is defined as to the right
bool above(double lx1, double ly1, double lx2, double ly2, double x,
double y)
{
return (lx1 != lx2) ? (y (ly1+(x-lx1)*(ly2-ly1)/(lx2-lx1))) : (x
lx1);
}
// True if point 1 and point 2 are on the same side of the line
defined by l1 and l2
bool sameSide(double lx1, double ly1, double lx2, double ly2, double
px1, double py1, double px2, double py2)
{
return above(lx1, ly1, lx2, ly2, px1, py1) == above(lx1, ly1, lx2,
ly2, px2, py2);
}
// True if point (x,y) is inside triangle
bool pointInTriangle(double x1, double y1, double x2, double y2,
double x3, double y3, double x, double y)
{
return sameSide(x1,y1,x2,y2,x,y,x3,y3)
sameSide(x1,y1,x3,y3,x,y,x2,y2)
sameSide(x2,y2,x3,y3,x,y,x1,y1);
}
--
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: plz give some efficient method to find out if a point lies inside or outside the triangle?
You just need some comparison which determines if they are very close
to equal. You can't expect them to be exactly equal in all 64 bits.
Something like this should be fine:
bool isClose(double a, double b)
{
const double epsilon = 1.001;
return (a b*epsilon) (b a*epsilon);
}
(Note that this assumes positive values.)
Don
On Jul 29, 1:21 pm, prashant bhutani prashantbhutani2...@gmail.com
wrote:
Yeah, the comparison of two floats will be a problem as the behaviour is
undefined and depends on the machine architecture and compiler.
Thanks Regards,
Prashant Bhutani
Senior Undergraduate
Computer Science Engineering (B.Tech)
Institute of Technology - BHU (IT-BHU)
Varanasi-221005
On Fri, Jul 29, 2011 at 11:43 PM, tech rascal techrascal...@gmail.comwrote:
area of 3 triangles being formed by joining the point to 3 vertices can be
float n when we add the 3 areas, the sum wud also be float. and this is to b
compared with original area
don't u think the problem wud arise in comparing the floats?
wud that give right ans??
On Fri, Jul 29, 2011 at 9:06 PM, Don dondod...@gmail.com wrote:
That should work, but I'd bet that my method is faster.
Don
On Jul 29, 6:02 am, Udit Gupta uditgupta...@gmail.com wrote:
Join the given point with all the vertices of the triangle and calculate
the
area of each of the three sub-triangles thus formed
now compare the area of original triangle with the sum of the area of
those
3 triangles
if that comes out to be equal, then the point lies inside
otherwise not.
On Fri, Jul 29, 2011 at 1:34 AM, Don dondod...@gmail.com wrote:
// True if point (x,y) is above line defined by two points
// If line is vertical, above is defined as to the right
bool above(double lx1, double ly1, double lx2, double ly2, double x,
double y)
{
return (lx1 != lx2) ? (y (ly1+(x-lx1)*(ly2-ly1)/(lx2-lx1))) : (x
lx1);
}
// True if point 1 and point 2 are on the same side of the line
defined by l1 and l2
bool sameSide(double lx1, double ly1, double lx2, double ly2, double
px1, double py1, double px2, double py2)
{
return above(lx1, ly1, lx2, ly2, px1, py1) == above(lx1, ly1, lx2,
ly2, px2, py2);
}
// True if point (x,y) is inside triangle
bool pointInTriangle(double x1, double y1, double x2, double y2,
double x3, double y3, double x, double y)
{
return sameSide(x1,y1,x2,y2,x,y,x3,y3)
sameSide(x1,y1,x3,y3,x,y,x2,y2)
sameSide(x2,y2,x3,y3,x,y,x1,y1);
}
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: random generation
That's actually a big question, because computers are deterministic,
so it is hard to see how they could act randomly.
There are all sorts of pseudo-random generators which will produce a
stream of output which appear more or less random. The larger and more
sophisticated ones produce much better results than the poorly
designed ones. Decades ago there was a random generator called randu
which was notoriously bad, but before people figured out how flawed it
was, hundreds of simulation studies had been performed with it, and
most ended up being rejected as invalid based on the poor statistical
qualities of randu.
Today there are several high-quality generators, such as the Mersenne
Twister. George Marsaglia has designed several excellent generators,
as well as the Diehard battery of tests to measure the statistical
quality of any generator.
However, you seem to be wanting a single number which will be
different each time you run a program.
You could do something as simple as
int random_value = 2 + (time() % 9);
Or you could pick any well-known random generator, seed it, and use it
to produce what you need.
To get you started, this function will produce a pseudo-random stream
of output in the range 0..65535 using Marsaglia's multiply with
carry algorithm.
unsigned int mwc()
{
static unsigned int x = time(0);
x = 63663 * (x65535) + (x16);
return x65535;
}
Don
On Jul 31, 4:39 am, Puneet Gautam puneet.nsi...@gmail.com wrote:
Can we write a code to generate random numbers without using rand function..?
Pls help me 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 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: random generation
Years ago I wrote a Yahtzee program which used feedback from user mouse movements to add entropy to the random generator. Using Borland Builder (Visual Studio could do the same thing) I created an event OnMouseMove which is called any time the mouse moves from one pixel to another. It provides the X and Y coordinates for the mouse location. I had a pool of 600 dice with 100 of each value (1-6), and when a mouse move event occurred, it used the X and Y locations to pick two dice in the pool and swap them. The user had to move the mouse around to select which dice to keep, to click on the Roll button, etc, so there was lots of input to the OnMouseMove event. It also used a timer which caused an event every 1/1000th of a second, which used a multiply-with-carry generator to select one dice in the pool to swap with another dice. That made sure that all the dice moved around frequently. Then when the user rolled the dice, it picked random locations in the pool and used the value at that location. The result was a truly random, non-deterministic dice roll which would be affected by the slightest difference in the way you moved the mouse in the window, which is something I doubt that most commercially produced Yahtzee programs can claim. Similar things could be done for card games to shuffle the deck. You could have the deck for the next game shuffling while the current game is being played. Don On Jul 31, 4:39 am, Puneet Gautam puneet.nsi...@gmail.com wrote: Can we write a code to generate random numbers without using rand function..? Pls help me 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 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: Algorithm complexity
int main()
{
double n;
printf(Enter n:);
scanf(%lf, n);
while(n 1.0)
n = log(log(n));
return 0;
}
On Aug 3, 9:41 am, Ajai Sathyan ajaisath...@gmail.com wrote:
Can u suggest a program with complexity O( log log n ) ?
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Tug of War
As some have said, this is NP, so for larger values of N it takes a
very long time. For N=20 it runs quite quickly.
// True if some set of strengths from s[n] sum to t
bool divide(unsigned int *s, int n, int t)
{
if (t == 0) return true; // We reached the goal
if (n == 0) return false;// No people left to assign
if (*s t) return false;// Smallest person exceeds goal
if (*s * n t) return false;// Everyone else can not total
to goal
if (divide(s+1,n-1,t)) return true; // Consider not including first
person in line
return divide(s+1,n-1,t-*s); // Consider including first
person in line
}
int main(int argc, char* argv[])
{
const int MAX=50;
int N;
unsigned int strength[MAX];
int sum = 0;
int i,j;
printf(How many people are playing?);
scanf(%d,N);
for(i = 0; i N; ++i)
{
printf(Enter strength of person %d:, i+1);
scanf(%d, strength[i]);
sum += strength[i];
}
if (sum % 2 == 1)
{
printf(NO\n);
}
else
{
// Sort from high to low
for(i = 0; i N; ++i)
for(j = 1; j N; ++j)
{
if (strength[j] strength[j-1])
{
strength[j] ^= strength[j-1];
strength[j-1] ^= strength[j];
strength[j] ^= strength[j-1];
}
}
if (divide(strength+1,N-1,sum/2)) printf(YES\n);
else printf(NO\n);
}
return 0;
}
On Jul 30, 4:44 am, sylvester abeygau...@gmail.com wrote:
input consists of N integers, separated by a space. The ith integer
indicates the strength of the ith person.
For each case, output YES if it is possible to pick some people from
the group and separate into two teams of equal strengths else NO
--
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: Circle
// Draw a circle with center (x,y) and radius r
circle(int x, int y, int r)
{
int a = 0;
int b = r;
while(a = b)
{
// Draw the current location in all 4 quadrants
plot(x+a, y+b);
plot(x-a, y+b);
plot(x+a, y-b);
plot(x-a, y-b);
plot(x+b, y+a);
plot(x-b, y+a);
plot(x+b, y-a);
plot(x-b, y-a);
// Look at two possible next points and pick the better
int delta1 = r*r - (a+1)*(a+1) - b*b;
int delta2 = r*r - a*a - (b-1)*(b-1);
if (delta1*delta1 delta2*delta2) ++a;
else --b;
}
}
On Aug 5, 8:38 am, rShetty rajeevr...@gmail.com wrote:
Write a routine to draw a circle (x ** 2 + y ** 2 = r ** 2) without
making use of any floating point
computations 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
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Probability Puzzle
The answer is 17 in 18, because flipping 5 heads in a row is evidence that the probability is high that we have the coin with two heads. Don On Aug 7, 12:34 pm, Algo Lover algolear...@gmail.com wrote: A bag contains 5 coins. Four of them are fair and one has heads on both sides. You randomly pulled one coin from the bag and tossed it 5 times, heads turned up all five times. What is the probability that you toss next time, heads turns up. (All this time you don't know you were tossing a fair coin or not). -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Probability Puzzle
Consider the 5 * 64 possible outcomes for the selection of coin and six flips, each one happening with equal probability. Of those 320 possible outcomes, 4*62 are excluded by knowing that the first 5 flips are heads. That leaves 64 outcomes with the rigged coin and 2 outcomes with each of the fair coins, for a total of 72 outcomes. 68 of those are heads, so the answer to the puzzle is 68 of 72, or 17 of 18. Don On Aug 8, 2:36 am, Shachindra A C sachindr...@gmail.com wrote: @brijesh *first five times* is mentioned intentionally to mislead i think. I vote for 3/5. Moreover, 17/80 doesn't make sense also. Plz correct me if I am wrong. On Mon, Aug 8, 2011 at 12:06 PM, sumit gaur sumitgau...@gmail.com wrote: (3/5) On Aug 7, 10:34 pm, Algo Lover algolear...@gmail.com wrote: A bag contains 5 coins. Four of them are fair and one has heads on both sides. You randomly pulled one coin from the bag and tossed it 5 times, heads turned up all five times. What is the probability that you toss next time, heads turns up. (All this time you don't know you were tossing a fair coin or not). -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Regards, Shachindra A 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: what is complexity of func(p)
I don't think that this function is doing what you want it to do. If
you ask for a^b, it returns a^1 in most cases.
Try this instead.
int power(int a, int b)
{
int result = 1;
if (b == 1) result = a;
else if (b1)
{
result = power(a,b/2);
result *= result;
if (b%2) result *= a;
}
return result;
}
On Aug 8, 10:37 pm, rohit rajuljain...@gmail.com wrote:
int get_power(int a, int b)
{
if(!b)
return 1;
if(b%2)
return a * get_power(a, b/2);
return get_power(a, b/2);
}
int func(int p)
{ int sum = 0;
for(int i = 1; i = p; ++i)
{
sum += get_power(i, 5);}
return sum;
}
--
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: need a pgm pls help me
#include stdio.h
#include stdlib.h
int main()
{
char inFileName[80];
char outFileName[80];
int numSegments;
int bytesPerSegment;
printf(Enter file name:);
fgets(inFileName,80,stdin);
printf(Enter number of segments:);
scanf(%d, numSegments);
FILE *f = fopen(inFileName, rb);
if (!f) return 0;
// Get size of file to determine bytes per file segment
fseek(f, 0, SEEK_END);
int bytesPerSegment = 1 + (ftell(f) / numSegments);
fseek(f,0,SEEK_SET);
char *buffer = (char *)malloc(bytesPerSegment);
for(int segment = 0; segment numSegments; ++segment)
{
sprintf(outFileName,%s%d, inFileName,segment);
FILE *out = fopen(outFileName,wb);
int len=fread(buffer, bytesPerSegment, 1, f);
fwrite(buffer, len, 1, out);
fclose(out);
}
return 1;
}
On Aug 9, 7:28 am, Divya Elangovan divistyl...@gmail.com wrote:
pls help me..its very urgent
need a program to divide a file into equal parts(segments)
--
*
**
*
* ** **DIVI*
--
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: Closest ancestor of two nodes
tree closestSharedAncestor(tree root, tree node1, tree node2, int
result)
{
tree returnValue = 0;
if (root)
{
if (root == node1) result += 1;
if (root == node2) result += 2;
int sum = 0;
tree returnLeft = closestSharedAncestor(root-left, node1, node2,
sum);
if (returnLeft) returnValuet = returnLeft;
else
{
tree returnRight = closestSharedAncestor(root-right, node1,
node2, sum);
if (returnRight) returnValue = returnRight;
else if (sum == 3) returnValue = root;
}
result += sum;
}
return returnValue;
}
On Aug 9, 9:56 am, Raman raman.u...@gmail.com wrote:
Can anyone give me the recursive algo to find closest ancestor of two nodes
in a tree(not a BST).
--
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: suggest simple code for
int depth(node *root)
{
return root ? max(depth(root-left), depth(root-right)) : 0;
}
On Aug 8, 8:03 am, jagrati verma jagrativermamn...@gmail.com wrote:
finding the depth or height of a 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
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: suggest simple code for
int depth(node *root)
{
return root ? 1+max(depth(root-left), depth(root-right)) : 0;
}
On Aug 8, 8:03 am, jagrati verma jagrativermamn...@gmail.com wrote:
finding the depth or height of a 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
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: suggest simple code for
I do love functions that start with return.
Don
On Aug 10, 10:09 am, Dave dave_and_da...@juno.com wrote:
@Don: Beautiful!
Dave
On Aug 10, 10:03 am, Don dondod...@gmail.com wrote:
int depth(node *root)
{
return root ? 1+max(depth(root-left), depth(root-right)) : 0;
}
On Aug 8, 8:03 am, jagrati verma jagrativermamn...@gmail.com wrote:
finding the depth or height of a 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
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Problems on Linked List
Q1: The function below reverses a linked list in place. Call it on one
of the lists, compare the resulting list to the other list. Then call
it again to put the list back in its original order.
list Reverse(list head)
{
list T, prv, nxt;
prv = head;
for(T = head-next; T; T = nxt)
{
nxt = T-next;
T-next = prv;
prv = T;
T = nxt;
}
head-next = 0;
return prv;
}
Q2:
delete(node *d)
{
if (d-next)
{
node nxt = d-next;
d-value = nxt-value;
d-next = nxt-next;
free nxt;
}
else
{
for(node p = head; p; p = p-next)
if (p-next == d)
{
p-next = 0;
free d;
}
}
}
On Aug 10, 1:14 pm, Piyush Kapoor pkjee2...@gmail.com wrote:
Q1)Two linked Lists are given,i.e,their head pointers are given,and the
problem is to check if the second one is reverse of the first one.Give the
most efficient algo for it.
Q2)A linked list is given,and one of its nodes is given.The problem is to
delete the given node from the linked list.(The head node is not given).
(In both of the above cases,the linked lists are singly linked lists.)
--
*Regards,*
*Piyush Kapoor,*
*2nd year,CSE
IT-BHU*
--
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: Design a concurrent hash table
Sounds like you need some sort of semaphore system to lock cells in the hash table. Essentially it would only give one user access to a particular cell at any given time. Make sure that the cells have a restricted interface so that they can only be accessed through the semaphore-controlled interface. The write interface would attempt to get the semaphore, and if successful, write the data and then release the semaphore. If it failed, it would return a failure notice to the caller. The read interface would check the semaphore and if it was open, get the data. Don On Aug 11, 5:15 am, Navneet Gupta navneetn...@gmail.com wrote: Q. Design a concurrent hash table with as much as concurrency as possible. System has multiple readers and writers. System will crash if a reader or writer is reading or writing from a location which is being updated by some writer. We need to prevent crash. It is pretty much an open-ended question, so basically looking for strategies. -- Regards, Navneet -- 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: Jumping Puzzle
int A[100];
int dist[100];
int N;
void findDist(int p, int d)
{
if (d dist[p])
{
dist[p] = d;
for(int i = 0; i p; ++i)
if ((i+A[i]) = p)
findDist(i,d+1);
}
}
int main(int argc, char* argv[])
{
int i;
int location = 0;
printf(Number of elements:);
scanf(%d, N);
for(i = 0; i N; ++i)
{
printf(Element %d:, i);
scanf(%d,A[i]);
}
for(i = 0; i N; ++i)
dist[i] = N;
findDist(N-1, 0);
for(i = 1; i N; ++i)
if (dist[i] == (dist[location]-1))
{
printf(Move %d to location %d\n, i-location, i);
location = i;
}
return 0;
}
On Aug 11, 3:07 am, Algo Lover algolear...@gmail.com wrote:
Given an array, start from the first element and reach the last by
jumping. The jump length can be at most the value at the current
position in the array. Optimum result is when you reach the goal in
minimum number of jumps.
For ex:
Given array A = {2,3,1,1,4}
possible ways to reach the end (index list)
i) 0,2,3,4 (jump 2 to index 2, then jump 1 to index 3 then 1 to index
4)
ii) 0,1,4 (jump 1 to index 1, then jump 3 to index 4)
Since second solution has only 2 jumps it is the optimum result.
My solution is for any index i loop from i to i + A[i]
find an index j where
(j + A[j]) is maximum for all j.
make i=j;
This solution in O(n) i suppose coz we are picking each element twice
in the worst case.
I have read a O(n^2) DP solution for this problem.Is there any
case where my approach will fail ?
--
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: reverse
What exactly do you mean by reverse a number? Please define what that means and give an example. Don On Aug 11, 12:13 pm, Rajeshwar Patra rajeshwarpa...@gmail.com wrote: how can we reverse a number using bitwise operators? -- *Rajeshwar Patra,* *MCA final year,* *Nit Durgapur* -- 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: Math Quiz
2 On Aug 11, 1:26 pm, Mani Bharathi manibharat...@gmail.com wrote: ABCD is a parallelogram and E is the middle point of side AD EC meets BD at O. If the area if the parallelogram is 24 units then the area of EOD is ? -- 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: Hash
Yes. Linear probing, if done in the usual way, will end up at 2 if the hash function returned values 1,2,7,8, 9, or 10. That is 6 of the 10 possible values, so if each one is equally likely, the probability is 0.6. Don On Aug 11, 3:04 pm, aditi garg aditi.garg.6...@gmail.com wrote: cud u xplain how? On Thu, Aug 11, 2011 at 11:31 PM, Tarun Arya tarun@gmail.com wrote: Rajeev sir, 0.6 is 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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Aditi Garg Undergraduate Student Electronics Communication Divison NETAJI SUBHAS INSTITUTE OF TECHNOLOGY Sector 3, Dwarka New Delhi -- 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: Non recursive preorder and postorder
It can be done without using a stack, by using the pointers in the node to keep track of the path back up the tree. The algorithm will temporarily modify the tree, but when completed the tree will be restored to its original state. Don On Aug 15, 8:07 am, rohit raman.u...@gmail.com wrote: Can anyone give algorithm for non recursive preorder and postorder?? -- 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: program puzzle
#include ctype.h
#include string.h
int main(int argc, char* argv[])
{
char line[500];
char tmp[500];
char *words[100];
int wordCount = 0;
char *p, *wordStart=0;
printf(Enter string:);
fgets(line,500,stdin);
for(p = line; *p; ++p)
{
if (!wordStart isalpha(*p)) wordStart = p;
else if (wordStart !isalpha(*p))
{
words[wordCount++] = wordStart;
*p = 0;
wordStart = 0;
}
}
p = tmp;
for(int i = wordCount-1; i = 0; --i) p += sprintf(p, %s ,
words[i]);
strcpy(line,tmp);
printf(%s\n, line);
return 0;
}
On Aug 15, 6:18 am, programming love love.for.programm...@gmail.com
wrote:
write a program to reverse the words in a give string.
also state the time complexity of the algo.
if the string is i am a programmer
the output should be programmer a am 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
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Prime numbers
I wrote a program to print prime numbers, but it is not very fast. Can
someone help me figure out why?
#include stdio.h
/* This program implements a blindingly fast algorithm
to find prime numbers, using an elegant recursive method. */
int _(int n, int m, int d, int t=0)
{
int r;
if (t) return d?1+_(n,m,d-1,d):n?_(n-1,m,m,n):0;
for(r=m!=n; d*(tn); ++t)
r = _(n,_(t,m,0,1),d-1)|!_(t,1,t);
return r*n;
}
/*--
Print primes up to the requested value
*/
int main(int argc, char* argv[])
{
for(int n = 2; n = 1000; n++)
printf(%d is%s prime\n,n, _(n,1,n,0)?: not);
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
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Prime numbers
I wrote it. Can you figure out how it works?
Don
On Aug 17, 1:25 am, Nitin Nizhawan nitin.nizha...@gmail.com wrote:
Hi Dod,
Could you pls expalin what this algorithm is doing and from where you got
it.
Thanks
Nitin
On Wed, Aug 17, 2011 at 2:56 AM, Don dondod...@gmail.com wrote:
I wrote a program to print prime numbers, but it is not very fast. Can
someone help me figure out why?
#include stdio.h
/* This program implements a blindingly fast algorithm
to find prime numbers, using an elegant recursive method. */
int _(int n, int m, int d, int t=0)
{
int r;
if (t) return d?1+_(n,m,d-1,d):n?_(n-1,m,m,n):0;
for(r=m!=n; d*(tn); ++t)
r = _(n,_(t,m,0,1),d-1)|!_(t,1,t);
return r*n;
}
/*--
Print primes up to the requested value
*/
int main(int argc, char* argv[])
{
for(int n = 2; n = 1000; n++)
printf(%d is%s prime\n,n, _(n,1,n,0)?: not);
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
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: Prime numbers
_(n,1,n,0) is true if n is prime. I set out to create an O(n^n) algorithm. It essentially computes the product of every possible set of n integers in the range (1..n-1). If any of those products equal n, the number is composite. You will notice that the program does not use the * operator to perform a multiplication. It does use * as a logical AND, but to do the products it uses a recursive call with t=1, which is a flag to tell _ to do multiplication instead of determining if n is prime. It does the multiplication by recursively adding up m*n ones. As a result, it takes billions of recursive calls to determine that 6 is not prime. Don On Aug 17, 10:33 am, Sanjay Rajpal srn...@gmail.com wrote: @Don : can you plz explain it ? Sanjay Kumar B.Tech Final Year Department of Computer Engineering National Institute of Technology Kurukshetra Kurukshetra - 136119 Haryana, India -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: an amazing amazon question!
Actually you are all wrong. His uniform speed was zero, and he was sitting by milestone 44 the whole time. On Aug 17, 11:58 am, priya ramesh love.for.programm...@gmail.com wrote: A car is traveling at a uniform speed.The driver sees a milestone showing a 2-digit number. After traveling for an hour the driver sees another milestone with the same digits in reverse order.After another hour the driver sees another milestone containing the same two digits. What is the average speed of the driver? -- 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: brain teaser
We know that n+m+s+carry 10. So n7. We also know that either n+n+n or o+o+o 9 because there must be a carry to make those two columns add to a different value. We can start eliminating values for n. If n is 1, o would have to be 7 to make the second row work out. But then u and e would both be 3. If n is 3, o must be 1, so u would also be 3. If n is 4, o must be 1 and u must be 3, which makes n+m+s 9. If n=5, then e would be 5, so n can't be 5. If n is larger than 5, there is no combination which makes n+m+s10. That leaves n=2. It follows that e=6, o=4, and u=3. m and s are interchangeable: 1 and 5. And j is 9. 2442+1442+5442=9326 Don On Aug 17, 1:23 pm, priya ramesh love.for.programm...@gmail.com wrote: noon + moon + soon = june find the values of the alphabets to satisfy this equation -- 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: apti! solve this!
Are we assuming a flat earth? On Aug 17, 9:13 am, priya ramesh love.for.programm...@gmail.com wrote: A moves 3 kms east from his starting point . He then travels 5 kms north. From that point he moves 8 kms to the east.How far is A from his starting point? -- 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: Need to Hire an algorithm expert for a one time assignment
Why not post your questions, one per thread, and let people discuss it? Don On Aug 18, 7:41 am, maxpayne aquarian.thun...@gmail.com wrote: Hi, I need help from some one who is really good at algorithms to finish an assignment. I am a freelancer (not a student, so don't expect homework problems) based in Singapore and unfortunately I do not have a back ground in algorithms. I will really appreciate it if some one in this group can spare an hour or so to give me some expert advice. The problems will be more along the lines of those asked in popular coding competitions (think TopCoder, ACM, Project Euler etc). Kindly write back to me at aquarian.thun...@gmail.com (for details) if you are interested and can spare an hour or so. thanks, Max -- 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: knight's tour - variant
1.0. A knight's only legal move is to remain on the board. On Aug 17, 10:27 am, Seshumadhav Chaturvedula seshumad...@gmail.com wrote: what is the probability that a knight will stay on a K X K chess board after 'n' steps ? -- 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: calculate a/b without using ‘*’, ‘/’’ and ‘%’
exp(ln(a)-ln(b)) On Aug 18, 8:56 am, radha krishnan radhakrishnance...@gmail.com wrote: how to do using BIT manipulation ? -- 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: question on fork()
// DO NOT RUN THIS! By inspection, how many times will it print Hello
world?
// If you find out by running it, that is cheating. Don't do it!
int main()
{
int i=0, j=0;
for(i = 0; i*j 20; ++i)
{
if (fork() 0) ++j;
else i = j = 0;
printf(Hello world\n);
}
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
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
