[algogeeks] Coding question.............

[UMESH KUMAR]

hello...

QN :- How to find *TRANSPOSE*  of the *RECTANGULAR* matrix
i,e. m * n , where n != m.

Ex:-
  input:-

   1  2  3  4
   5  6  7  8

output:-
   1  5
   2  6
   3  7
   4  8

thanks and regards
  UMESH KUMAR
   D.U.

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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] Suggestions required regarding my final year Project....

[vishwa kumar]

Hello saravana,
   venu asked idea only.he doesnt code like
u..

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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] Suggestions required regarding my final year Project....

[saravana kumar]

http://www.hackchina.com/en/

On Fri, Jan 28, 2011 at 11:13 AM, pawan gangwani
wrote:

> Hi Rajeev/venu,
>
> i suggest you to think of a domain of you interest first, then proceed in
> that direction thinking of some project.
> have you thought of any domain in which you want to go for a project.
>
> it may some web application, some thing in O/S like unix, may be
> implementing a protocol of networks, bulding your own shell in Unix/Linux.
>
> regards
> Pawan
>
>
>
> On Fri, Jan 28, 2011 at 11:06 AM, Rajeev Kumar 
> wrote:
>
>> Hi,
>>  Can any one please suggest any good site to find good projects to do in
>> final year.
>>
>> Thanks,
>> Rajeev.
>>
>> On Fri, Jan 28, 2011 at 9:10 AM, Venu  wrote:
>>
>>> Hi friends-
>>>
>>> This is Venu, studying final year B.Tech in Computer Science at
>>> Jawaharlal Nehru University, Hyderabad.
>>> Can you please suggest me some ideas regarding my final year project
>>> (3 months duration).
>>>
>>> Thanking you in advance...
>>>
>>> Regards
>>> Venu.
>>>
>>> --
>>> You received this message because you are subscribed to the Google Groups
>>> "Algorithm Geeks" group.
>>> To post to this group, send email to algogeeks@googlegroups.com.
>>> To unsubscribe from this group, send email to
>>> algogeeks+unsubscr...@googlegroups.com
>>> .
>>> For more options, visit this group at
>>> http://groups.google.com/group/algogeeks?hl=en.
>>>
>>>
>>
>>
>> --
>> Thank You
>> Rajeev 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.
>>
>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Suggestions required regarding my final year Project....

[pawan gangwani]

Hi Rajeev/venu,

i suggest you to think of a domain of you interest first, then proceed in
that direction thinking of some project.
have you thought of any domain in which you want to go for a project.

it may some web application, some thing in O/S like unix, may be
implementing a protocol of networks, bulding your own shell in Unix/Linux.

regards
Pawan


On Fri, Jan 28, 2011 at 11:06 AM, Rajeev Kumar wrote:

> Hi,
>  Can any one please suggest any good site to find good projects to do in
> final year.
>
> Thanks,
> Rajeev.
>
> On Fri, Jan 28, 2011 at 9:10 AM, Venu  wrote:
>
>> Hi friends-
>>
>> This is Venu, studying final year B.Tech in Computer Science at
>> Jawaharlal Nehru University, Hyderabad.
>> Can you please suggest me some ideas regarding my final year project
>> (3 months duration).
>>
>> Thanking you in advance...
>>
>> Regards
>> Venu.
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com
>> .
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>>
>
>
> --
> Thank You
> Rajeev 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.
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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] Suggestions required regarding my final year Project....

[Rajeev Kumar]

Hi,
 Can any one please suggest any good site to find good projects to do in
final year.

Thanks,
Rajeev.

On Fri, Jan 28, 2011 at 9:10 AM, Venu  wrote:

> Hi friends-
>
> This is Venu, studying final year B.Tech in Computer Science at
> Jawaharlal Nehru University, Hyderabad.
> Can you please suggest me some ideas regarding my final year project
> (3 months duration).
>
> Thanking you in advance...
>
> Regards
> Venu.
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>


-- 
Thank You
Rajeev 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.

Re: [algogeeks] Re: Amazon Question

[nphard nphard]

Not correct. You cannot assume that the right node always points to the
successor. If you do that, your traversal will be affected. Consider that
when you reach a node B from the right pointer of its parent A, you traverse
that subtree rooted at B in normal inorder. However, when you reach B from
its inorder predecessor C, you should have the knowledge that you have
visited that node's left subtree and should not visit again (which is only
known if you have the information that you are reaching that node through a
thread).

On Thu, Jan 27, 2011 at 10:57 PM, Ritu Garg  wrote:

> @nphard
>
> ideally,a flag is required in right threaded tree to distinguish whether
> right child is a pointer to inorder successor or to right child.Even we can
> do without flag assuming that  there ll be no further insertions taking
> place in tree and no other traversal is required.
>
> here we suppose that right pointer always gives the successor..
>
> The solution to get the linear inorder traversal is just tailored for a
> situation where there is no extra space,not even for stack!!!
>
> On Fri, Jan 28, 2011 at 5:42 AM, nphard nphard wrote:
>
>> @Ritu - Do you realize that you cannot just convert a given binary tree
>> into right-threaded binary tree? You need at least 1 bit information at each
>> node to specify whether the right pointer of that node is a regular pointer
>> or pointer to the inorder successor. This is because traversal is done
>> differently when you arrive at a node through its inorder predecessor.
>>
>>   On Thu, Jan 27, 2011 at 7:22 AM, Ritu Garg wrote:
>>
>>>   solution is not too hard to understand!!
>>> 1. [quote] For every none leaf node , go to the last node in it's left
>>>
>>> subtree and mark the right child of that node as x [\quote]. How are
>>> we going to refer to the right child now ??We have removed it's
>>> reference now !!
>>>
>>> last node in left sub tree of any node always have right pointer as NULL
>>> because this is the last node
>>>
>>> 2. It is to be repeated for every node except the non leaf nodes . This
>>>
>>> will take O(n*n) time in worst case , say a leftist tree with only
>>> left pointers . root makes n-1 traversals , root's left subtree's root
>>> makes n-2 , and so on.
>>> i said that it ll take O(n) time for well balanced tree.
>>> for a node at height h ,it takes O(h) to fill this node as successor of
>>> some other node.if combined for all sum(O(h)) h=1 to lg n ..total time ll
>>> come as O(n)
>>>
>>> 3. Take the case below .
>>>
>>>
>>>1
>>>   2 3
>>> 1  1.5   2.5   4
>>>
>>> for node 2 , you will go to 1 , which is the successor of 2 , you make
>>> 2->right=1  but what about node 1.5 ???
>>> same is the case with node 3 ... 3->right=2.5 . How will we refer to 4
>>> now ??
>>>
>>> when you ll process node 1,it ll be filled in as right child of 1.5
>>> there is no successor for 4.
>>>
>>> In Brief
>>>
>>> 1. Convert the tree to right threaded binary tree.means all right
>>> children point to their successors.
>>> it ll take no additional space.ll take O(n) time if tree is well balanced
>>>
>>> 2. Do inorder traversal to find ith element without using extra space
>>> because succssor of each node is pointed by right child.
>>>
>>> i hope you got it now!!
>>>
>>>
>>>
>>>
>>>
>>>
>>>
>>> On Wed, Jan 26, 2011 at 5:31 PM, sankalp srivastava <
>>> richi.sankalp1...@gmail.com> wrote:
>>>
 I don't seem to understand ur solution .
 [quote] For every none leaf node , go to the last node in it's left
 subtree and mark the right child of that node as x [\quote]. How are
 we going to refer to the right child now ??We have removed it's
 reference now !!

 It is to be repeated for every node except the non leaf nodes . This
 will take O(n*n) time in worst case , say a leftist tree with only
 left pointers . root makes n-1 traversals , root's left subtree's root
 makes n-2 , and so on.

 Go to the largest node in the left subtree .This means go to the left
 subtree and keep on going to the right until it becomes null  , in
 which case  , you make y->right as x . This means effectively , that y
 is the predecessor of x , in the tree . Considering a very good code ,
 it may take O(1) space , but you will still need additional pointers.
 Take the case below .

1
   2 3
 1  1.5   2.5   4

 for node 2 , you will go to 1 , which is the successor of 2 , you make
 2->right=1  but what about node 1.5 ???
 same is the case with node 3 ... 3->right=2.5 . How will we refer to 4
 now ??

 Now using inorder traversal with a count , I will start at 1->left , 2-
 >left = 1 , then 2 ... then 2->right = 1 again . then 1 , and then 1-
 >right=3 ...clearly , this will not give us a solution .
 A reverse inorder looks just fine to me .

 On Jan 26, 3:14 pm, Ritu Garg  wrote:
 > @Algoose
 >
 > I said ..*

Re: [algogeeks] Re: Amazon Question

[Ritu Garg]

@nphard

ideally,a flag is required in right threaded tree to distinguish whether
right child is a pointer to inorder successor or to right child.Even we can
do without flag assuming that  there ll be no further insertions taking
place in tree and no other traversal is required.

here we suppose that right pointer always gives the successor..

The solution to get the linear inorder traversal is just tailored for a
situation where there is no extra space,not even for stack!!!

On Fri, Jan 28, 2011 at 5:42 AM, nphard nphard wrote:

> @Ritu - Do you realize that you cannot just convert a given binary tree
> into right-threaded binary tree? You need at least 1 bit information at each
> node to specify whether the right pointer of that node is a regular pointer
> or pointer to the inorder successor. This is because traversal is done
> differently when you arrive at a node through its inorder predecessor.
>
>   On Thu, Jan 27, 2011 at 7:22 AM, Ritu Garg wrote:
>
>>   solution is not too hard to understand!!
>> 1. [quote] For every none leaf node , go to the last node in it's left
>>
>> subtree and mark the right child of that node as x [\quote]. How are
>> we going to refer to the right child now ??We have removed it's
>> reference now !!
>>
>> last node in left sub tree of any node always have right pointer as NULL
>> because this is the last node
>>
>> 2. It is to be repeated for every node except the non leaf nodes . This
>>
>> will take O(n*n) time in worst case , say a leftist tree with only
>> left pointers . root makes n-1 traversals , root's left subtree's root
>> makes n-2 , and so on.
>> i said that it ll take O(n) time for well balanced tree.
>> for a node at height h ,it takes O(h) to fill this node as successor of
>> some other node.if combined for all sum(O(h)) h=1 to lg n ..total time ll
>> come as O(n)
>>
>> 3. Take the case below .
>>
>>
>>1
>>   2 3
>> 1  1.5   2.5   4
>>
>> for node 2 , you will go to 1 , which is the successor of 2 , you make
>> 2->right=1  but what about node 1.5 ???
>> same is the case with node 3 ... 3->right=2.5 . How will we refer to 4
>> now ??
>>
>> when you ll process node 1,it ll be filled in as right child of 1.5
>> there is no successor for 4.
>>
>> In Brief
>>
>> 1. Convert the tree to right threaded binary tree.means all right children
>> point to their successors.
>> it ll take no additional space.ll take O(n) time if tree is well balanced
>>
>> 2. Do inorder traversal to find ith element without using extra space
>> because succssor of each node is pointed by right child.
>>
>> i hope you got it now!!
>>
>>
>>
>>
>>
>>
>>
>> On Wed, Jan 26, 2011 at 5:31 PM, sankalp srivastava <
>> richi.sankalp1...@gmail.com> wrote:
>>
>>> I don't seem to understand ur solution .
>>> [quote] For every none leaf node , go to the last node in it's left
>>> subtree and mark the right child of that node as x [\quote]. How are
>>> we going to refer to the right child now ??We have removed it's
>>> reference now !!
>>>
>>> It is to be repeated for every node except the non leaf nodes . This
>>> will take O(n*n) time in worst case , say a leftist tree with only
>>> left pointers . root makes n-1 traversals , root's left subtree's root
>>> makes n-2 , and so on.
>>>
>>> Go to the largest node in the left subtree .This means go to the left
>>> subtree and keep on going to the right until it becomes null  , in
>>> which case  , you make y->right as x . This means effectively , that y
>>> is the predecessor of x , in the tree . Considering a very good code ,
>>> it may take O(1) space , but you will still need additional pointers.
>>> Take the case below .
>>>
>>>1
>>>   2 3
>>> 1  1.5   2.5   4
>>>
>>> for node 2 , you will go to 1 , which is the successor of 2 , you make
>>> 2->right=1  but what about node 1.5 ???
>>> same is the case with node 3 ... 3->right=2.5 . How will we refer to 4
>>> now ??
>>>
>>> Now using inorder traversal with a count , I will start at 1->left , 2-
>>> >left = 1 , then 2 ... then 2->right = 1 again . then 1 , and then 1-
>>> >right=3 ...clearly , this will not give us a solution .
>>> A reverse inorder looks just fine to me .
>>>
>>> On Jan 26, 3:14 pm, Ritu Garg  wrote:
>>> > @Algoose
>>> >
>>> > I said ..*.For every node x,go to the last node in its left subtree and
>>> mark
>>> > the right child of that node as x.*
>>> >
>>> > it is to be repeated for all nodes except leaf nodes.
>>> > to apply this approach ,you need to go down the tree.No parent pointers
>>> > required.
>>> > for every node say x whose left sub tree is not null ,go to the largest
>>> node
>>> > in left sub-tree say y.
>>> > Set  y->right = x
>>> > y is the last node to be processed in left sub-tree of x hence x is
>>> > successor of y.
>>> >
>>> >
>>> >
>>> > On Wed, Jan 26, 2011 at 3:27 PM, Algoose chase 
>>> wrote:
>>> > > @ritu
>>> > > how would you find a successor without extra space if you dont have a
>>> > > parent point

[algogeeks] Suggestions required regarding my final year Project....

[Venu]

Hi friends-

This is Venu, studying final year B.Tech in Computer Science at
Jawaharlal Nehru University, Hyderabad.
Can you please suggest me some ideas regarding my final year project
(3 months duration).

Thanking you in advance...

Regards
Venu.

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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: Amazon Question

[ligerdave]

this is a tree traversal(depth first) problem.

as for the extra space, depends on how you see it. "fifth" can be the
counter and when the counter reaches 0, you have your fifth largest
element

On Jan 21, 9:58 am, nagaraj N  wrote:
> How do you find out the fifth maximum element in an binary search tree
> in efficient manner without using any extra space?

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Re: Amazon Question

[nphard nphard]

@Ritu - Do you realize that you cannot just convert a given binary tree into
right-threaded binary tree? You need at least 1 bit information at each node
to specify whether the right pointer of that node is a regular pointer or
pointer to the inorder successor. This is because traversal is done
differently when you arrive at a node through its inorder predecessor.

On Thu, Jan 27, 2011 at 7:22 AM, Ritu Garg  wrote:

> solution is not too hard to understand!!
> 1. [quote] For every none leaf node , go to the last node in it's left
>
> subtree and mark the right child of that node as x [\quote]. How are
> we going to refer to the right child now ??We have removed it's
> reference now !!
>
> last node in left sub tree of any node always have right pointer as NULL
> because this is the last node
>
> 2. It is to be repeated for every node except the non leaf nodes . This
>
> will take O(n*n) time in worst case , say a leftist tree with only
> left pointers . root makes n-1 traversals , root's left subtree's root
> makes n-2 , and so on.
> i said that it ll take O(n) time for well balanced tree.
> for a node at height h ,it takes O(h) to fill this node as successor of
> some other node.if combined for all sum(O(h)) h=1 to lg n ..total time ll
> come as O(n)
>
> 3. Take the case below .
>
>
>1
>   2 3
> 1  1.5   2.5   4
>
> for node 2 , you will go to 1 , which is the successor of 2 , you make
> 2->right=1  but what about node 1.5 ???
> same is the case with node 3 ... 3->right=2.5 . How will we refer to 4
> now ??
>
> when you ll process node 1,it ll be filled in as right child of 1.5
> there is no successor for 4.
>
> In Brief
>
> 1. Convert the tree to right threaded binary tree.means all right children
> point to their successors.
> it ll take no additional space.ll take O(n) time if tree is well balanced
>
> 2. Do inorder traversal to find ith element without using extra space
> because succssor of each node is pointed by right child.
>
> i hope you got it now!!
>
>
>
>
>
>
>
> On Wed, Jan 26, 2011 at 5:31 PM, sankalp srivastava <
> richi.sankalp1...@gmail.com> wrote:
>
>> I don't seem to understand ur solution .
>> [quote] For every none leaf node , go to the last node in it's left
>> subtree and mark the right child of that node as x [\quote]. How are
>> we going to refer to the right child now ??We have removed it's
>> reference now !!
>>
>> It is to be repeated for every node except the non leaf nodes . This
>> will take O(n*n) time in worst case , say a leftist tree with only
>> left pointers . root makes n-1 traversals , root's left subtree's root
>> makes n-2 , and so on.
>>
>> Go to the largest node in the left subtree .This means go to the left
>> subtree and keep on going to the right until it becomes null  , in
>> which case  , you make y->right as x . This means effectively , that y
>> is the predecessor of x , in the tree . Considering a very good code ,
>> it may take O(1) space , but you will still need additional pointers.
>> Take the case below .
>>
>>1
>>   2 3
>> 1  1.5   2.5   4
>>
>> for node 2 , you will go to 1 , which is the successor of 2 , you make
>> 2->right=1  but what about node 1.5 ???
>> same is the case with node 3 ... 3->right=2.5 . How will we refer to 4
>> now ??
>>
>> Now using inorder traversal with a count , I will start at 1->left , 2-
>> >left = 1 , then 2 ... then 2->right = 1 again . then 1 , and then 1-
>> >right=3 ...clearly , this will not give us a solution .
>> A reverse inorder looks just fine to me .
>>
>> On Jan 26, 3:14 pm, Ritu Garg  wrote:
>> > @Algoose
>> >
>> > I said ..*.For every node x,go to the last node in its left subtree and
>> mark
>> > the right child of that node as x.*
>> >
>> > it is to be repeated for all nodes except leaf nodes.
>> > to apply this approach ,you need to go down the tree.No parent pointers
>> > required.
>> > for every node say x whose left sub tree is not null ,go to the largest
>> node
>> > in left sub-tree say y.
>> > Set  y->right = x
>> > y is the last node to be processed in left sub-tree of x hence x is
>> > successor of y.
>> >
>> >
>> >
>> > On Wed, Jan 26, 2011 at 3:27 PM, Algoose chase 
>> wrote:
>> > > @ritu
>> > > how would you find a successor without extra space if you dont have a
>> > > parent pointer ?
>> > > for Instance from the right most node of left subtree to the parent of
>> left
>> > > subtree(root) ?
>> > > @Juver++
>> > > Internal stack does count as extra space !!
>> >
>>  > > On Wed, Jan 26, 2011 at 3:02 PM, ritu 
>> wrote:
>> >
>> > >> No,no extra space is needed.
>> > >> Right children which are NULL pointers are replaced with pointer to
>> > >> successor.
>> >
>> > >> On Jan 26, 1:18 pm, nphard nphard  wrote:
>> > >> > If you convert the given binary tree into right threaded binary
>> tree,
>> > >> won't
>> > >> > you be using extra space while doing so? Either the given tree
>> should
>> > >> > already be right-threaded (or with parent p

Re: [algogeeks] Distance in a dictionary

[nphard nphard]

One more thing is that you cannot stop if you reach the goal state as you
still do not know if its the optimal path or not (heuristic does not help in
that). So, you need to search in a Breadth First manner anyway regardless of
reaching goal states in some places to determine the optimal path (as you
may later encounter a shorter path). In fact, a heuristic is not even
necessary. Its a simple BFS.

On Sat, Jan 22, 2011 at 1:20 PM, Algoose chase  wrote:

> To add to what nishaanth mentioned, I think we should also track all the
> state transitions so that we can back track and make alternate transitions
> if the path that was already taken was later found to be incorrect one which
> will not help to reach the given target (with the given set of words).
>
>
> On Fri, Jan 21, 2011 at 10:09 PM, Manmeet Singh wrote:
>
>> whts complexity for this movegen()
>>
>>
>> On Fri, Jan 21, 2011 at 9:52 PM, nishaanth  wrote:
>>
>>> Ok lets define the following functions.
>>>
>>> movegen()- gives the list of next move given the state. This is basically
>>> all the 1 distance words given the current word.
>>>
>>> heuristic()- this gives the number of non-matching characters of the
>>> given word with the goal word.
>>>
>>> Start from start state and expand.
>>> Now always choose the move which gives a lesser heuristic valued state.
>>> Stop if you reach the goal.
>>>
>>> You can refer to Russel Norvig book on AI for detailed explanation.
>>>
>>>
>>>
>>> Regards,
>>>
>>> S.Nishaanth,
>>> Computer Science and engineering,
>>> IIT Madras.
>>>
>>> --
>>> You received this message because you are subscribed to the Google Groups
>>> "Algorithm Geeks" group.
>>> To post to this group, send email to algogeeks@googlegroups.com.
>>> To unsubscribe from 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] CodeFest - Online Coding Festival by Computer Engineering Society, IT-BHU

[vishal kumar rai]

Hello,

We are delighted to inform you that
*Codefest'11*,
the *annual International online coding festival* of *Computer Engineering
Society, IT-BHU*, has been unveiled. CodeFest is a unique fest wherein
concepts of mathematics, logic, artificial intelligence, algorithms,
language syntax, etc. are required to be deployed in programming; these
concepts manifest themselves in solving problems effectively and
efficiently!

CodeFest was started last year. CodeFest'10 was a phenomenal success with
participation from all over the globe. CodeFest'11 is geared up with some
new and pepped up events, while maintaining the integrity of its
standards.This year CodeFest has associated with
*Technex'11*,
the *annual all India Technical Festival of IT-BHU*, to expand its horizons.


*Here is a brief description of the constituent online events:*

   - *Mathmania :* A
   mathematical puzzle contest that puts mathematical and computational skills
   to test.
   - *Manthan :* An
   algorithm intensive programming contest that would require coders to tailor
   existing standard algorithms.
   - *Perplexed
:*A
programming contest, aimed to test the knowledge of C, wherein codes
will
   be rewarded against syntactic constraints.
   - *Ratespiel :* A
   technical contest covering different areas of Computer Science.
   - *Virtual Combat
   :* An educational game wherein teams of programmed robotic tanks will
   fight the battles for glory. Codes Do Fight! Watch
thisout.

Visit our *website*  for more details.

*Few exciting statistics about Codefest'10:*

   - 2354 registrations (including 128 professionals) from 680 different
   institutions, across 59 countries
   - Some participants were among the winners of Google Code Jam, Top Coder
   SRMs and ACM ICPC
   - Total prize money was a whopping amount of 260,000 INR!
   - Codefest '10 was the largest online coding festival of the Indian
   subcontinent in 2010 in terms of prize money!
   - Codefest'10 was the second largest online coding festival of the Indian
   subcontinent in 2010, next to Bitwise
   - Gained recognition from several international organizations including
   Codechef, Adobe, British Telecom, TCS and IEEE

The Codefest'11 team has set out to unleash a yet another coding
extravaganza. We hope that your participation would raise the level of
competition in Codefest'11. Feel free to contact us at
codef...@itbhu.ac.inor reach us personally at:

   - Mohit Bansal mohit.bansal.cs...@itbhu.ac.in
   - Saket Saurabh saket.saurabh.cs...@itbhu.ac.in

We wish you all the best for Codefest'11 and for your future endeavours.

Happy coding, and be free!

Regards,
Team Codefest
Visit us at http://itbhu.ac.in/codefest
Mail us at codef...@itbhu.ac.in
Check out our page at http://facebook.com/codefest
Follow us at http://twitter.com/c0defest/
Read our blog at http://itbhu.ac.in/codefest/blog

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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] CodeFest - Online Coding Festival by Computer Engineering Society, IT-BHU

[vishal kumar rai]

Hello,

We are delighted to inform you that 
*Codefest'11*, 
the *annual International online coding festival* of *Computer Engineering 
Society, IT-BHU*, has been unveiled. CodeFest is a unique fest wherein 
concepts of mathematics, logic, artificial intelligence, algorithms, 
language syntax, etc. are required to be deployed in programming; these 
concepts manifest themselves in solving problems effectively and 
efficiently! 

CodeFest was started last year. CodeFest'10 was a phenomenal success with 
participation from all over the globe. CodeFest'11 is geared up with some 
new and pepped up events, while maintaining the integrity of its 
standards.This year CodeFest has associated with 
*Technex'11*, 
the *annual all India Technical Festival of IT-BHU*, to expand its horizons. 


*Here is a brief description of the constituent online events:*

   - *Mathmania :* A 
   mathematical puzzle contest that puts mathematical and computational skills 
   to test. 
   - *Manthan :* An 
   algorithm intensive programming contest that would require coders to tailor 
   existing standard algorithms.
   - *Perplexed :*A 
programming contest, aimed to test the knowledge of C, wherein codes will 
   be rewarded against syntactic constraints. 
   - *Ratespiel :* A 
   technical contest covering different areas of Computer Science.
   - *Virtual Combat
   :* An educational game wherein teams of programmed robotic tanks will 
   fight the battles for glory. Codes Do Fight! Watch 
thisout. 
   
Visit our *website*  for more details.

*Few exciting statistics about Codefest'10:* 
   
   - 2354 registrations (including 128 professionals) from 680 different 
   institutions, across 59 countries 
   - Some participants were among the winners of Google Code Jam, Top Coder 
   SRMs and ACM ICPC 
   - Total prize money was a whopping amount of 260,000 INR! 
   - Codefest '10 was the largest online coding festival of the Indian 
   subcontinent in 2010 in terms of prize money!
   - Codefest'10 was the second largest online coding festival of the Indian 
   subcontinent in 2010, next to Bitwise
   - Gained recognition from several international organizations including 
   Codechef, Adobe, British Telecom, TCS and IEEE
   
The Codefest'11 team has set out to unleash a yet another coding 
extravaganza. We hope that your participation would raise the level of 
competition in Codefest'11. Feel free to contact us at codef...@itbhu.ac.inor 
reach us personally at: 
   
   - Mohit Bansal mohit.bansal.cs...@itbhu.ac.in 
   - Saket Saurabh saket.saurabh.cs...@itbhu.ac.in

We wish you all the best for Codefest'11 and for your future endeavours.

Happy coding, and be free!

Regards,
Team Codefest
Visit us at http://itbhu.ac.in/codefest 
Mail us at codef...@itbhu.ac.in
Check out our page at http://facebook.com/codefest
Follow us at http://twitter.com/c0defest/
Read our blog at http://itbhu.ac.in/codefest/blog 


 


-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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] Troika 2011, Annual technical fest of DTU

[Saikat Debnath]

Troika 2011, presents you with the Great AI Challenge "BOTS". A fun
filled and thrilling game where your codes will play against other
codes to pave their way to VICTORY.

Problem statements are announced, for more information and
registrations visit : troika.dcetech.com

Rulebook and sample files are available on : troika.dcetech.com/
BOTS.rar

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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] Sparse Matrix multiplication

[Rohit Saraf]

http://www.eecs.harvard.edu/~ellard/Q-97/HTML/root/node20.html

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] and or tree

[Rohit Saraf]

Of course memoization is needed (Can be done by using an array and the fact
that it is complete binary tree.)

Also if the later half of the array is all 0, then 1 cannot be obtained at
the root and vice versa.

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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 elements near the median

[Dave]

As described earlier, it can be done in O(n) independently of k.

1. Find the median, M: O(n)
2. Form a second array containing y(i) = abs(x(i) - M): O(n)
3. Find the kth smallest element of this array, K: O(n)
4. Scan the original array and locate the first k elements such that
abs(x(i) - M) <= K: O(n)

Total algorithm: O(n).

Dave

On Jan 27, 10:01 am, Jammy  wrote:
> I agree time should be O(kn)
>
> On Jan 26, 9:55 pm, Sharath Channahalli
>
>
>
>  wrote:
> > a) Find the median - O(n)
> > b) remove the element and again find the median
> > c) conitnue b until you get k-1 elements
>
> > time complexity - kO(n)
>
> > On Wed, Jan 26, 2011 at 9:55 PM, ritu  wrote:
>
> > > solution is nice!!but How to keep track of k closet numbers?
>
> > > On Jan 23, 9:22 pm, ritesh  wrote:
> > > > 1.) find x= median in o(n)
> > > > 2.) subtract x from each number of the array
> > > > 3.) find the k smallest number using o(n) algrithm
>
> > > > On Jan 21, 4:04 am, snehal jain  wrote:
>
> > > > > Given an unsorted array A of n distinct numbers and an integer k where
> > > > > 1 <= k <= n, design an algorithm that finds the k numbers in A that
> > > > > are closest in value to the median of A in O(n) time.
>
> > > --
> > > You received this message because you are subscribed to the Google Groups
> > > "Algorithm Geeks" group.
> > > To post to this group, send email to algogeeks@googlegroups.com.
> > > To unsubscribe from this group, send email to
> > > 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 algogeeks@googlegroups.com.
To unsubscribe from 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 elements near the median

[Jammy]

I agree time should be O(kn)

On Jan 26, 9:55 pm, Sharath Channahalli
 wrote:
> a) Find the median - O(n)
> b) remove the element and again find the median
> c) conitnue b until you get k-1 elements
>
> time complexity - kO(n)
>
> On Wed, Jan 26, 2011 at 9:55 PM, ritu  wrote:
>
> > solution is nice!!but How to keep track of k closet numbers?
>
> > On Jan 23, 9:22 pm, ritesh  wrote:
> > > 1.) find x= median in o(n)
> > > 2.) subtract x from each number of the array
> > > 3.) find the k smallest number using o(n) algrithm
>
> > > On Jan 21, 4:04 am, snehal jain  wrote:
>
> > > > Given an unsorted array A of n distinct numbers and an integer k where
> > > > 1 <= k <= n, design an algorithm that finds the k numbers in A that
> > > > are closest in value to the median of A in O(n) time.
>
> > --
> > You received this message because you are subscribed to the Google Groups
> > "Algorithm Geeks" group.
> > To post to this group, send email to algogeeks@googlegroups.com.
> > To unsubscribe from this group, send email to
> > 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: Doubt regarding Pointers in C......

[Jammy]

call it by reference.

bst *rec = Null;
insert(rec,5);

void insert(bst *&rec,int data){rec->data = data;}

Or declare it as
void insert(bst **rec,int data){*rec->data = data;}
and invoke with insert(&rec,5);

First one is just syntactic sugar to me although you can argue about
the whole pass-by-value/ref/pointer thing for hours. :)

On Jan 27, 8:03 am, nishaanth  wrote:
> How can we pass pointers by value. Lets say even if it creates a copy of the
> pointer.
> The address stored by the pointer is the same. So when we dereference it
> shouldnt it get updated(as its just a memory address)?
>
>
>
> On Thu, Jan 27, 2011 at 5:39 PM, ritu  wrote:
> > Here you are passing record pointer by value.
>
> > as you call insert(record, 5),stack frame of insert contains a copy
> > of  record.after this value is modified by calling program,it should
> > be either returned explicitly to caller program or needs to be passed
> > by reference,so that calling program refers to it always by address.
>
> > On Jan 27, 4:17 pm, nishaanth  wrote:
> > > Hi guys,
>
> > > I have a small doubt regarding pointers and functions.
>
> > > Consider the following prototype
>
> > > void insert(bst * head, int data);
>
> > > This function creates a node and inserts the data in the node. Lets say i
> > > call this function iteratively from main.
>
> > > main(){
>
> > > bst* record=NULL;
> > > insert(record, 5);
> > > insert(record, 8);
>
> > > }
>
> > > I see that record is not getting modified. Now is this related to call by
> > > value. But since we are passing pointers shouldnt the change get
> > reflected
> > > in main.
> > > isnt is similar to passing an array?
> > > Enlighten me in this regard. I am tired of segfaults :(
>
> > > Regards,
> > > S.Nishaanth,
> > > Computer Science and engineering,
> > > IIT Madras.
>
> > --
> > You received this message because you are subscribed to the Google Groups
> > "Algorithm Geeks" group.
> > To post to this group, send email to algogeeks@googlegroups.com.
> > To unsubscribe from this group, send email to
> > algogeeks+unsubscr...@googlegroups.com
> > .
> > For more options, visit this group at
> >http://groups.google.com/group/algogeeks?hl=en.
>
> --
> S.Nishaanth,
> Computer Science and engineering,
> IIT Madras.

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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] and or tree

[Rohit Saraf]

Let
No of flips reqd  = solve(N, V)
L=left subtree.
R = right subtree
N = root node.

If V=0, then
   only problem is when L = 1 and R=1.  (otherwise atmax changing the root
node will do)
   then ans = min(solve(L, 0), solve(R,0)) + (R=AND)?0:1

If V=1 then
   only problem is when L=0 and R=0
   similarly dealt.

If V=something else
   output -1

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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: zig zag

[bittu]

well I found it  as it  Can be Done in O(n). but with additional space
O(n)
here program is written in Java

public class ZigZag
{


 public int longestZigZag(int[] sequence)
  {
  if (sequence.length==1) return 1;
  if (sequence.length==2) return 2;
  int[] diff = new int[sequence.length-1];

  for (int i=1;ihttp://groups.google.com/group/algogeeks?hl=en.

[algogeeks] Re: Prime Numbers

[alexsolo]

#include 
#include 
#include 

#define MAX 15485863
#define LMT 100

unsigned flag[MAX>>6];

#define ifc(n) (flag[n>>6]&(1<<((n>>1)&31)))
#define isc(n) (flag[n>>6]|=(1<<((n>>1)&31)))

void sieve() {
unsigned i, j, k;
for(i=3; i>6);
}

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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] and or tree

[snehal jain]

given a complete binary tree (either a node is a leaf node or has two
children)
every leaf node has value 0 or 1.
every internal node has value as the AND gate or OR gate.
you are given with the tree and a value V.
you have to output the minimum number of flips (AND to OR or OR to
AND) if the evaluated value is not equal to V, if it is equal return
0, if not possible return -1.
you can just change the value of internal nodes i.e can make and to
or , or to and to get the desired output
give the minimum number of flips required to get the desired 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: Building A Special Tree

[bittu]

Please Try to Correct it Its Showing Segmentation fault...Reply
ASAP...
its code for the above program might be not designed in same
way...what question..asking ..but i tried..itTry to make is Clear
& Executable ...


consider tree below

 1
 /  \
1  0
   /  \  /   \
  1   0   10
  / \  /   \
00   00


#include 
#include 

/* A binary tree node has data, pointer to left child
   and a pointer to right child */
struct node
{
 int data;
 struct node* left;
 struct node* right;
};

/* Given a binary tree, print its nodes in inorder*/
void printPreorder(struct node* node)
{
 if (node == NULL)
  return;

 /* first print data of node */
 printf("%d ", node->data);

 /* then recur on left sutree */
 printPreorder(node->left);

 /* now recur on right subtree */
 printPreorder(node->right);
}

struct node* newNode(int data)
{
  struct node* node = (struct node*)
   malloc(sizeof(struct node));
  node->data = data;
  node->left = NULL;
  node->right = NULL;

  return(node);
}


struct node* build_CBT(struct node *root)
{
   struct node *node=root;

   if(node==NULL)
   { printf(" Special Tree Yes");
  return;
   }

  if(node!=NULL)
  {  node->data=newNode(1);

   if(node->left ==NULL && node->right==NULL)
   {  node->left->data=node->right->data=newNode(0);
  return;
   }
  }
   else
{

  if(node->left!=NULL)
  {
 //node->left->data=N;
 build_CBT(node->left);
   }
  if(node->right!=NULL)
   {

  //put(node->right->data=N;
 build_CBT(node->right);
   }


}

 return node;
}

/*Driver program to test above functions*/
int main()
{
  /*create a tree*/
  struct node *root=(struct node *)malloc(sizeof(struct node)*9);

  root=build_CBT(root);

  printPreorder(root);


  getchar();
  return 0;
}

Thanks & Regards
Shashank Mani  "The Best Way To Escape From The Problem is to Solve 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.

Re: [algogeeks] Re: Doubt regarding Pointers in C......

[nishaanth]

How can we pass pointers by value. Lets say even if it creates a copy of the
pointer.
The address stored by the pointer is the same. So when we dereference it
shouldnt it get updated(as its just a memory address)?

On Thu, Jan 27, 2011 at 5:39 PM, ritu  wrote:

> Here you are passing record pointer by value.
>
> as you call insert(record, 5),stack frame of insert contains a copy
> of  record.after this value is modified by calling program,it should
> be either returned explicitly to caller program or needs to be passed
> by reference,so that calling program refers to it always by address.
>
>
> On Jan 27, 4:17 pm, nishaanth  wrote:
> > Hi guys,
> >
> > I have a small doubt regarding pointers and functions.
> >
> > Consider the following prototype
> >
> > void insert(bst * head, int data);
> >
> > This function creates a node and inserts the data in the node. Lets say i
> > call this function iteratively from main.
> >
> > main(){
> >
> > bst* record=NULL;
> > insert(record, 5);
> > insert(record, 8);
> >
> > }
> >
> > I see that record is not getting modified. Now is this related to call by
> > value. But since we are passing pointers shouldnt the change get
> reflected
> > in main.
> > isnt is similar to passing an array?
> > Enlighten me in this regard. I am tired of segfaults :(
> >
> > Regards,
> > S.Nishaanth,
> > Computer Science and engineering,
> > IIT Madras.
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>


-- 
S.Nishaanth,
Computer Science and engineering,
IIT Madras.

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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: Google Question

[ritu]

Following is the algorithm to get max number of A's .
it gives number = 20 for n=10


set buff = 0


call get_max(n)


int get_max(int i)
{
if (i>=1 && i<=3)
{
n[i] = i
m[i] = 'A'
return n[i]
  }
  else
{
   num_A = getmax(i-3);
   max= MAX(num_A+3,2*num_A, num_A+3*buff)
   n[i] = max


if max == 2*num_A
 m[i-2] = ctrl-A , m[i-1]=ctrl-C ,m[i-2] = ctrl-V
 buff = num_A
if (max == num_A + 3*buff)
   m[i]=m[i-1]=m[i-2]='ctrl-v'
else if (max == num_A + 3)
  m[i]=m[i-1]=m[i-2]='A'


 return n[i]
}
return
}


-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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: Google Question

[ritu]

Following is the algorithm to get max number of A's .
it gives number = 20 for n=10

set buff = 0

call get_max(n)

int get_max(int i)
{
if (i>=1 && i<=3)
{
n[i] = i
m[i] = 'A'
return n[i]
  }
  else
{
   num_A = getmax(i-3);
   max= MAX(num_A+3,2*num_A, num_A+3*buff)
   n[i] = max

if max == 2*num_A
 m[i-2] = ctrl-A , m[i-1]=ctrl-C ,m[i-2] = ctrl-V
 buff = num_A
if (max == num_A + 3*buff)
   m[i]=m[i-1]=m[i-2]='ctrl-v'
else if (max == num_A + 3)
  m[i]=m[i-1]=m[i-2]='A'

 return n[i]
}
return
}

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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: Puzzle

[sunny agrawal]

another one
9*(1+ 1/9)

On Thu, Jan 27, 2011 at 5:40 PM, nhkrishna2...@yahoo.com <
nhkrishna2...@gmail.com> wrote:

> 9+1+1/9
>
>
>
> On Jan 27, 4:43 pm, ankit agarwal  wrote:
> > (9*9-1)/(9-1)
> >
> >
> >
> > On Thu, Jan 27, 2011 at 4:55 PM, nishaanth 
> wrote:
> > > (91-1)/9
> >
> > > On Wed, Jan 26, 2011 at 11:07 PM, Apoorve Mohan <
> apoorvemo...@gmail.com>wrote:
> >
> > >> 9 + 1 - ( 1 / 9 )
> >
> > >> On Wed, Jan 26, 2011 at 10:29 PM, satish 
> wrote:
> >
> > >>> 19-(9/1).
> >
> > >>>  --
> > >>> You received this message because you are subscribed to the Google
> Groups
> > >>> "Algorithm Geeks" group.
> > >>> To post to this group, send email to algogeeks@googlegroups.com.
> > >>> To unsubscribe from 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
> >
> > >> 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 algogeeks@googlegroups.com.
> > >> To unsubscribe from this group, send email to
> > >> algogeeks+unsubscr...@googlegroups.com
> 
> >
> > >> .
> > >> For more options, visit this group at
> > >>http://groups.google.com/group/algogeeks?hl=en.
> >
> > > --
> > > S.Nishaanth,
> > > Computer Science and engineering,
> > > IIT Madras.
> >
> > >  --
> > > You received this message because you are subscribed to the Google
> Groups
> > > "Algorithm Geeks" group.
> > > To post to this group, send email to algogeeks@googlegroups.com.
> > > To unsubscribe from this group, send email to
> > > algogeeks+unsubscr...@googlegroups.com
> 
> >
> > > .
> > > For more options, visit this group at
> > >http://groups.google.com/group/algogeeks?hl=en.
> >
> > --
> > Ankit Agarwal
> > B.Tech. 3rd Year
> > Computer Science & Engineering
> > IIT Rajasthan
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from 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.

Re: [algogeeks] Re: Amazon Question

[Ritu Garg]

solution is not too hard to understand!!
1. [quote] For every none leaf node , go to the last node in it's left
subtree and mark the right child of that node as x [\quote]. How are
we going to refer to the right child now ??We have removed it's
reference now !!

last node in left sub tree of any node always have right pointer as NULL
because this is the last node

2. It is to be repeated for every node except the non leaf nodes . This
will take O(n*n) time in worst case , say a leftist tree with only
left pointers . root makes n-1 traversals , root's left subtree's root
makes n-2 , and so on.
i said that it ll take O(n) time for well balanced tree.
for a node at height h ,it takes O(h) to fill this node as successor of some
other node.if combined for all sum(O(h)) h=1 to lg n ..total time ll come as
O(n)

3. Take the case below .

   1
  2 3
1  1.5   2.5   4

for node 2 , you will go to 1 , which is the successor of 2 , you make
2->right=1  but what about node 1.5 ???
same is the case with node 3 ... 3->right=2.5 . How will we refer to 4
now ??

when you ll process node 1,it ll be filled in as right child of 1.5
there is no successor for 4.

In Brief

1. Convert the tree to right threaded binary tree.means all right children
point to their successors.
it ll take no additional space.ll take O(n) time if tree is well balanced

2. Do inorder traversal to find ith element without using extra space
because succssor of each node is pointed by right child.

i hope you got it now!!







On Wed, Jan 26, 2011 at 5:31 PM, sankalp srivastava <
richi.sankalp1...@gmail.com> wrote:

> I don't seem to understand ur solution .
> [quote] For every none leaf node , go to the last node in it's left
> subtree and mark the right child of that node as x [\quote]. How are
> we going to refer to the right child now ??We have removed it's
> reference now !!
>
> It is to be repeated for every node except the non leaf nodes . This
> will take O(n*n) time in worst case , say a leftist tree with only
> left pointers . root makes n-1 traversals , root's left subtree's root
> makes n-2 , and so on.
>
> Go to the largest node in the left subtree .This means go to the left
> subtree and keep on going to the right until it becomes null  , in
> which case  , you make y->right as x . This means effectively , that y
> is the predecessor of x , in the tree . Considering a very good code ,
> it may take O(1) space , but you will still need additional pointers.
> Take the case below .
>
>1
>   2 3
> 1  1.5   2.5   4
>
> for node 2 , you will go to 1 , which is the successor of 2 , you make
> 2->right=1  but what about node 1.5 ???
> same is the case with node 3 ... 3->right=2.5 . How will we refer to 4
> now ??
>
> Now using inorder traversal with a count , I will start at 1->left , 2-
> >left = 1 , then 2 ... then 2->right = 1 again . then 1 , and then 1-
> >right=3 ...clearly , this will not give us a solution .
> A reverse inorder looks just fine to me .
>
> On Jan 26, 3:14 pm, Ritu Garg  wrote:
> > @Algoose
> >
> > I said ..*.For every node x,go to the last node in its left subtree and
> mark
> > the right child of that node as x.*
> >
> > it is to be repeated for all nodes except leaf nodes.
> > to apply this approach ,you need to go down the tree.No parent pointers
> > required.
> > for every node say x whose left sub tree is not null ,go to the largest
> node
> > in left sub-tree say y.
> > Set  y->right = x
> > y is the last node to be processed in left sub-tree of x hence x is
> > successor of y.
> >
> >
> >
> > On Wed, Jan 26, 2011 at 3:27 PM, Algoose chase 
> wrote:
> > > @ritu
> > > how would you find a successor without extra space if you dont have a
> > > parent pointer ?
> > > for Instance from the right most node of left subtree to the parent of
> left
> > > subtree(root) ?
> > > @Juver++
> > > Internal stack does count as extra space !!
> >
>  > > On Wed, Jan 26, 2011 at 3:02 PM, ritu 
> wrote:
> >
> > >> No,no extra space is needed.
> > >> Right children which are NULL pointers are replaced with pointer to
> > >> successor.
> >
> > >> On Jan 26, 1:18 pm, nphard nphard  wrote:
> > >> > If you convert the given binary tree into right threaded binary
> tree,
> > >> won't
> > >> > you be using extra space while doing so? Either the given tree
> should
> > >> > already be right-threaded (or with parent pointers at each node) or
> > >> internal
> > >> > stack should be allowed for recursion but no extra space usage apart
> > >> from
> > >> > that.
> >
> > >> > On Wed, Jan 26, 2011 at 3:04 AM, ritu 
> wrote:
> > >> > > it can be done in O(n) time using right threaded binary tree.
> > >> > > 1.Convert the tree to right threaded tree.
> > >> > > right threaded tree means every node points to its successor in
> > >> > > tree.if right child is not NULL,then it already contains a pointer
> to
> > >> > > its successor Else it needs to filled up as following
> > >> > >  a. For every no

[algogeeks] Re: Google Question

[ritu]

Following is the algorithm to ger max number of A's

set n[0] = 0

int get_max(int 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: Puzzle

[nhkrishna2...@yahoo.com]

9+1+1/9



On Jan 27, 4:43 pm, ankit agarwal  wrote:
> (9*9-1)/(9-1)
>
>
>
> On Thu, Jan 27, 2011 at 4:55 PM, nishaanth  wrote:
> > (91-1)/9
>
> > On Wed, Jan 26, 2011 at 11:07 PM, Apoorve Mohan 
> > wrote:
>
> >> 9 + 1 - ( 1 / 9 )
>
> >> On Wed, Jan 26, 2011 at 10:29 PM, satish  wrote:
>
> >>> 19-(9/1).
>
> >>>  --
> >>> You received this message because you are subscribed to the Google Groups
> >>> "Algorithm Geeks" group.
> >>> To post to this group, send email to algogeeks@googlegroups.com.
> >>> To unsubscribe from 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
>
> >> 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 algogeeks@googlegroups.com.
> >> To unsubscribe from this group, send email to
> >> algogeeks+unsubscr...@googlegroups.com
> >> .
> >> For more options, visit this group at
> >>http://groups.google.com/group/algogeeks?hl=en.
>
> > --
> > S.Nishaanth,
> > Computer Science and engineering,
> > IIT Madras.
>
> >  --
> > You received this message because you are subscribed to the Google Groups
> > "Algorithm Geeks" group.
> > To post to this group, send email to algogeeks@googlegroups.com.
> > To unsubscribe from this group, send email to
> > algogeeks+unsubscr...@googlegroups.com
> > .
> > For more options, visit this group at
> >http://groups.google.com/group/algogeeks?hl=en.
>
> --
> Ankit Agarwal
> B.Tech. 3rd Year
> Computer Science & Engineering
> IIT Rajasthan

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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: Doubt regarding Pointers in C......

[ritu]

Here you are passing record pointer by value.

as you call insert(record, 5),stack frame of insert contains a copy
of  record.after this value is modified by calling program,it should
be either returned explicitly to caller program or needs to be passed
by reference,so that calling program refers to it always by address.


On Jan 27, 4:17 pm, nishaanth  wrote:
> Hi guys,
>
> I have a small doubt regarding pointers and functions.
>
> Consider the following prototype
>
> void insert(bst * head, int data);
>
> This function creates a node and inserts the data in the node. Lets say i
> call this function iteratively from main.
>
> main(){
>
> bst* record=NULL;
> insert(record, 5);
> insert(record, 8);
>
> }
>
> I see that record is not getting modified. Now is this related to call by
> value. But since we are passing pointers shouldnt the change get reflected
> in main.
> isnt is similar to passing an array?
> Enlighten me in this regard. I am tired of segfaults :(
>
> Regards,
> S.Nishaanth,
> Computer Science and engineering,
> IIT Madras.

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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: Microsoft Written Test Questions

[Rahul Menon]

This time MS rather than conducting the written tests by itself has
outsourced the procedure to MERITTRAC Services to be conducted to jan
30th, So unlike the regular 6 questions type written test , it will be
replaced by MCQs which is the regular pattern of merittrac tests
[think so] . From a bit googling I came to know that these people put
lot of repeated questions and each time and if we can get questions
from previously conducted tests of  MS , it can be very helpful.

So the ones with experience with merritrac tests here ,can do a lot
help,

I would also like to know about the pattern or topics they usually
test. And also sample questions



Regards,

Rahul

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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: Building A Special Tree

[Devil_Fish]

Taking a Wild Stab at this problem:

This is like evaluating a prefix expression.

We know that an expression tree also has either 0 or 2 children and
the internal nodes are operators and leaf nodes are operands.

In a prefix expression we try to look for the pattern
"". If we find such a thing we evaluate it
and put a placeholder for it in the string.

Similarly for this, we look for the pattern NXX. where X is either L
or a placeholder for a partially constructed tree. Construct the tree
and replace in place of NXX a placeholder like L'. Repeat this and you
will have a tree.

Consider the following tree(Same from above comment)

N
/ \
N N
/ \ / \
N L N L
/ \ / \
L L L L
Prefix expression is
NNNLLLNNLLL
1st NXX pattern is:

NN(NLL)LNNLLL construct a tree for it and replace in the String as L'
to get NNL'LNNLLL

2nd NXX:

N(NL'L)NNLLL =>NL'NNLLL

3rd NXX:
NL'N(NLL)L => NL'NL'L

4th NXX
NL'(NL'L) => NL'L' (Final result)

Basically we are constructing the tree in a bottom up fashion.


On Jan 14, 10:20 am, Decipher  wrote:
> A special type of tree is given, where all leaf are marked with L and others
> are marked with N. every node can have 0 or at most 2 nodes. Trees preorder
> traversal is given give a algorithm to build tree from this traversal.

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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] Puzzle

[ankit agarwal]

(9*9-1)/(9-1)

On Thu, Jan 27, 2011 at 4:55 PM, nishaanth  wrote:

> (91-1)/9
>
>
> On Wed, Jan 26, 2011 at 11:07 PM, Apoorve Mohan wrote:
>
>> 9 + 1 - ( 1 / 9 )
>>
>>
>> On Wed, Jan 26, 2011 at 10:29 PM, satish  wrote:
>>
>>> 19-(9/1).
>>>
>>>  --
>>> You received this message because you are subscribed to the Google Groups
>>> "Algorithm Geeks" group.
>>> To post to this group, send email to algogeeks@googlegroups.com.
>>> To unsubscribe from 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
>>
>> 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 algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com
>> .
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
>
>
> --
> S.Nishaanth,
> Computer Science and engineering,
> IIT Madras.
>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>



-- 
Ankit Agarwal
B.Tech. 3rd Year
Computer Science & Engineering
IIT Rajasthan

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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] Puzzle

[nishaanth]

(91-1)/9

On Wed, Jan 26, 2011 at 11:07 PM, Apoorve Mohan wrote:

> 9 + 1 - ( 1 / 9 )
>
>
> On Wed, Jan 26, 2011 at 10:29 PM, satish  wrote:
>
>> 19-(9/1).
>>
>>  --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from 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
>
> 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 algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>



-- 
S.Nishaanth,
Computer Science and engineering,
IIT Madras.

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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] Doubt regarding Pointers in C......

[rahul]

pass a address of pointer.

void insert(bst **head, int data);

call it using insert(&record,8).

try this.
On Thu, Jan 27, 2011 at 4:47 PM, nishaanth  wrote:

> Hi guys,
>
> I have a small doubt regarding pointers and functions.
>
> Consider the following prototype
>
> void insert(bst * head, int data);
>
> This function creates a node and inserts the data in the node. Lets say i
> call this function iteratively from main.
>
> main(){
>
> bst* record=NULL;
> insert(record, 5);
> insert(record, 8);
>
> }
>
> I see that record is not getting modified. Now is this related to call by
> value. But since we are passing pointers shouldnt the change get reflected
> in main.
> isnt is similar to passing an array?
> Enlighten me in this regard. I am tired of segfaults :(
>
>
> Regards,
> S.Nishaanth,
> Computer Science and engineering,
> IIT Madras.
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Microsoft Written Test Questions

[Ankit Babbar]

http://www.cracktheinterview.org/category/company-wise/microsoft/

but these are all subjective type...need MCQ's..!!

On Thu, Jan 27, 2011 at 9:39 AM, Umer Farooq  wrote:

> Hi there, can you share some of the Microsoft phone interview questions.?
>
> On Thu, Jan 27, 2011 at 6:47 AM, Ankit Babbar wrote:
>
>> Hey all...Can anyone provide me with the recent (/most common) written
>> test questions(or links ) of Microsoft IDC and Microsoft IT SDE
>> positions...??
>>
>> Thanks in advance..
>>
>> Regards,
>> Ankit.
>>
>>
>>
>>  --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com
>> .
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
>
>
> --
> Umer
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from 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,
Ankit Babbar
BE-IVth yr,
Computer Science,
Thapar University,
Patiala.

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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] Doubt regarding Pointers in C......

[nishaanth]

Hi guys,

I have a small doubt regarding pointers and functions.

Consider the following prototype

void insert(bst * head, int data);

This function creates a node and inserts the data in the node. Lets say i
call this function iteratively from main.

main(){

bst* record=NULL;
insert(record, 5);
insert(record, 8);

}

I see that record is not getting modified. Now is this related to call by
value. But since we are passing pointers shouldnt the change get reflected
in main.
isnt is similar to passing an array?
Enlighten me in this regard. I am tired of segfaults :(


Regards,
S.Nishaanth,
Computer Science and engineering,
IIT Madras.

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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] Microsoft Written Test Questions

[Umer Farooq]

Hi there, can you share some of the Microsoft phone interview questions.?

On Thu, Jan 27, 2011 at 6:47 AM, Ankit Babbar wrote:

> Hey all...Can anyone provide me with the recent (/most common) written test
> questions(or links ) of Microsoft IDC and Microsoft IT SDE positions...??
>
> Thanks in advance..
>
> Regards,
> Ankit.
>
>
>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>



-- 
Umer

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.