Gate 2010 Algo solutions

Q.1. Let G=(V, E) be a graph. Define $\xi(G) = \sum\limits_d i_d*d$, where $i_d$ is the number of vertices of degree d in G. If S and T are two different trees with $\xi(S) = \xi(T)$, then
(A) |S| = 2|T|   (B) |S| = |T| - 1   (C) |S| = |T|   (D) |S| = |T| + 1

Sol : $\xi(G)$ basically is the sum of degrees of all vertices in a graph. If sum of degrees of two different trees are same, then number of nodes in the trees has to be same. We prove this by induction on sum of degree of all vertices in the two trees.

• Base case : When $\xi(S) = \xi(T) = 1$, then we have only single node in both trees and hence |S| = |T|.
• Induction hypothesis : Assume, for $\xi(S) = \xi(T) = k$, we have |S| = |T|.
• Induction step : For $\xi(S) = \xi(T) = k+1$, we must add a leaf vertex in both trees, and hence |S| = |T|.

Q.10. In a  binary tree with $n$ nodes, every node has an odd number of descendants. Every node is considered to be its own descendant. What is the number of nodes in the tree that have exactly one child?

(A) $0$

(B) $1$

(C) $\frac{(n-1)}{2}$

(D) $n-1$

Sol : Suppose a node $n$ contains exactly one child, then that child must have odd number of descendants (since it is given in the question that every node has odd number of descendants), but then $n$ has an even number of descendants (all descendants of its child + node $n$ itself), which is not possible. So Answer is $0$ i.e. option (A).

Q.11 What does the following program print?

#include<stdio.h>

void f(int *p, int *q) {
    p=q;
    *p=2;
}

int i=0, j=1;

int main() {
    f(&i, &j);
    printf("%d %d\n", i,j);
    return 0;
}

(A) $max(Y, a_0+Y)$

(B) $max(Y, a_0+Y/2)$

(C) $max(Y, a_0 +2Y)$

(D) $a_0+Y/2$

To Be Continued....