GATE Breaker

In a class of 200 students, 125 students have taken Programming Language course, 85 students have taken Data Structures course, 65 students have taken Computer Organization course, 50 students have taken both Programming Language and Data Structures, 35 students have taken both Data Structures and Computer Organization 30 students have taken both Data Structures and Computer Organization, 15 students have taken all the three courses. How many students have not taken any of the three courses? (A) 15  (B) 20  (C) 25  (D) 35  (GATE 2004)  Answer: (C) 25  Explanation:  Let $P$, $D$ and $C$ be the sets of students taking programming language, data structure and computer organization courses, respectively.  Here, $n(P) = 125$, $n(D) = 85$, $n(C) = 65$, $n(P \cap D) = 50$, $n(P \cap C) = 35$, $n(D \cap C) = 30$ and $n(P \cap D \cap C) = 15$  [$n(X)$ denotes the number of elements present in the set $X$.]  Now, $n(P \cup D \cup C)$  $= n(P)...

How many distinct binary search trees can be created out of 4 distinct keys?  (GATE 2005)  (A) 5  (B) 14   (C) 24   (D) 42  Answer: (B) 14  Explanation:  Here, number of keys, $k = 4$.  Therefore, the number of distinct binary search trees that can be formed out of 4 distinct keys is  $= \dfrac{^{2k}C_k}{k + 1}$  $ = \dfrac{^{8}C_4}{5}$  $= 14$ 

How many substrings of different lengths (non-zero) can be found formed from a character string of length $n$? (A) $n$,  (B) $n^2$,  (C) $\frac{n(n - 1)}{2}$,  (D) $\frac{n(n + 1)}{2}$.  (GATE 1994)  Answer: (D) $\frac{n(n + 1)}{2}$.   Explanation:  The given string has length $n$.  No. of substrings of length $n = 1$  No. of substrings of length $n - 1 = 2$  $\cdots \cdots \cdots \cdots \cdots \cdots$  $\cdots \cdots \cdots \cdots \cdots \cdots$  No. of substrings of length $1 = n$  Therefore, the total number of substrings  $= 1 + 2 + \cdots + n$  $= \frac{n(n + 1)}{2}$. 

We need to choose a team of 11 from a pool of 15 players and also select a captain. Find the number of different ways this can be done.  (A) $\binom{15}{11}$,  (B) $11 \times \binom{15}{11}$,  (C) $15 \times 14 \times \cdots \times 5$,  (D) $(15 \times 14 \times \cdots \times 5) \times 11$.  Answer: (B) $11 \times \binom{15}{11}$  Explanation:  Number of ways of selecting a captain from 15 players  = $\binom{15}{1}$.  Remaining players in the pool $= 15 - 1  = 14$, and the remaining number of players to be chosen $= 11 - 1 = 10$.  Number of ways of selecting 10 players from a pool of 14 players = $\binom{14}{10}$.  Therefore, the total number of different ways of selecting 11 players from a pool of 15 players and also select a captain is  $= \binom{15}{1} \times \binom{14}{10}$  $= 15 \times \frac{14 \times 13 \times 12 \times 11 \times 10!}{4! \times 10!}$  $= \frac{15 \times 14 \times 13 \times 12 \times 11!}{4...

How many undirected graphs (not necessarily connected) can be constructed out of a given set $V = \{v_1, v_2, \ldots, v_n\}$ of $n$ vertices? (GATE 2001) (A) $\frac{n(n-1)}{2}$, (B) $2^n$, (C) $n!$, (D) $2^{\frac{n(n-1)}{2}}$  Answer: (D) $2^{\frac{n(n-1)}{2}}$  Explanation:  Here, number of vertices = $n$.  Therefore, $^nC_2 = \frac{n(n-1)}{2}$ number of edges can be formed.  Now, each subset of these edges can form an undirected graph (not necessarily connected).  Therefore, total $2^{\frac{n(n-1)}{2}}$ number of graphs can be formed.  Next Post