JIGYASA

An online placement forum.


You are not connected. Please login or register

maximum and minimum!

Go down  Message [Page 1 of 1]

1 maximum and minimum! on Wed Apr 21, 2010 5:48 am

Suppose you are given a tree with n nodes.

Now let e define some terms for you:
depth of a tree: number of levels in the tree
breadth of a tree: maximum number of nodes at any level.

Now for any tree what is the maximum value of the function min(depth,breadth)?

View user profile

2 A more involved question! on Mon Apr 26, 2010 7:51 am

My previous question is actually not a very difficult problem to solve if you sit down to analyze for a while. Forget that question for a while. I will ask it again when the time comes. What I am going to do in this thread is to take you towards understanding a difficult problem progressively! SO I am waiting for your answers to take you to the next level! We will end up solving a problem for parallel processing. So algorithm freaks here we go

Suppose you are given any tree.

All you have to do is what is known as upward accumulation! For the ease of understanding lets take addition as the operation. So, every leaf node in the tree is given a weight.
1. The accumulation at leaf node is nothing but the weight of the node itself.
2. The accumulation at every other node is the sum of weights of all nodes in its subtree for which it is the root!

A solution to this is very easy! I am expecting the answer soon. No need of giving me an implementation. Just share your idea Smile. First lets start with a uni-processor system!



Last edited by indranil on Mon Apr 26, 2010 7:52 am; edited 1 time in total (Reason for editing : grammar)

View user profile

3 Re: maximum and minimum! on Sun Jul 18, 2010 6:12 am

assuming it to be a N-ary tree...

struct node
{
int weight;
struct node * children[N];
};

int totalAcmOfNode( node * root)
{
int totalAcm = 0;

if (root != NULL)
{
for ( int i=0; i<N; ++i)
totalAcm += totalAcmOfNode(root->children[i]);

total += root->weight;
}

return totalAcm;
}

View user profile

Sponsored content


Back to top  Message [Page 1 of 1]

Permissions in this forum:
You cannot reply to topics in this forum