Login
Register
Dark Mode
Brightness
Profile
Edit Profile
Messages
My favorites
My Updates
Logout
Filter
Profile
Wall
Recent activity
All questions
All answers
Exams Taken
All Blogs
Recent activity by tarun_svbk
2
answers
1
TIFR CSE 2017 | Part B | Question: 7
An array of $n$ distinct elements is said to be un-sorted if for every index $i$ such that $ 2 \leq i \leq n-1$, either $A[i] > \text{max} \{A [i-1], A[i+1]\}$, or $A[i] < \text{min} \{A[i-1], A[i+1]\}$. What is the time-complexity of the fastest ... $O(n)$ but not $O(\sqrt{n})$ $O(\sqrt{n})$ but not $O(\log n)$ $O(\log n)$ but not $O(1)$ $O(1)$
An array of $n$ distinct elements is said to be un-sorted if for every index $i$ such that $ 2 \leq i \leq n-1$, either $A[i] \text{max} \{A [i-1], A[i+1]\}$, or $A[i] <...
2.7k
views
commented
Oct 1, 2020
Algorithms
tifr2017
algorithms
sorting
time-complexity
+
–
1
answer
2
Peter Linz Edition 4 Derivation Trees Definition 5.3 (Page No. 130)
Which of the following is false for derivation tree of CFG- $G (V, T, P, S)$ ? The root is labeled $S$. Every leaf has a label from $V ⋃ T ⋃ \{ λ \}$. A vertex with a child labeled $λ$ can only have it as the rightmost child. $\text{1 & 3}$ $\text{1 & 2}$ $\text{2 & 3}$ $\text{Only 2}$
Which of the following is false for derivation tree of CFG- $G (V, T, P, S)$ ?The root is labeled $S$.Every leaf has a label from $V ⋃ T ⋃ \{ λ \}$.A vertex with a ...
749
views
commented
Mar 10, 2018
Theory of Computation
theory-of-computation
peter-linz
peter-linz-edition4
context-free-grammar
derivation-tree
+
–
2
answers
3
Brute Force Parsing
Which of the following can be said about the Exhaustive search parsing or brute force parsing ? It is inefficient as the time taken is proportional to the length of the string. The parser always terminates on the strings in the $L(G)$. The parser always terminates on the strings not in $L(G)$. $\text{1 & 2}$ $\text{2 & 3}$ $\text{1 & 3}$ $\text{1, 2 & 3}$
Which of the following can be said about the Exhaustive search parsing or brute force parsing ?It is inefficient as the time taken is proportional to the length of the st...
1.5k
views
asked
Feb 24, 2018
Theory of Computation
parsing
theory-of-computation
compiler-design
+
–
2
answers
4
Simple Grammar
Consider Grammar G with the following characteristic- $A → ax$, where $A ∈ V$, $a ∈ T$, $x ∈ V^*$, and any pair $( A, a )$ occurs at most once in $P$. For example, $S → aA \mid aB...,$ is not a grammar of type $G$ because the pair $(S,a)$ occur in two productions. ... string w belonging to $L(G)$ ? $\mid w \mid^3$ $\mid w \mid$ $2^{\mid w \mid}$ Not a function of $\mid w \mid$ alone.
Consider Grammar G with the following characteristic-$A → ax$, where $A ∈ V$, $a ∈ T$, $x ∈ V^*$, and any pair $( A, a )$ occurs at most once in $P$. For example,...
2.1k
views
asked
Feb 24, 2018
Theory of Computation
theory-of-computation
context-free-language
peter-linz
grammar
context-free-grammar
+
–
0
answers
5
Sentential forms
Restricting only to the leftmost derivations, how many sentential forms can exhaustive search parsing generate ? $O(P^{\mid w \mid})$ $O(P^{\mid w \mid +1})$ $O(P^{2\mid w \mid})$ $O(P^{2\mid w \mid + 1})$ where, $P$ is the number of productions and w is the word to be generated.
Restricting only to the leftmost derivations, how many sentential forms can exhaustive search parsing generate ? $O(P^{\mid w \mid})$$O(P^{\mid w \mid +1})$$O(P^{2\mid w ...
378
views
asked
Feb 24, 2018
Theory of Computation
theory-of-computation
context-free-language
peter-linz
grammar
+
–
0
answers
6
Peter Linz Edition 4 Example 5.13 (Page No. 144)
Consider the language $L = \{a^nb^nc^m\}U \{a^nb^mc^m\}$ with $n$ and $m$ nonnegative. Which of the following options is correct? There is no context free grammar possible for $L$. There exists a simple grammar for $L$. There exists an unambiguous grammar for $L$. There exists an ambiguous grammar for $L$.
Consider the language $L = \{a^nb^nc^m\}U \{a^nb^mc^m\}$ with $n$ and $m$ nonnegative. Which of the following options is correct?There is no context free grammar possible...
328
views
asked
Feb 24, 2018
Theory of Computation
theory-of-computation
context-free-language
peter-linz
peter-linz-edition4
grammar
inherently-ambiguous
+
–
2
answers
7
TIFR CSE 2018 | Part A | Question: 13
A hacker knows that the password to the TIFR server is $10$-letter string consisting of lower-case letters from the English alphabet. He guesses a set of $5$ distinct $10$-letter strings (with lower-case letters) uniformly at random. What is the probability that one of the ... $ \frac{1}{(26)^{10}}$ None of the above
A hacker knows that the password to the TIFR server is $10$-letter string consisting of lower-case letters from the English alphabet. He guesses a set of $5$ distinct $10...
2.0k
views
answered
Dec 31, 2017
Probability
tifr2018
probability
conditional-probability
+
–
4
answers
8
TIFR CSE 2017 | Part A | Question: 11
Let $f \: \circ \: g$ denote function composition such that $(f \circ g)(x) = f(g(x))$. Let $f: A \rightarrow B$ such that for all $g \: : \: B \rightarrow A$ and $h \: : \: B \rightarrow A$ ... ) $f$ is one-to-one (injective) $f$ is both one-to-one and onto (bijective) the range of $f$ is finite the domain of $f$ is finite
Let $f \: \circ \: g$ denote function composition such that $(f \circ g)(x) = f(g(x))$. Let $f: A \rightarrow B$ such that for all $g \: : \: B \rightarrow A$ and $h \: :...
4.0k
views
commented
Dec 28, 2016
Set Theory & Algebra
tifr2017
set-theory&algebra
functions
+
–
2
answers
9
TIFR CSE 2017 | Part B | Question: 13
For an undirected graph $G=(V, E)$, the line graph $G'=(V', E')$ is obtained by replacing each edge in $E$ by a vertex, and adding an edge between two vertices in $V'$ if the corresponding edges in $G$ are ... vertex in the line graph is at most the maximum degree in the original graph each vertex in the line graph has degree one or two
For an undirected graph $G=(V, E)$, the line graph $G'=(V', E')$ is obtained by replacing each edge in $E$ by a vertex, and adding an edge between two vertices in $V'$ if...
2.9k
views
commented
Dec 27, 2016
Graph Theory
tifr2017
graph-theory
bipartite-graph
+
–
2
answers
10
TIFR CSE 2017 | Part B | Question: 10
A vertex colouring of a graph $G=(V, E)$ with $k$ coulours is a mapping $c: V \rightarrow \{1, \dots , k\}$ such that $c(u) \neq c(v)$ for every $(u, v) \in E$. Consider the following statements: If every vertex in $G$ has ... the above statements is/are TRUE? Choose from the following options: only i only i and ii only i and iii only ii and iii i, ii, and iii
A vertex colouring of a graph $G=(V, E)$ with $k$ coulours is a mapping $c: V \rightarrow \{1, \dots , k\}$ such that $c(u) \neq c(v)$ for every $(u, v) \in E$. Consider ...
2.8k
views
answered
Dec 24, 2016
Graph Theory
tifr2017
graph-theory
graph-coloring
+
–
7
answers
11
TIFR CSE 2017 | Part B | Question: 12
An undirected graph is complete if there is an edge between every pair of vertices. Given a complete undirected graph on $n$ vertices, in how many ways can you choose a direction for the edges so that there are no directed cycles? $n$ $\frac{n(n-1)}{2}$ $n!$ $2^n$ $2^m, \: \text{ where } m=\frac{n(n-1)}{2}$
An undirected graph is complete if there is an edge between every pair of vertices. Given a complete undirected graph on $n$ vertices, in how many ways can you choose a d...
6.6k
views
answered
Dec 24, 2016
Graph Theory
tifr2017
graph-theory
graph-connectivity
+
–
4
answers
12
TIFR CSE 2017 | Part A | Question: 15
Let $T(a, b)$ be the function with two arguments (both nonnegative integral powers of 2) defined by the following recurrence: $ T(a, b) = T \left( \frac{a}{2}, b \right) +T\left( a, \frac{b}{2} \right)\quad \quad \quad \text{if } a, b \geq 2$ ... $\begin{pmatrix} r+s \\ r \end{pmatrix}$ $2^{r-s}$ if $r \geq s$, otherwise $2^{s-r}$
Let $T(a, b)$ be the function with two arguments (both nonnegative integral powers of 2) defined by the following recurrence:$ T(a, b) = T \left( \frac{a}{2}, b \right) +...
2.4k
views
answered
Dec 23, 2016
Algorithms
tifr2017
algorithms
recurrence-relation
+
–
1
answer
13
TIFR CSE 2017 | Part A | Question: 12
Consider the following program modifying an $n \times n$ square matrix $A$: for i=1 to n: for j=1 to n: temp=A[i][j]+10 A[i][j]=A[j][i] A[j][i]=temp-10 end for end for Which of the following statements about the contents of matrix $A$ at the end of ... the new matrix $A$ is symmetric, that is, $A[i][j]=A[j][i]$ for all $1 \leq i, j \leq n$ $A$ remains unchanged
Consider the following program modifying an $n \times n$ square matrix $A$:for i=1 to n: for j=1 to n: temp=A[i][j]+10 A[i][j]=A[j][i] A[j][i]=temp-10 end for end forWhic...
1.4k
views
answered
Dec 23, 2016
Algorithms
tifr2017
algorithms
identify-function
+
–
2
answers
14
TIFR CSE 2017 | Part A | Question: 8
In a tutorial on geometrical constructions, the teacher asks a student to construct a right-angled triangle ABC where the hypotenuse BC is 8 inches and the length of the perpendicular dropped from A onto the hypotenuse is $h$ inches, and offers various choices for teh ... NOT exist? 3.90 inches $2 \sqrt{2}$ inches $2 \sqrt{3}$ inches 4.1 inches none of the above
In a tutorial on geometrical constructions, the teacher asks a student to construct a right-angled triangle ABC where the hypotenuse BC is 8 inches and the length of the ...
986
views
answered
Dec 23, 2016
Quantitative Aptitude
tifr2017
quantitative-aptitude
geometry
+
–
2
answers
15
TIFR CSE 2017 | Part A | Question: 2
For vectors $x, \: y$ in $\mathbb{R}^n$, define the inner product $\langle x, y \rangle = \Sigma^n_{i=1} x_iy_i$, and the length of $x$ to be $\| x \| = \sqrt{\langle x, x \rangle}$. Let $a, \: b$ ... $a, \: b$? Choose from the following options. ii only i and ii iii only iv only iv and v
For vectors $x, \: y$ in $\mathbb{R}^n$, define the inner product $\langle x, y \rangle = \Sigma^n_{i=1} x_iy_i$, and the length of $x$ to be $\| x \| = \sqrt{\langle x, ...
1.6k
views
answered
Dec 23, 2016
Linear Algebra
tifr2017
linear-algebra
vector-space
+
–
5
answers
16
TIFR CSE 2017 | Part B | Question: 5
Consider the following psuedocode fragment, where $y$ is an integer that has been initialized. int i=1 int j=1 while (i<10): j=j*i i=i+1 if (i==y): break end if end while Consider the following statements: $(i==10)$ or $(i==y)$ If ... the end of the while loop? Choose from the following options. i only iii only ii and iii only i, ii, and iii None of the above
Consider the following psuedocode fragment, where $y$ is an integer that has been initialized.int i=1 int j=1 while (i<10): j=j*i i=i+1 if (i==y): break end if end whileC...
3.1k
views
answered
Dec 23, 2016
Programming in C
tifr2017
programming
loop-invariants
+
–
4
answers
17
TIFR CSE 2017 | Part B | Question: 8
For any natural number $n$, an ordering of all binary strings of length $n$ is a Gray code if it starts with $0^n$, and any successive strings in the ordering differ in exactly one bit (the first and last string must also differ by one ... two strings are separated by $k$ other strings in the ordering, then they must differ in exactly $k$ bits none of the above
For any natural number $n$, an ordering of all binary strings of length $n$ is a Gray code if it starts with $0^n$, and any successive strings in the ordering differ in e...
3.2k
views
answered
Dec 23, 2016
Digital Logic
tifr2017
digital-logic
boolean-algebra
+
–
6
answers
18
TIFR CSE 2017 | Part B | Question: 9
Which of the following regular expressions correctly accepts the set of all $0/1$-strings with an even (possibly zero) number of $1$s? $(10^*10^*)^*$ $(0^*10^*1)^*$ $0^*1(10^*1)^*10^*$ $0^*1(0^*10^*10^*)^*10^*$ $(0^*10^*1)^*0^*$
Which of the following regular expressions correctly accepts the set of all $0/1$-strings with an even (possibly zero) number of $1$s?$(10^*10^*)^*$$(0^*10^*1)^*$$0^*1(10...
2.3k
views
answered
Dec 23, 2016
Theory of Computation
tifr2017
theory-of-computation
regular-expression
+
–
4
answers
19
TIFR CSE 2017 | Part A | Question: 14
Consider the following game with two players, Aditi and Bharat. There are $n$ tokens in a bag. The two players know $n$, and take turns removing tokens from the bag. In each turn, a player can either remove one token or two tokens. The player ... a winning strategy. For both $n=7$ and $n=8$, Bharat has a winning strategy. Bharat never has a winning strategy.
Consider the following game with two players, Aditi and Bharat. There are $n$ tokens in a bag. The two players know $n$, and take turns removing tokens from the bag. In e...
2.9k
views
answered
Dec 23, 2016
Analytical Aptitude
tifr2017
analytical-aptitude
logical-reasoning
+
–
2
answers
20
TIFR CSE 2017 | Part B | Question: 4
Let $L$ be the language over the alphabet $\{1, 2, 3, (, )\}$ generated by the following grammar (with start symbol $S$, and non-terminals $\{A, B, C\}$ ... $L$ is finite $L$ is not recursively enumerable $L$ is regular $L$ contains only strings of even length $L$ is context-free but not regular
Let $L$ be the language over the alphabet $\{1, 2, 3, (, )\}$ generated by the following grammar (with start symbol $S$, and non-terminals $\{A, B, C\}$):$ S \rightarrow ...
2.5k
views
answered
Dec 23, 2016
Theory of Computation
tifr2017
theory-of-computation
identify-class-language
+
–
4
answers
21
TIFR CSE 2017 | Part B | Question: 1
A vertex colouring with three colours of a graph $G=(V, E)$ is a mapping $c: V \rightarrow \{R, G, B\}$ so that adjacent vertices receive distinct colours. Consider the following undirected graph. How many vertex colouring with three colours does this graph have? $3^9$ $6^3$ $3 \times 2^8$ $27$ $24$
A vertex colouring with three colours of a graph $G=(V, E)$ is a mapping $c: V \rightarrow \{R, G, B\}$ so that adjacent vertices receive distinct colours. Consider the f...
4.6k
views
answered
Dec 23, 2016
Graph Theory
tifr2017
graph-theory
graph-coloring
+
–
Email or Username
Show
Hide
Password
I forgot my password
Remember
Log in
Register