Login
Register
Dark Mode
Brightness
Profile
Edit Profile
Messages
My favorites
My Updates
Logout
Search results for tifr2017
54
votes
7
answers
1
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...
go_editor
6.6k
views
go_editor
asked
Dec 23, 2016
Graph Theory
tifr2017
graph-theory
graph-connectivity
+
–
30
votes
5
answers
2
TIFR CSE 2017 | Part B | Question: 3
We have an implementation that supports the following operations on a stack (in the instructions below, $\mathsf{s}$ is the name of the stack). $\mathsf{isempty(s)}$ : returns $\mathsf{True}$ if $\mathsf{s}$ is empty, and $\mathsf{False}$ otherwise. $\mathsf{top(s)}$ : returns the top ... ()((())((((") is executed? $(((($ $))) \ (((($ $)))$ $(((()))$ $()()$
We have an implementation that supports the following operations on a stack (in the instructions below, $\mathsf{s}$ is the name of the stack).$\mathsf{isempty(s)}$ : ret...
go_editor
3.0k
views
go_editor
asked
Dec 23, 2016
DS
tifr2017
data-structures
stack
+
–
38
votes
4
answers
3
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...
go_editor
4.8k
views
go_editor
asked
Dec 23, 2016
Graph Theory
tifr2017
graph-theory
graph-coloring
+
–
19
votes
4
answers
4
TIFR CSE 2017 | Part A | Question: 5
How many distinct ways are there to split $50$ identical coins among three people so that each person gets at least $5$ coins? $3^{35}$ $3^{50}-2^{50}$ $\binom{35}{2}$ $\binom{50}{15} \cdot 3^{35}$ $\binom{37}{2}$
How many distinct ways are there to split $50$ identical coins among three people so that each person gets at least $5$ coins?$3^{35}$$3^{50}-2^{50}$$\binom{35}{2}$$\bino...
go_editor
4.1k
views
go_editor
asked
Dec 21, 2016
Combinatory
tifr2017
combinatory
discrete-mathematics
normal
balls-in-bins
+
–
20
votes
5
answers
5
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...
go_editor
3.1k
views
go_editor
asked
Dec 23, 2016
Programming in C
tifr2017
programming
loop-invariants
+
–
12
votes
6
answers
6
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...
go_editor
2.3k
views
go_editor
asked
Dec 23, 2016
Theory of Computation
tifr2017
theory-of-computation
regular-expression
+
–
20
votes
4
answers
7
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...
go_editor
3.2k
views
go_editor
asked
Dec 23, 2016
Digital Logic
tifr2017
digital-logic
boolean-algebra
+
–
9
votes
4
answers
8
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...
go_editor
2.9k
views
go_editor
asked
Dec 23, 2016
Analytical Aptitude
tifr2017
analytical-aptitude
logical-reasoning
+
–
6
votes
2
answers
9
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, ...
go_editor
1.6k
views
go_editor
asked
Dec 21, 2016
Linear Algebra
tifr2017
linear-algebra
vector-space
+
–
19
votes
2
answers
10
TIFR CSE 2017 | Part B | Question: 14
Consider the following grammar $G$ with terminals $\{[, ]\}$, start symbol $S$, and non-terminals $\{A, B, C\}$: $S \rightarrow AC \mid SS \mid AB$ $C \rightarrow SB$ $A \rightarrow [$ $B \rightarrow ]$ A language $L$ is called ... $L(G)$ can be recognized by a deterministic push down automaton $L(G)$ is prefix-closed $L(G)$ is recursive
Consider the following grammar $G$ with terminals $\{[, ]\}$, start symbol $S$, and non-terminals $\{A, B, C\}$:$$S \rightarrow AC \mid SS \mid AB$$$$C \rightarrow SB$$$...
go_editor
2.9k
views
go_editor
asked
Dec 23, 2016
Theory of Computation
tifr2017
theory-of-computation
identify-class-language
+
–
32
votes
3
answers
11
TIFR CSE 2017 | Part B | Question: 11
Given that $B(x)$ means "$x$ is a bat", $F(x)$ means "$x$ is a fly", and $E(x, y)$ means "$x$ eats $y$", what is the best English translation of $ \forall x(F(x) \rightarrow \forall y (E(y, x) \rightarrow B(y)))?$ all flies eat bats every fly is eaten by some bat bats eat only flies every bat eats flies only bats eat flies
Given that$B(x)$ means "$x$ is a bat",$F(x)$ means "$x$ is a fly", and$E(x, y)$ means "$x$ eats $y$",what is the best English translation of $$ \forall x(F(x) \rightarrow...
go_editor
3.6k
views
go_editor
asked
Dec 23, 2016
Mathematical Logic
tifr2017
first-order-logic
+
–
22
votes
3
answers
12
TIFR CSE 2017 | Part A | Question: 4
Which of the following functions asymptotically grows the fastest as $n$ goes to infinity? $(\log \: \log \: n)!$ $(\log \: \log \: n)^ {\log \: n}$ $(\log \: \log \: n)^{\log \: \log \: \log \: n}$ $(\log \: n)^{\log \: \log \: n}$ $2^{\sqrt{\log \: \log \: n}}$
Which of the following functions asymptotically grows the fastest as $n$ goes to infinity?$(\log \: \log \: n)!$$(\log \: \log \: n)^ {\log \: n}$$(\log \: \log \: n)^{\l...
go_editor
4.0k
views
go_editor
asked
Dec 21, 2016
Algorithms
tifr2017
algorithms
asymptotic-notation
+
–
15
votes
4
answers
13
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) +...
go_editor
2.4k
views
go_editor
asked
Dec 23, 2016
Algorithms
tifr2017
algorithms
recurrence-relation
+
–
26
votes
4
answers
14
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 \: :...
go_editor
4.0k
views
go_editor
asked
Dec 22, 2016
Set Theory & Algebra
tifr2017
set-theory&algebra
functions
+
–
8
votes
1
answer
15
TIFR CSE 2017 | Part B | Question: 6
Consider the First Order Logic (FOL) with equality and suitable function and relation symbols. Which of the following is FALSE? Partial orders cannot be axiomatized in FOL FOL has a complete proof system Natural numbers cannot be axiomatized in FOL Real numbers cannot be axiomatized in FOL Relational numbers cannot be axiomatized in FOL
Consider the First Order Logic (FOL) with equality and suitable function and relation symbols. Which of the following is FALSE?Partial orders cannot be axiomatized in FOL...
go_editor
1.2k
views
go_editor
asked
Dec 23, 2016
Mathematical Logic
tifr2017
first-order-logic
normal
+
–
16
votes
2
answers
16
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] <...
go_editor
2.7k
views
go_editor
asked
Dec 23, 2016
Algorithms
tifr2017
algorithms
sorting
time-complexity
+
–
17
votes
2
answers
17
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...
go_editor
2.9k
views
go_editor
asked
Dec 23, 2016
Graph Theory
tifr2017
graph-theory
bipartite-graph
+
–
23
votes
2
answers
18
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 ...
go_editor
2.8k
views
go_editor
asked
Dec 23, 2016
Graph Theory
tifr2017
graph-theory
graph-coloring
+
–
14
votes
2
answers
19
TIFR CSE 2017 | Part A | Question: 10
For a set $A$ define $P(A)$ to be the set of all subsets of $A$. For example, if $A = \{1, 2\}$ then $P(A) = \{ \emptyset, \{1, 2\}, \{1\}, \{ 2 \} \}$. Let $A \rightarrow P(A)$ be a function and $A$ is not ... be onto (surjective) $f$ is both one-to-one and onto (bijective) there is no such $f$ possible if such a function $f$ exists, then $A$ is infinite
For a set $A$ define $P(A)$ to be the set of all subsets of $A$. For example, if $A = \{1, 2\}$ then $P(A) = \{ \emptyset, \{1, 2\}, \{1\}, \{ 2 \} \}$. Let $A \rightarro...
go_editor
2.2k
views
go_editor
asked
Dec 22, 2016
Set Theory & Algebra
tifr2017
set-theory&algebra
functions
easy
+
–
15
votes
2
answers
20
TIFR CSE 2017 | Part A | Question: 9
Consider the $majority$ function on three bits, $\textbf{maj}: \{0, 1\}^3 \rightarrow \{0, 1\}$ where $\textbf{maj}(x_1, x_2, x_3)=1$ if and only if $x_1+x_2+x_3 \geq 2$. Let $p(\alpha)$ be the probability that the output is $1$ when each input is set to ... $3 \alpha$ $\alpha^2$ $6\alpha(1-\alpha)$ $3\alpha^2 (1-\alpha)$ $6\alpha(1-\alpha)+\alpha^2$
Consider the $majority$ function on three bits, $\textbf{maj}: \{0, 1\}^3 \rightarrow \{0, 1\}$ where $\textbf{maj}(x_1, x_2, x_3)=1$ if and only if $x_1+x_2+x_3 \geq 2$....
go_editor
1.4k
views
go_editor
asked
Dec 21, 2016
Probability
tifr2017
probability
independent-events
differentiation
+
–
Page:
1
2
next »
Email or Username
Show
Hide
Password
I forgot my password
Remember
Log in
Register