[algogeeks] Re: Generate a number
can u give example? is it like that for 3 , a no which is made of 1st ,2nd and 3rd digit should be divisible by 3 or individual all three digits must be divisible by 3? A 2nd case seems impossible. On Jul 30, 9:12 am, Shiv ... shivsinha2...@gmail.com wrote: If space is not a restriction- Build a B-tree. 1. Have a dummy root. 2. At level one- Numbers divisible by 1. ie. (1-9). 3. At level 2- numbers made after adding a digit to numbers at level 1. e.g. number 7 at level will have children- (70,72,74,76,78). and so on.. 4. Do the same at each level. Leaf nodes at level 10 will be your answers. I think math can optimize this a bit- though. On Thu, Jul 29, 2010 at 9:57 PM, amit amitjaspal...@gmail.com wrote: An algorithm to print all the 10-digit nos such that first 1 digit is divisible by 1, first 2 digits by 2, first 3 digits by 3 and so on...first 9 digits by 9. I think the tenth digit can be anything from 0 to 9. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Amazon question
Consider there are N players who have a round robin tournament. input is a data structure which says who won the match for every pair i , j i != j . write an algo to give a sequence A[1...n] such that for ever i , i th player lost to i+1 th player and won against i-1 th player. -- Regards, Ramkumar.G -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] number of BST's
int num_of_BST(int n)
{
int sum=0;
int left,right,root;
if(n=1)
return 1;
else
{
for(root=1;root=n;root++)
{
left=num_of_BST(root-1);
right=num_of_BST(n-root);
sum+=left*right;
}
}
return sum;
}
On Thu, Jul 29, 2010 at 9:56 PM, amit amitjaspal...@gmail.com wrote:
Given the numbers from 1 to n, write an algorithm to find how many
distinct binary search trees can be formed.. eg n=4, no of distinct
bst's are 14. ??
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] number of BST's
The question is to find the no of structures possible for a BST which is directly given bycomputing the catalan number for n(no of nodes) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Amazon Placement Question
@Anand, you are partly correct, thanks for modifying my code
On 31 July 2010 00:01, Anand anandut2...@gmail.com wrote:
I highlighted the code which I feel need a change. Do let me know if it
correct.
LinkNode *levelOrderTraversal(node *root, int level)
{
LinkNode *ptr1, *ptr2, temp;
if(root == NULL)
return NULL;
if(level == 1)
return createLinkNode(root);
else
{
ptr1 = levelOrderTraversal(root-left, level-1);
ptr2 = levelOrderTraversal(root-right, level-1);
if(ptr1 == NULL ptr2 == NULL)
return NULL;
else if(ptr1 == NULL) // why do you need else if constructs??? i used
return statement after each if
return ptr2;
else if(ptr2 == NULL)
return ptr1;
else
{
* temp = ptr1;
while(ptr1-next)
ptr1= ptr1-next;
ptr1-next = ptr2;
*
/* this is significant modification, i missed it in my code*/
*
return temp;* (Will always return the head of the linked list to
store it in the array)
}
}
}
On Fri, Jul 30, 2010 at 8:18 AM, vineel yalamarth
vineelyalamar...@gmail.com wrote:
Dude, yeah I got the algo, but can u write java code for that
On Fri, Jul 30, 2010 at 6:03 PM, karthik ramanathan
nathankart...@gmail.com wrote:
Do a BFS, by having a queue and keep inserting the nodes into it.
You should know how many nodes are there in each level, for which you can
have a variable to count the number of nodes in each level.
The when you remove from your queue do connect these nodes till your
count. You may need to use one more temp variable to not to lose the
previous level node count when you compute the next level node count.
Repeat the same for all the level.
RK
On Fri, Jul 30, 2010 at 11:21 AM, Amit Agarwal lifea...@gmail.comwrote:
A simple queue implementation will do.
-Regards
Amit Agarwal
blog.amitagrwal.com
On Fri, Jul 30, 2010 at 9:22 AM, Priyanka Chatterjee
dona.1...@gmail.com wrote:
On 30 July 2010 02:59, Priyanka Chatterjee dona.1...@gmail.comwrote:
Algo: 1. find height of tree
2. do level order traversal
i at each level store the address of each tree node in
the data part of a linked node and form linked list of the nodes
ii store the header of a linked list at a certain level
in an array
3. return array.// gives final structure
complexity - T(n) =O(n)
S(n)=O(h+n ) //h=height of tree
//CODE
//tree structure
struct node {
int data;
struct node * left, *right};
// linked list structure
struct linkNode{
struct node * data;
struct linkNode * next;
}
struct linkNode** func(struct node * root){
struct linkNode ** array;
int i, h=height(root);
for(i=1;i=h;i++)
array[i-1]=levelOrderTraversal(root, i);
return array;// final tree structure
}
//max height of tree
int height(struct node *root){
int hL=height(root-left);
int hR=height(root-right);
return 1+ HRHL?HR:HL;
}
struct nodelink* levelOrderTraversal(struct node*root, int level){
if(root==NULL) return NULL;
if (level==1)
return createLinkNode(root); // create a node of a singly l
struct LinkNode *ptr;
if(level1){
struct nodeLink * ptr1, *ptr2;
ptr1=levelOrderTraversal(root-left,level-1);
ptr2=levelOrderTraversal(root-right,level-1);
if(ptr1==NULL ptr2==NULL) return NULL;
if(ptr1==NULL) return ptr2;
if(ptr2==NULL) return ptr1;
ptr1-next=ptr2;
return ptr2;
}
}
struct linkNode * createLinkNode(struct node * root){
struct linkNode* newNode=(struct linkNode*) malloc(sizeof(struct
linkNode));
newNode-data=root;
newNode-next=NULL;
}
--
Thanks Regards,
Priyanka Chatterjee
Final Year Undergraduate Student,
Computer Science Engineering,
National Institute Of Technology,Durgapur
India
http://priyanka-nit.blogspot.com/
--
Thanks Regards,
Priyanka Chatterjee
Final Year Undergraduate Student,
Computer Science Engineering,
National Institute Of Technology,Durgapur
India
http://priyanka-nit.blogspot.com/
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to
[algogeeks] Complexity of Algorithms [√n and log ( n^2)]
f(n) = sqrt(n) [squate root of n] g(n) = log(^2) [log of (n square)] For the above pair of functions is f(n) = Ω(g(n))? i.e., is there some c 0, such that f(n) = g(n) for all n? Give proof in case answer is yes or no. --- Note: f(n) = O(g(n)) is proved as below. Need to find if f(n) = Ω(g(n) also. Let a = √(n), then log a = 1/2(log n) As logarithm of a number is smaller than the number, we have a log a = √n 1/2(log n) = √n 2/4(log n) = √n 1/2(log n^2) Hence √n is log (n^2) for c = 1/4 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: number of BST's
int countTree(int num)
{
if(num = 1) return 1;
int sum =0;
for(i =1; inum; ++i)
{
left = countTree(i-1);
right = countTree(num - i);
sum += left*right;
}
return sum;
}
The code snippet is self explanatory. Let me know if any difficulty.
On Jul 30, 11:28 am, Pramod Negi negi.1...@gmail.com wrote:
Follow up on Catalon Nubmer...
On Fri, Jul 30, 2010 at 10:44 AM, Amit Jaspal amitjaspal...@gmail.comwrote:
n is clearly a number lets say 3 then BST's with 1,2,3 values as key are to
be calculated
On Fri, Jul 30, 2010 at 9:08 AM, Apoorve Mohan
apoorvemo...@gmail.comwrote:
@AMIT: what does n represents?
On Fri, Jul 30, 2010 at 5:46 AM, sharad kumar
aryansmit3...@gmail.comwrote:
@amit is it BST or binary tree??cos BST is unique rite???binary tree meas
use catalan numbers 2nCn/(n+1)!
On Thu, Jul 29, 2010 at 9:56 PM, amit amitjaspal...@gmail.com wrote:
Given the numbers from 1 to n, write an algorithm to find how many
distinct binary search trees can be formed.. eg n=4, no of distinct
bst's are 14. ??
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
yezhu malai vaasa venkataramana Govinda Govinda
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
regards
Apoorve Mohan
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Amit Jaspal
Btech IT 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 algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.- Hide quoted text -
- Show quoted text -
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] number of BST's
is n not the number of nodes? On Fri, Jul 30, 2010 at 11:58 AM, Pramod Negi negi.1...@gmail.com wrote: Follow up on Catalon Nubmer... On Fri, Jul 30, 2010 at 10:44 AM, Amit Jaspal amitjaspal...@gmail.comwrote: n is clearly a number lets say 3 then BST's with 1,2,3 values as key are to be calculated On Fri, Jul 30, 2010 at 9:08 AM, Apoorve Mohan apoorvemo...@gmail.comwrote: @AMIT: what does n represents? On Fri, Jul 30, 2010 at 5:46 AM, sharad kumar aryansmit3...@gmail.comwrote: @amit is it BST or binary tree??cos BST is unique rite???binary tree meas use catalan numbers 2nCn/(n+1)! On Thu, Jul 29, 2010 at 9:56 PM, amit amitjaspal...@gmail.com wrote: Given the numbers from 1 to n, write an algorithm to find how many distinct binary search trees can be formed.. eg n=4, no of distinct bst's are 14. ?? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- yezhu malai vaasa venkataramana Govinda Govinda -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- regards Apoorve Mohan -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Amit Jaspal Btech IT 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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- regards Apoorve Mohan -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] algorithm
given a rand5 function which generates numbers from 1 to 5 with equal probability.. give an algorithm which uses rand5 function and generates numbers from 1 to 7 with equal probability -- With Regards, Jalaj Jaiswal +919026283397 B.TECH IT 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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Amazon question
put all the players in a stack now pop two players from stack insert the winning player in to a circular doubly linked list. now repeat the procedure and while inserting in doubly linked list if the linked list is not null then start from tail and compare the popped node with it that whether it won, if it won then make it the tail if not then move inwards ... i.e insert it before the node it won against. On Sat, Jul 31, 2010 at 3:45 PM, Ram Kumar harrypotter@gmail.comwrote: Consider there are N players who have a round robin tournament. input is a data structure which says who won the match for every pair i , j i != j . write an algo to give a sequence A[1...n] such that for ever i , i th player lost to i+1 th player and won against i-1 th player. -- Regards, Ramkumar.G -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- With Regards, Jalaj Jaiswal +919026283397 B.TECH IT 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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Complexity of Algorithms [√n and l og (n^2)]
A small correction. You need to prove if f(n) = O(g(n)). My Proff (under Note) is for f(n) = Ω(g(n)) On Sat, Jul 31, 2010 at 12:08 AM, sourav souravs...@gmail.com wrote: f(n) = sqrt(n) [squate root of n] g(n) = log(^2) [log of (n square)] For the above pair of functions is f(n) = Ω(g(n))? i.e., is there some c 0, such that f(n) = g(n) for all n? Give proof in case answer is yes or no. --- Note: f(n) = O(g(n)) is proved as below. Need to find if f(n) = Ω(g(n) also. Let a = √(n), then log a = 1/2(log n) As logarithm of a number is smaller than the number, we have a log a = √n 1/2(log n) = √n 2/4(log n) = √n 1/2(log n^2) Hence √n is log (n^2) for c = 1/4 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: number of BST's
the number of unique binary trees which can be formed with n nodes is (2^n)-n -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: algorithm
Use the rejection method...
int rand7()
{
int i;
do
i = 5 * rand5() + rand5() - 3;
while( i 23 );
return i / 3;
}
The loop assigns i a value between 5*1+1-3 = 3 and 5*5+5-3 = 27 with
uniform probability, and then rejects any value of i 23. Thus, after
the loop, i has a uniform distribution on the interval 3 to 23.
Dividing by 3 gives the desired result.
Under the assumptions of the problem, a value of i is rejected with
probability 4/25, so the loop executes an average of 1/(1 - 4/25) =
25/21 times. Therefore, on average, it takes 50/21 rand5's to make a
rand7.
Dave
On Jul 30, 8:33 am, jalaj jaiswal jalaj.jaiswa...@gmail.com wrote:
given a rand5 function which generates numbers from 1 to 5 with equal
probability.. give an algorithm which uses rand5 function and generates
numbers from 1 to 7 with equal probability
--
With Regards,
Jalaj Jaiswal
+919026283397
B.TECH IT
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 algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: algorithm
@Sony. No. Consider the following table:
rand5() (2/3)*rand5()
_
10
21
32
42
53
Thus, (2/3)*rand5() is not uniformly distributed, nor is it in the
range 0 to 2.
Dave
On Jul 31, 7:49 am, Sony Jose sonyj...@gmail.com wrote:
what about
int i = rand5() + (2/3)*rand5();
won't this work?
On Sat, Jul 31, 2010 at 5:46 PM, Dave dave_and_da...@juno.com wrote:
Use the rejection method...
int rand7()
{
int i;
do
i = 5 * rand5() + rand5() - 3;
while( i 23 );
return i / 3;
}
The loop assigns i a value between 5*1+1-3 = 3 and 5*5+5-3 = 27 with
uniform probability, and then rejects any value of i 23. Thus, after
the loop, i has a uniform distribution on the interval 3 to 23.
Dividing by 3 gives the desired result.
Under the assumptions of the problem, a value of i is rejected with
probability 4/25, so the loop executes an average of 1/(1 - 4/25) =
25/21 times. Therefore, on average, it takes 50/21 rand5's to make a
rand7.
Dave
On Jul 30, 8:33 am, jalaj jaiswal jalaj.jaiswa...@gmail.com wrote:
given a rand5 function which generates numbers from 1 to 5 with equal
probability.. give an algorithm which uses rand5 function and generates
numbers from 1 to 7 with equal probability
--
With Regards,
Jalaj Jaiswal
+919026283397
B.TECH IT
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 algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Regards,
Sony- Hide quoted text -
- Show quoted text -
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: algorithm
Hi Dave,
i just checked;
int i;
int j;
for(i=1;i6;i++) {
j = 2*(i/3);
printf(\n%d\n,j);
}
gives me output 0,0,2,2,2. and there was no 3;
and since we are anyway generating random numbers would this difference in
distribution really matter?
On Sat, Jul 31, 2010 at 6:30 PM, Dave dave_and_da...@juno.com wrote:
@Sony. No. Consider the following table:
rand5() (2/3)*rand5()
_
10
21
32
42
53
Thus, (2/3)*rand5() is not uniformly distributed, nor is it in the
range 0 to 2.
Dave
On Jul 31, 7:49 am, Sony Jose sonyj...@gmail.com wrote:
what about
int i = rand5() + (2/3)*rand5();
won't this work?
On Sat, Jul 31, 2010 at 5:46 PM, Dave dave_and_da...@juno.com wrote:
Use the rejection method...
int rand7()
{
int i;
do
i = 5 * rand5() + rand5() - 3;
while( i 23 );
return i / 3;
}
The loop assigns i a value between 5*1+1-3 = 3 and 5*5+5-3 = 27 with
uniform probability, and then rejects any value of i 23. Thus, after
the loop, i has a uniform distribution on the interval 3 to 23.
Dividing by 3 gives the desired result.
Under the assumptions of the problem, a value of i is rejected with
probability 4/25, so the loop executes an average of 1/(1 - 4/25) =
25/21 times. Therefore, on average, it takes 50/21 rand5's to make a
rand7.
Dave
On Jul 30, 8:33 am, jalaj jaiswal jalaj.jaiswa...@gmail.com wrote:
given a rand5 function which generates numbers from 1 to 5 with equal
probability.. give an algorithm which uses rand5 function and
generates
numbers from 1 to 7 with equal probability
--
With Regards,
Jalaj Jaiswal
+919026283397
B.TECH IT
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 algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
algogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Regards,
Sony- Hide quoted text -
- Show quoted text -
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Regards,
Sony
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: number of BST's
catalan number works fine On Sat, Jul 31, 2010 at 4:55 PM, Soumya_Prasad_Ukil ukil.sou...@gmail.comwrote: @above, result is incorrect for n=4. It should print 14. On 31 July 2010 16:44, Manjunath Manohar manjunath.n...@gmail.com wrote: the number of unique binary trees which can be formed with n nodes is (2^n)-n -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- regards, soumya prasad ukil -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- With Regards, Jalaj Jaiswal +919026283397 B.TECH IT 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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: algorithm
why u have chosen that 23 ?
why dividing by 3 ?
don't understand the logic.
Please explain so that it become understandable.
On 7/31/10, Dave dave_and_da...@juno.com wrote:
Use the rejection method...
int rand7()
{
int i;
do
i = 5 * rand5() + rand5() - 3;
while( i 23 );
return i / 3;
}
The loop assigns i a value between 5*1+1-3 = 3 and 5*5+5-3 = 27 with
uniform probability, and then rejects any value of i 23. Thus, after
the loop, i has a uniform distribution on the interval 3 to 23.
Dividing by 3 gives the desired result.
Under the assumptions of the problem, a value of i is rejected with
probability 4/25, so the loop executes an average of 1/(1 - 4/25) =
25/21 times. Therefore, on average, it takes 50/21 rand5's to make a
rand7.
Dave
On Jul 30, 8:33 am, jalaj jaiswal jalaj.jaiswa...@gmail.com wrote:
given a rand5 function which generates numbers from 1 to 5 with equal
probability.. give an algorithm which uses rand5 function and generates
numbers from 1 to 7 with equal probability
--
With Regards,
Jalaj Jaiswal
+919026283397
B.TECH IT
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 algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] minimum window containing charecters
given two string , find the minimum width in string 1 containing the all characters of string 2 , they may present in different order string 1-HELLO string 2- LE answer-2 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: algorithm
@Sony. I took (2/3)*rand5() as if (2/3) was a double. Otherwise,
(2/3)*rand5() = 0*rand5() = 0, which is not what you calculated when
you wrote 2*(i/3) instead of (2/3)*i.
And yes, the fact that the distribution is not uniform does matter,
since we want the results to be uniform. Using your interpretation of
(2/3)*rand5(), to get i = 1, the first rand5() must be 1 and the
second rand5() must be 1 or 2. Thus, the probability of i = 1 is 1/5 *
2/5 = 2/25. To get i = 2, the first rand5() must be 2 and the second
rand5() must be 1 or 2. Thus, i = 2 also with probability 1/5 * 2/5 =
2/25. For i = 3, either the first rand5() must be 1 and the second
rand5() must be 3, 4, or 5, or the first rand5 must be 3 and the
second rand5() must be 1 or 2. Thus, i = 3 with probability 1/5 * 3/5
+ 1/5 * 2/5 = 1/5. Continuing in this way, we see that the
probabilities of the various results are 2/25, 2/25, 1/5, 1/5, 1/5,
3/25, 3/25. These are not uniform!
Dave
On Jul 31, 8:12 am, Sony Jose sonyj...@gmail.com wrote:
Hi Dave,
i just checked;
int i;
int j;
for(i=1;i6;i++) {
j = 2*(i/3);
printf(\n%d\n,j);
}
gives me output 0,0,2,2,2. and there was no 3;
and since we are anyway generating random numbers would this difference in
distribution really matter?
On Sat, Jul 31, 2010 at 6:30 PM, Dave dave_and_da...@juno.com wrote:
@Sony. No. Consider the following table:
rand5() (2/3)*rand5()
_
1 0
2 1
3 2
4 2
5 3
Thus, (2/3)*rand5() is not uniformly distributed, nor is it in the
range 0 to 2.
Dave
On Jul 31, 7:49 am, Sony Jose sonyj...@gmail.com wrote:
what about
int i = rand5() + (2/3)*rand5();
won't this work?
On Sat, Jul 31, 2010 at 5:46 PM, Dave dave_and_da...@juno.com wrote:
Use the rejection method...
int rand7()
{
int i;
do
i = 5 * rand5() + rand5() - 3;
while( i 23 );
return i / 3;
}
The loop assigns i a value between 5*1+1-3 = 3 and 5*5+5-3 = 27 with
uniform probability, and then rejects any value of i 23. Thus, after
the loop, i has a uniform distribution on the interval 3 to 23.
Dividing by 3 gives the desired result.
Under the assumptions of the problem, a value of i is rejected with
probability 4/25, so the loop executes an average of 1/(1 - 4/25) =
25/21 times. Therefore, on average, it takes 50/21 rand5's to make a
rand7.
Dave
On Jul 30, 8:33 am, jalaj jaiswal jalaj.jaiswa...@gmail.com wrote:
given a rand5 function which generates numbers from 1 to 5 with equal
probability.. give an algorithm which uses rand5 function and
generates
numbers from 1 to 7 with equal probability
--
With Regards,
Jalaj Jaiswal
+919026283397
B.TECH IT
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 algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
algogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Regards,
Sony- Hide quoted text -
- Show quoted text -
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Regards,
Sony- Hide quoted text -
- Show quoted text -
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: algorithm
@Debajyoti. There are 25 possible values of 5*rand5() + rand5(). The
largest multiple of 7 not exceeding 25 is 3*7. Thus, I divide by 3.
The largest number n such that n/3 = 7 is 23. This is where the 3 and
23 come from. You might google rejection method to find fuller
descriptions of the theory behind these methods.
Dave
On Jul 31, 8:04 am, Debajyoti Sarma sarma.debajy...@gmail.com wrote:
why u have chosen that 23 ?
why dividing by 3 ?
don't understand the logic.
Please explain so that it become understandable.
On 7/31/10, Dave dave_and_da...@juno.com wrote:
Use the rejection method...
int rand7()
{
int i;
do
i = 5 * rand5() + rand5() - 3;
while( i 23 );
return i / 3;
}
The loop assigns i a value between 5*1+1-3 = 3 and 5*5+5-3 = 27 with
uniform probability, and then rejects any value of i 23. Thus, after
the loop, i has a uniform distribution on the interval 3 to 23.
Dividing by 3 gives the desired result.
Under the assumptions of the problem, a value of i is rejected with
probability 4/25, so the loop executes an average of 1/(1 - 4/25) =
25/21 times. Therefore, on average, it takes 50/21 rand5's to make a
rand7.
Dave
On Jul 30, 8:33 am, jalaj jaiswal jalaj.jaiswa...@gmail.com wrote:
given a rand5 function which generates numbers from 1 to 5 with equal
probability.. give an algorithm which uses rand5 function and generates
numbers from 1 to 7 with equal probability
--
With Regards,
Jalaj Jaiswal
+919026283397
B.TECH IT
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 algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.- Hide quoted text -
- Show quoted text -
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] What is the time complexity of multiplying two n-digit numbers base b
O(log n). If u add in pairs. e.g. (5+5)=10. now add 10+10. On Sat, Jul 31, 2010 at 6:28 PM, sourav souravs...@gmail.com wrote: When you first learned to multiply numbers, you were told that x * y means adding x a total of y times, so 5 * 4 = 5+5+5+5 = 20. What is the time complexity of multiplying two n-digit numbers in base b using the repeated addition method, as a function of n and b. Assume that single-digit by single-digit addition or multiplication takes O(1) time. Show how you arrive at your answer. (Hint that was given : how big can y be as a function of n and b?) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: What is the time complexity of multiplying two n-digit numbers base b
If by repeated addition method, you mean m + m + m + ... + m (where m occurs k times) for forming the product k*m, then the work of forming k*m where k and m are n digit numbers is O((k-1)*n). Using the elementary school algorithm, the work can be reduced to O(n^2). See http://en.wikipedia.org/wiki/Multiplication_algorithm for even faster algorithms. Dave On Jul 31, 7:58 am, sourav souravs...@gmail.com wrote: When you first learned to multiply numbers, you were told that x * y means adding x a total of y times, so 5 * 4 = 5+5+5+5 = 20. What is the time complexity of multiplying two n-digit numbers in base b using the repeated addition method, as a function of n and b. Assume that single-digit by single-digit addition or multiplication takes O(1) time. Show how you arrive at your answer. (Hint that was given : how big can y be as a function of n and b?) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Merging Companies Problem
Suppose we start with n companies that eventually merge into one big
company. How many different ways are there for them to merge?
With three companies {a,b,c}, we need to find the number of ways that
the three companies can become two companies, and for every one of
those possibilities, the two remaining companies can be reduced to one
in only 1 way (because we've already solved the case of two
companies). In the case of {a,b,c}, we can have 1 * [{ab,c}, {ac,b},
{bc,a}], or 3.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] minimum window containing charecters
@ abv ... ab to band kar de bhai On Sat, Jul 31, 2010 at 7:09 PM, srikanth sg srikanthini...@gmail.comwrote: given two string , find the minimum width in string 1 containing the all characters of string 2 , they may present in different order string 1-HELLO string 2- LE answer-2 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- With Regards, Jalaj Jaiswal +919026283397 B.TECH IT 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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] minimum window containing charecters
LOL :P On Sat, Jul 31, 2010 at 8:18 AM, jalaj jaiswal jalaj.jaiswa...@gmail.comwrote: @ abv ... ab to band kar de bhai On Sat, Jul 31, 2010 at 7:09 PM, srikanth sg srikanthini...@gmail.comwrote: given two string , find the minimum width in string 1 containing the all characters of string 2 , they may present in different order string 1-HELLO string 2- LE answer-2 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- With Regards, Jalaj Jaiswal +919026283397 B.TECH IT 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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks]
A doubly linked list with ordered nodes(increasing order) is a SKEWED BST. How can we change it into (inplace)balanced BST . Shrish Mishra NIT,Allahabad -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] minimum window containing charecters
At the moment, I can only think of an O(n^3) algo. Maybe if you can find a hash function which computes the hash value depending on the unique characters the string contains, you can reduce it to O(n^2). On Sat, Jul 31, 2010 at 7:09 PM, srikanth sg srikanthini...@gmail.comwrote: given two string , find the minimum width in string 1 containing the all characters of string 2 , they may present in different order string 1-HELLO string 2- LE answer-2 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. Please access the attached hyperlink for an important electronic communications disclaimer: http://dce.edu/web/Sections/Standalone/Email_Disclaimer.php -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Merging Companies Problem
For merging n companies, F(n) = n*F(n-1) for n 3.
Base case, F(3) = 3.
On Sat, Jul 31, 2010 at 6:59 PM, sourav souravs...@gmail.com wrote:
Suppose we start with n companies that eventually merge into one big
company. How many different ways are there for them to merge?
With three companies {a,b,c}, we need to find the number of ways that
the three companies can become two companies, and for every one of
those possibilities, the two remaining companies can be reduced to one
in only 1 way (because we've already solved the case of two
companies). In the case of {a,b,c}, we can have 1 * [{ab,c}, {ac,b},
{bc,a}], or 3.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Please access the attached hyperlink for an important electronic communications
disclaimer: http://dce.edu/web/Sections/Standalone/Email_Disclaimer.php
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: What is the time complexity of multiplying two n-digit numbers base b
Multiplying two n digit numbers, where multiplication of two 1 digit numbers is O(1), is : O(n^2). On Sat, Jul 31, 2010 at 9:12 PM, Dave dave_and_da...@juno.com wrote: If by repeated addition method, you mean m + m + m + ... + m (where m occurs k times) for forming the product k*m, then the work of forming k*m where k and m are n digit numbers is O((k-1)*n). Using the elementary school algorithm, the work can be reduced to O(n^2). See http://en.wikipedia.org/wiki/Multiplication_algorithm for even faster algorithms. Dave On Jul 31, 7:58 am, sourav souravs...@gmail.com wrote: When you first learned to multiply numbers, you were told that x * y means adding x a total of y times, so 5 * 4 = 5+5+5+5 = 20. What is the time complexity of multiplying two n-digit numbers in base b using the repeated addition method, as a function of n and b. Assume that single-digit by single-digit addition or multiplication takes O(1) time. Show how you arrive at your answer. (Hint that was given : how big can y be as a function of n and b?) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. Please access the attached hyperlink for an important electronic communications disclaimer: http://dce.edu/web/Sections/Standalone/Email_Disclaimer.php -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Amazon Placement Question
@Ram Kumar: Yes. Simple and affective. Just at each node: node-left-side=node-right node-right-side=node-side-left i.e at each node you are setting the side of each of your child. Go on and just do it for all nodes. Done. On Sat, Jul 31, 2010 at 9:39 AM, Ram Kumar harrypotter@gmail.comwrote: DONT DO A BFS!! NOT WORTH IT! CALL THE NEW POINTER AS 'SIDE' POINTER. for every root connect its left and right, for every root connect root-right and root-SIDE-left that ll do -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. Please access the attached hyperlink for an important electronic communications disclaimer: http://dce.edu/web/Sections/Standalone/Email_Disclaimer.php -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Merging Companies Problem
Cant u slit it s n/2 companies and merge them recursively .like x^y the
multiply x to y/2 time and then multiply tht product twice.
On Sat, Jul 31, 2010 at 6:59 PM, sourav souravs...@gmail.com wrote:
Suppose we start with n companies that eventually merge into one big
company. How many different ways are there for them to merge?
With three companies {a,b,c}, we need to find the number of ways that
the three companies can become two companies, and for every one of
those possibilities, the two remaining companies can be reduced to one
in only 1 way (because we've already solved the case of two
companies). In the case of {a,b,c}, we can have 1 * [{ab,c}, {ac,b},
{bc,a}], or 3.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
yezhu malai vaasa venkataramana Govinda Govinda
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: What is the time complexity of multiplying two n-digit numbers base b
If suppose we want to Do N*K then we add N K-times or K N-times. hence the complexity should be O(N*K) On Sat, Jul 31, 2010 at 9:12 PM, Dave dave_and_da...@juno.com wrote: If by repeated addition method, you mean m + m + m + ... + m (where m occurs k times) for forming the product k*m, then the work of forming k*m where k and m are n digit numbers is O((k-1)*n). Using the elementary school algorithm, the work can be reduced to O(n^2). See http://en.wikipedia.org/wiki/Multiplication_algorithm for even faster algorithms. Dave On Jul 31, 7:58 am, sourav souravs...@gmail.com wrote: When you first learned to multiply numbers, you were told that x * y means adding x a total of y times, so 5 * 4 = 5+5+5+5 = 20. What is the time complexity of multiplying two n-digit numbers in base b using the repeated addition method, as a function of n and b. Assume that single-digit by single-digit addition or multiplication takes O(1) time. Show how you arrive at your answer. (Hint that was given : how big can y be as a function of n and b?) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- regards Apoorve Mohan -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks]
find the middle of the list and make it as the root..thus i this maner u will get a balanced tree.. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: What is the time complexity of multiplying two n-digit numbers base b
What about this-
=
long multiply(long num, int n) {
long bigSum=0;
while(n=1) {
int sum =num; int j;
for(int i =2; i=n; i= i*2) {
sum+=sum;
j=i;
} //for
n = n -j;
bigSum=bigSum+sum;
}//while
return bigSum;
}//multiply()
===
It's *O(logn).*
On Sun, Aug 1, 2010 at 8:54 AM, Apoorve Mohan apoorvemo...@gmail.comwrote:
If suppose
we want to Do N*K
then we add N K-times or K N-times.
hence the complexity should be O(N*K)
On Sat, Jul 31, 2010 at 9:12 PM, Dave dave_and_da...@juno.com wrote:
If by repeated addition method, you mean
m + m + m + ... + m (where m occurs k times)
for forming the product k*m, then the work of forming k*m where k and
m are n digit numbers is O((k-1)*n).
Using the elementary school algorithm, the work can be reduced to
O(n^2).
See http://en.wikipedia.org/wiki/Multiplication_algorithm for even
faster algorithms.
Dave
On Jul 31, 7:58 am, sourav souravs...@gmail.com wrote:
When you first learned to multiply numbers, you were told that x * y
means adding x a total of y times, so 5 * 4 = 5+5+5+5 = 20. What is
the time complexity of multiplying two n-digit numbers in base b using
the repeated addition method, as a function of n and b. Assume that
single-digit by single-digit addition or multiplication takes O(1)
time.
Show how you arrive at your answer.
(Hint that was given : how big can y be as a function of n and b?)
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
regards
Apoorve Mohan
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: What is the time complexity of multiplying two n-digit numbers base b
An edgy case...
On Sun, Aug 1, 2010 at 9:52 AM, Shiv ... shivsinha2...@gmail.com wrote:
What about this-
=
long multiply(long num, int n) {
long bigSum=0;
while(n=1) {
int sum =num; int j*=1*; //to avoid garbage @n=1.
for(int i =2; i=n; i= i*2) {
sum+=sum;
j=i;
} //for
n = n -j;
bigSum=bigSum+sum;
}//while
return bigSum;
}//multiply()
===
It's *O(logn).*
On Sun, Aug 1, 2010 at 8:54 AM, Apoorve Mohan apoorvemo...@gmail.comwrote:
If suppose
we want to Do N*K
then we add N K-times or K N-times.
hence the complexity should be O(N*K)
On Sat, Jul 31, 2010 at 9:12 PM, Dave dave_and_da...@juno.com wrote:
If by repeated addition method, you mean
m + m + m + ... + m (where m occurs k times)
for forming the product k*m, then the work of forming k*m where k and
m are n digit numbers is O((k-1)*n).
Using the elementary school algorithm, the work can be reduced to
O(n^2).
See http://en.wikipedia.org/wiki/Multiplication_algorithm for even
faster algorithms.
Dave
On Jul 31, 7:58 am, sourav souravs...@gmail.com wrote:
When you first learned to multiply numbers, you were told that x * y
means adding x a total of y times, so 5 * 4 = 5+5+5+5 = 20. What is
the time complexity of multiplying two n-digit numbers in base b using
the repeated addition method, as a function of n and b. Assume that
single-digit by single-digit addition or multiplication takes O(1)
time.
Show how you arrive at your answer.
(Hint that was given : how big can y be as a function of n and b?)
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
regards
Apoorve Mohan
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks]
No it won't it will just reduce the height of tree to n/2 (from n). My algo- 1. Parse in triplets. For every 3 nodes make the second one parent of other two. Also, queue up such parents. 2. repeat step 1 till you have only 1 node left (root). But this may give a tree 'imbalanced at root. we may need to do some height re-balancing. -Thanks On Sun, Aug 1, 2010 at 9:26 AM, Manjunath Manohar manjunath.n...@gmail.comwrote: find the middle of the list and make it as the root..thus i this maner u will get a balanced tree.. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
