Recent questions tagged tifr2015

Consider the following grammar (the start symbol is $E$) for generating expressions.$E \rightarrow T - E \mid T + E \mid T$$T \rightarrow T * F \mid F$$F \rightarrow 0 \m...

Consider the following concurrent program (where statements separated by | | with-in cobegin-coend are executed concurrently).x:=1 cobegin x:= x + 1 || x:= x + 1 || x:=...

Let $t_{n}$ be the sum of the first $n$ natural numbers, for $n 0$. A number is called triangular if it is equal to $t_{n}$ for some $n$. Which of the following statemen...

Let $K_{n}$ be the complete graph on $n$ vertices labeled $\left\{1, 2,\dots ,n\right\}$ with $m=\frac{n (n - 1)}{2}$ edges. What is the number of spanning trees of $K_{n...

Consider the languages $L_{1}= \left\{a^{m}b^{n}c^{p} \mid (m = n \vee n = p) \wedge m + n + p \geq 10\right\}$$L_{2}= \left\{a^{m}b^{n}c^{p} \mid (m = n \vee n = p) \wed...

A Boolean expression is an expression made out of propositional letters (such as $p, q, r$) and operators $\wedge$, $\vee$ and $\neg$; e.g. $p\wedge \neg (q \vee \neg r)$...

Let $\sum_{1}= \left\{a\right\}$ be a one letter alphabet and $\sum_{2}= \left\{a, b\right\}$ be a two letter alphabet. A language over an alphabet is a set of finite len...

Let $a, b, c$ be regular expressions. Which of the following identities is correct?$(a + b)^{*} = a^{*}b^{*}$$a(b + c) = ab + c$$(a + b)^{*} = a^{*} + b^{*}$$(ab + a)^{*}...

Let $B$ consist of all binary strings beginning with a $1$ whose value when converted to decimal is divisible by $7$.$B$ can be recognized by a deterministic finite state...

Suppose $\begin{pmatrix}0&1 &0&0&0&1 \\1&0&1&0&0&0 \\0&1&0&1&0&1 \\0&0&1&0&1&0 \\0&0&0&1&0&1 \\1&0&1&0&1&0\end{pmatrix}$is the adjacency matrix of an undirected graph...

First, consider the tree on the left. On the right, the nine nodes of the tree have been assigned numbers from the set $\left\{1, 2,\ldots,9\right\}$ so that for every ...

Consider the following code fragment in the $C$ programming language when run on a non-negative integer $n$.int f (int n) { if (n==0 || n==1) return 1; else return f (n -...

Consider the following undirected connected graph $G$ with weights on its edges as given in the figure below. A minimum spanning tree is a spanning tree of least weight a...

Consider the following recurrence relation:$T(n)= \begin{cases}2T (\lfloor\sqrt{n}\rfloor)+ \log n & \text{if }n \geq 2 \\ 1& \text{if }n = 1 \end{cases}$Which of the...

Let $A$ and $B$ be non-empty disjoint sets of real numbers. Suppose that the average of the numbers in the first set is $\mu_{A}$ and the average of the numbers in the se...

Consider the following $3 \times 3$ matrices.$M_{1}=\begin{pmatrix} 0&1&1 \\1&0&1 \\1&1&0 \end{pmatrix} $$M_{2}=\begin{pmatrix} 1&0&1 \\0&0&0 \\1&0&1 \end{pmatrix} ...

Imagine the first quadrant of the real plane as consisting of unit squares. A typical square has $4$ corners: $(i, j), (i+1, j), (i+1, j+1),$and $(i, j+1)$, where $(i, j)...

Consider a square of side length $2$. We throw five points into the square. Consider the following statements:There will always be three points that lie on a straight lin...

There is a set of $2n$ people: $n$ male and $n$ female. A good party is one with equal number of males and females (including the one where none are invited). The total n...

A $1 \times 1$ chessboard has one square, a $2 \times 2$ chessboard has five squares. Continuing along this fashion, what is the number of squares on the regular $8 \time...

Ram has a fair coin, i.e., a toss of the coin results in either head or tail and each event happens with probability exactly half $(1/2)$. He repeatedly tosses the coin u...

What is logically equivalent to "If Kareena and Parineeti go to the shopping mall then it is raining":If Kareena and Parineeti do not go to the shopping mall then it is n...

The Boolean function obtained by adding an inverter to each and every input of an $\text{AND}$ gate is:$\text{OR}$$\text{XOR}$$\text{NAND}$$\text{NOR}$None of the above

Let $|z| < 1$. Define $M_{n}(z)= \sum_{i=1}^{10} z^{10^{n}(i - 1)}?$ what is $\prod\limits_{i=0}^{\infty} M_{i}(z)= M_{0}(z)\times M_{1}(z) \times M_{2}(z) \t...

Consider a circle with a circumference of one unit length. Let $d< \dfrac{1}{6}$. Suppose that we independently throw two arcs, each of length $d$, randomly on this circu...

Consider a $6$-sided die with all sides not necessarily equally likely such that probability of an even number is $P (\left \{2, 4, 6 \right \}) =\dfrac{1}{2}$, probabil...