Login
Register
Dark Mode
Brightness
Profile
Edit Profile
Messages
My favorites
My Updates
Logout
Recent questions tagged tifr2022
3
votes
1
answer
1
TIFR CSE 2022 | Part B | Question: 1
Which data structure is commonly used to implement breadth first search in a graph? A queue A stack A heap A hash table A splay tree
Which data structure is commonly used to implement breadth first search in a graph?A queueA stackA heapA hash tableA splay tree
admin
548
views
admin
asked
Sep 1, 2022
DS
tifr2022
data-structures
queue
easy
+
–
4
votes
2
answers
2
TIFR CSE 2022 | Part B | Question: 2
Let $G=(V, E)$ be an undirected simple graph. A subset $M \subseteq E$ is a matching in $G$ if distinct edges in $M$ do not share a vertex. A matching is maximal if no strict superset of $M$ is a matching. How many maximal matchings does the following graph have? $1$ $2$ $3$ $4$ $5$
Let $G=(V, E)$ be an undirected simple graph. A subset $M \subseteq E$ is a matching in $G$ if distinct edges in $M$ do not share a vertex. A matching is maximal if no st...
admin
975
views
admin
asked
Sep 1, 2022
Graph Theory
tifr2022
graph-theory
graph-matching
+
–
1
votes
1
answer
3
TIFR CSE 2022 | Part B | Question: 3
Consider the problem of sorting $n$ single digit integers (base $10$). This problem can be solved in time $O(n \log n)$ but not $O(n \log \log n)$ $O(n \log \log n)$ but not $O(n)$ $O(n)$ but not $O(n / \log \log n)$ $O(n / \log \log n)$ None of the above.
Consider the problem of sorting $n$ single digit integers (base $10$). This problem can be solved in time$O(n \log n)$ but not $O(n \log \log n)$$O(n \log \log n)$ but no...
admin
842
views
admin
asked
Sep 1, 2022
Algorithms
tifr2022
algorithms
sorting
time-complexity
+
–
1
votes
1
answer
4
TIFR CSE 2022 | Part B | Question: 4
Consider the following algorithm for computing the factorial of a positive integer $n$, specified in binary: prod ← 1 for i from 1 to n prod ← prod i output prod Assume that the number of bit operations required to multiply a $k$-bit positive integer with an $\ell$ ... $\omega(n \log n)$ $O\left(n^3\right)$ but $\omega\left(n^2\right) $ None of the above
Consider the following algorithm for computing the factorial of a positive integer $n$, specified in binary:prod ← 1 for i from 1 to n prod ← prod × i output prodAss...
admin
677
views
admin
asked
Sep 1, 2022
Algorithms
tifr2022
algorithms
identify-function
time-complexity
+
–
2
votes
1
answer
5
TIFR CSE 2022 | Part B | Question: 5
There is an unsorted list of $n$ integers. You are given $3$ distinct integers and you have to check if all $3$ integers are present in the list or not. The only operation that you are allowed to perform is a comparison. Let $A$ be an algorithm for this task that performs the least number ... $c=3 n$ $c=2 n+5$ $c \geq 3 n-1$ $c \leq n$ $c \leq 2 n+3 $
There is an unsorted list of $n$ integers. You are given $3$ distinct integers and you have to check if all $3$ integers are present in the list or not. The only operatio...
admin
613
views
admin
asked
Sep 1, 2022
DS
tifr2022
data-structures
linked-list
+
–
3
votes
1
answer
6
TIFR CSE 2022 | Part B | Question: 6
We are given a graph $G$ along with a matching $M$ and a vertex cover $C$ in it such that $|M|=|C|$. Consider the following statements: $M$ is a maximum matching in $G$. $C$ is a minimum vertex cover in $G$. $G$ is a bipartite graph. Which of ... $(1)$ and $(2)$ are correct All the three statements $(1), (2),$ and $(3)$ are correct
We are given a graph $G$ along with a matching $M$ and a vertex cover $C$ in it such that $|M|=|C|$. Consider the following statements:$M$ is a maximum matching in $G$.$C...
admin
938
views
admin
asked
Sep 1, 2022
Graph Theory
tifr2022
graph-theory
graph-matching
+
–
1
votes
1
answer
7
TIFR CSE 2022 | Part B | Question: 7
Consider the following grammar: $\text{P, Q, R}$ are non-terminals; $c, d$ are terminals; $\text{P}$ is the start symbol; and the production rules follow. $\mathrm{P}::=\mathrm{QR}$ $\text{Q ::= c}$ $\text{Q} ::=\text{RcR}$ ... three consecutive $c\text{'s}$ Every string produced by the grammar has at least has many $d\text{'s}$ as $c\text{'s}$
Consider the following grammar: $\text{P, Q, R}$ are non-terminals; $c, d$ are terminals; $\text{P}$ is the start symbol; and the production rules follow.$\mathrm{P}::=\m...
admin
511
views
admin
asked
Sep 1, 2022
Compiler Design
tifr2022
compiler-design
grammar
+
–
2
votes
0
answers
8
TIFR CSE 2022 | Part B | Question: 8
Let $r_1$ and $r_2$ be two regular expressions. They symbol $\equiv$ stands for equivalence of two regular expressions in the sense that if $r_1 \equiv r_2$, then both regular expressions describe the same language. Which of the following is/are $\text{FALSE}$? ... (i) is false Only (ii) is false Only (iii) is false Both (i) and (iii) are false None of the above
Let $r_1$ and $r_2$ be two regular expressions. They symbol $\equiv$ stands for equivalence of two regular expressions in the sense that if $r_1 \equiv r_2$, then both re...
admin
370
views
admin
asked
Sep 1, 2022
Theory of Computation
tifr2022
theory-of-computation
regular-expression
+
–
1
votes
1
answer
9
TIFR CSE 2022 | Part B | Question: 9
Let $n \geq 2$ be any integer. Which of the following statements is $\text{FALSE}?$ $n!$ divides the product of any $n$ consecutive integers $\displaystyle{}\sum_{i=0}^n\left(\begin{array}{c}n \\ i\end{array}\right)=2^n$ ... an odd prime, then $n$ divides $2^{n-1}-1$ $n$ divides $\left(\begin{array}{c}2 n \\ n\end{array}\right)$
Let $n \geq 2$ be any integer. Which of the following statements is $\text{FALSE}?$$n!$ divides the product of any $n$ consecutive integers$\displaystyle{}\sum_{i=0}^n\le...
admin
333
views
admin
asked
Sep 1, 2022
Combinatory
tifr2022
combinatory
binomial-theorem
+
–
1
votes
0
answers
10
TIFR CSE 2022 | Part B | Question: 10
Consider the assertions $\text{(A1)}$ Given a directed graph $G$ with positive weights on the edges, two special vertices $s$ and $t$, and an integer $k$ - it is $\text{NP}$-complete to determine if $G$ has an $s- t$ path of length at most $k$ ... $\text{A1}$ does not imply $\text{A2}$ and $\text{A2}$ does not imply $\text{A1}$ None of the above.
Consider the assertions$\text{(A1)}$ Given a directed graph $G$ with positive weights on the edges, two special vertices $s$ and $t$, and an integer $k$ - it is $\text{NP...
admin
382
views
admin
asked
Sep 1, 2022
Algorithms
tifr2022
algorithms
graph-connectivity
p-np-npc-nph
+
–
2
votes
0
answers
11
TIFR CSE 2022 | Part B | Question: 11
Consider the following function $\textsf{count},$ that takes as input $a,$ an array of integers, and $\textsf{N}$, the size of the array. int count(int a[], int N) { int i, j, count_FN; count_FN = 0; for (i=1 ; i<N ; i++) { j=i-1 ; while ... $\textsf{N} \geq c$, for all arrays of size $\textsf{N, count_FN} \geq \textsf{N}^2 / c$ None of the above
Consider the following function $\textsf{count},$ that takes as input $a,$ an array of integers, and $\textsf{N}$, the size of the array.int count(int a[], int N) { int i...
admin
432
views
admin
asked
Sep 1, 2022
Algorithms
tifr2022
algorithms
sorting
+
–
1
votes
0
answers
12
TIFR CSE 2022 | Part B | Question: 12
Given an undirected graph $G$, an ordering $\sigma$ of its vertices is called a perfect ordering if for every vertex $v$, the neighbours of $v$ which precede $v$ in $\sigma$ form a clique in $G$. Recall that given an undirected ... SPECIAL-COLOURING are in $\mathrm{P}$ Neither of SPECIAL-CLiQUE and SPECIAL-COLOURING is in $\mathrm{P},$ but both are decidable
Given an undirected graph $G$, an ordering $\sigma$ of its vertices is called a perfect ordering if for every vertex $v$, the neighbours of $v$ which precede $v$ in $\sig...
admin
380
views
admin
asked
Sep 1, 2022
Graph Theory
tifr2022
graph-theory
graph-coloring
p-np-npc-nph
+
–
1
votes
0
answers
13
TIFR CSE 2022 | Part B | Question: 13
Consider a directed graph $G=(V, E)$, where each edge $e \in E$ has a positive edge weight $c_e$. Determine the appropriate choices for the blanks below so that the value of the following linear program is the length of the shortest directed path in $G$ from $s$ ... $\text{blank }1: \min, \text{blank }2:\; \geq$ $\text{blank }1: \min, \text{blank }2:\; =$
Consider a directed graph $G=(V, E)$, where each edge $e \in E$ has a positive edge weight $c_e$. Determine the appropriate choices for the blanks below so that the value...
admin
292
views
admin
asked
Sep 1, 2022
Algorithms
tifr2022
algorithms
shortest-path
+
–
1
votes
1
answer
14
TIFR CSE 2022 | Part B | Question: 14
Let $G$ be a directed graph (with no self-loops or parallel edges) with $n \geq 2$ vertices and $m$ edges. Consider the $n \times m$ incidence matrix $M$ of $G$, whose rows are indexed by the vertices of $G$ and the columns by the edges of $G$ ... . Then, what is the rank of $M?$ $m-1$ $m-n+1$ $\lceil m / 2\rceil$ $n-1$ $\lceil n / 2\rceil$
Let $G$ be a directed graph (with no self-loops or parallel edges) with $n \geq 2$ vertices and $m$ edges. Consider the $n \times m$ incidence matrix $M$ of $G$, whose ro...
admin
467
views
admin
asked
Sep 1, 2022
Graph Theory
tifr2022
graph-theory
graph-connectivity
rank-of-matrix
+
–
1
votes
0
answers
15
TIFR CSE 2022 | Part B | Question: 15
Let $\mathbb{R}$ denote the set of real numbers. Let $d \geq 4$ and $\alpha \in \mathbb{R}$ ... $\left(a_0, a_1, \ldots, a_d\right) \in S$, the function $ x \mapsto \sum_{i=0}^d a_i x^i $ has a local optimum at $\alpha$
Let $\mathbb{R}$ denote the set of real numbers. Let $d \geq 4$ and $\alpha \in \mathbb{R}$. Let$$ S=\left\{\left(a_0, a_1, \ldots, a_d\right) \in \mathbb{R}^{d+1}: \sum_...
admin
354
views
admin
asked
Sep 1, 2022
Linear Algebra
tifr2022
linear-algebra
vector-space
+
–
0
votes
1
answer
16
TIFR CSE 2022 | Part A | Question: 1
A snail crawls up a vertical pole $75$ feet high, starting from the ground. Each day it crawls up $5$ feet, and each night it slides down $4$ feet. When will it first reach the top of the pole? $75^{\text {th}}$ day $74^{\text {th}}$ day $73^{ \text{rd}}$ day $72^{\text {nd }}$ day $71^{\text {st }}$ day
A snail crawls up a vertical pole $75$ feet high, starting from the ground. Each day it crawls up $5$ feet, and each night it slides down $4$ feet. When will it first rea...
admin
590
views
admin
asked
Sep 1, 2022
Combinatory
tifr2022
combinatory
counting
+
–
0
votes
2
answers
17
TIFR CSE 2022 | Part A | Question: 2
We would like to invite a minimum number $n$ of people (their birthdays are independent of each other) to a party such that the expected number of pairs of people that share the same birthday is at least $1.$ What should $n$ be? (Ignore leap years, so ... birthdays fall with equal probability on each of the $365$ days of the year.) $23$ $28$ $92$ $183$ $366$
We would like to invite a minimum number $n$ of people (their birthdays are independent of each other) to a party such that the expected number of pairs of people that sh...
admin
816
views
admin
asked
Sep 1, 2022
Probability
tifr2022
probability
expectation
+
–
1
votes
1
answer
18
TIFR CSE 2022 | Part A | Question: 3
A binary string is a sequence of $0 \text{'s}$ and $1\text{'s}.$ A binary string is finite if the sequence is finite, otherwise it is infinite. Examples of finite binary strings include $00010100$, and $1111101010.$ ... set of all finite binary strings is countable while whether the set of all infinite binary strings is countable or not is not known
A binary string is a sequence of $0 \text{'s}$ and $1\text{'s}.$ A binary string is finite if the sequence is finite, otherwise it is infinite. Examples of finite binary ...
admin
640
views
admin
asked
Sep 1, 2022
Theory of Computation
tifr2022
theory-of-computation
countable-uncountable-set
+
–
1
votes
1
answer
19
TIFR CSE 2022 | Part A | Question: 4
Consider the polynomial $p(x)=x^3-x^2+x-1$. How many symmetric matrices with integer entries are there whose characteristic polynomial is $p$? (Recall that the characteristic polynomial of a square matrix $A$ in the variable $x$ is defined to be the determinant of the matrix $(A-x I)$ where $I$ is the identity matrix.) $0$ $1$ $2$ $4$ Infinitely many
Consider the polynomial $p(x)=x^3-x^2+x-1$. How many symmetric matrices with integer entries are there whose characteristic polynomial is $p$? (Recall that the characteri...
admin
715
views
admin
asked
Sep 1, 2022
Linear Algebra
tifr2022
linear-algebra
matrix
determinant
+
–
5
votes
1
answer
20
TIFR CSE 2022 | Part A | Question: 5
Let $\mathcal{F}$ be the set of all functions mapping $\{1, \ldots, n\}$ to $\{1, \ldots, m\}$. Let $f$ be a function that is chosen uniformly at random from $\mathcal{F}$. Let $x, y$ be distinct elements from the set $\{1, \ldots, n\}$. Let $p$ denote the probability ... Then, $p=0$ $p=\frac{1}{n^m}$ $0<p \leq \frac{1}{m^n}$ $p=\frac{1}{m}$ $p=\frac{1}{n}$
Let $\mathcal{F}$ be the set of all functions mapping $\{1, \ldots, n\}$ to $\{1, \ldots, m\}$. Let $f$ be a function that is chosen uniformly at random from $\mathcal{F}...
admin
465
views
admin
asked
Sep 1, 2022
Probability
tifr2022
probability
uniform-distribution
functions
+
–
0
votes
2
answers
21
TIFR CSE 2022 | Part A | Question: 6
Let $f$ be a polynomial of degree $n \geq 3$ all of whose roots are non-positive real numbers. Suppose that $f(1)=1$. What is the maximum possible value of $f^{\prime}(1)?$ $1$ $n$ $n+1$ $\frac{n(n+1)}{2}$ $f^{\prime}(1)$ can be arbitrarily large given only the constraints in the question
Let $f$ be a polynomial of degree $n \geq 3$ all of whose roots are non-positive real numbers. Suppose that $f(1)=1$. What is the maximum possible value of $f^{\prime}(1)...
admin
715
views
admin
asked
Sep 1, 2022
Calculus
tifr2022
calculus
maxima-minima
+
–
0
votes
1
answer
22
TIFR CSE 2022 | Part A | Question: 7
Initially, $N$ white beads are arranged in a circle. A number $k$ is chosen uniformly at random from $\{1, \ldots, N-1\}$. Then a set of $k$ beads is chosen uniformly from the white beads, and these $k$ beads are coloured black. The position of the beads remains ... None of the above
Initially, $N$ white beads are arranged in a circle. A number $k$ is chosen uniformly at random from $\{1, \ldots, N-1\}$. Then a set of $k$ beads is chosen uniformly fro...
admin
602
views
admin
asked
Sep 1, 2022
Probability
tifr2022
probability
uniform-distribution
+
–
13
votes
1
answer
23
TIFR CSE 2022 | Part A | Question: 8
Let $A$ be the $(n+1) \times(n+1)$ matrix given below, where $n \geq 1$. For $i \leq n$, the $i$-th row of $A$ has every entry equal to $2i-1$ and the last row, i.e., the $(n+1)$-th row of $A$ has every entry equal to $-n^2$ ... $A$ has rank $n$ $A^2$ has rank $1$ All the eigenvalues of $A$ are distinct All the eigenvalues of $A$ are $0$ None of the above
Let $A$ be the $(n+1) \times(n+1)$ matrix given below, where $n \geq 1$. For $i \leq n$, the $i$-th row of $A$ has every entry equal to $2i-1$ and the last row, i.e., the...
admin
686
views
admin
asked
Sep 1, 2022
Linear Algebra
tifr2022
linear-algebra
rank-of-matrix
eigen-value
+
–
0
votes
1
answer
24
TIFR CSE 2022 | Part A | Question: 9
You are given the following properties of sets $A, B, X$, and $Y$. For notation, $|A|$ denotes the cardinality of set $A$ (i.e., the number of elements in $A$ ), and $A \backslash B$ denotes the set of elements that are in $A$ but not in $B$. $A \cup B=X \cup Y$ ... $|X|=5$ $|Y|=5$ $|A \cup X|=|B \cup Y|$ $|A \cap X|=|B \cap Y|$ $|A|=|B|$
You are given the following properties of sets $A, B, X$, and $Y$. For notation, $|A|$ denotes the cardinality of set $A$ (i.e., the number of elements in $A$ ), and $A \...
admin
401
views
admin
asked
Sep 1, 2022
Set Theory & Algebra
tifr2022
set-theory&algebra
set-theory
+
–
1
votes
1
answer
25
TIFR CSE 2022 | Part A | Question: 10
Consider a bag containing colored marbles. There are $n$ marbles in the bag such that there is exactly one pair of marbles of color $i$ for each $i \in\{1, \ldots, m\}$ and the rest of the marbles are of distinct colors (different from colors $\{1, \ldots, m\}$ ). You draw ... $\frac{2m}{n}$ $\frac{2m}{n(n-1)}$ $\frac{2m}{n^2}$ $\frac{m}{n(n-1)}$
Consider a bag containing colored marbles. There are $n$ marbles in the bag such that there is exactly one pair of marbles of color $i$ for each $i \in\{1, \ldots, m\}$ a...
admin
589
views
admin
asked
Sep 1, 2022
Probability
tifr2022
probability
conditional-probability
+
–
0
votes
0
answers
26
TIFR CSE 2022 | Part A | Question: 11
Let $X$ be a finite set. A family $\mathcal{F}$ of subsets of $X$ is said to be upward closed if the following holds for all sets $A, B \subseteq X$ ... $\mathcal{F} \sqcup \mathcal{G}=\mathcal{G} \backslash \mathcal{F}$ None of the above
Let $X$ be a finite set. A family $\mathcal{F}$ of subsets of $X$ is said to be upward closed if the following holds for all sets $A, B \subseteq X$ :$$ A \in \mathcal{F}...
admin
321
views
admin
asked
Sep 1, 2022
Set Theory & Algebra
tifr2022
set-theory&algebra
set-theory
+
–
1
votes
1
answer
27
TIFR CSE 2022 | Part A | Question: 12
Alice plays the following game on a math show. There are $7$ boxes and identical prizes are hidden inside $3$ of the boxes. Alice is asked to choose a box where a prize might be. She chooses a box uniformly at random. From the unchosen boxes which do not have a prize, ... ). Her probability of winning the prize is $3 / 7$ $1 / 2$ $17 / 30$ $18 / 35$ $9 / 19$
Alice plays the following game on a math show. There are $7$ boxes and identical prizes are hidden inside $3$ of the boxes. Alice is asked to choose a box where a prize m...
admin
522
views
admin
asked
Sep 1, 2022
Probability
tifr2022
probability
conditional-probability
+
–
2
votes
1
answer
28
TIFR CSE 2022 | Part A | Question: 13
Consider the transition system shown in the figure below with the initial state $s_1$. A token is initially placed at $s_1$, and it moves to $s_2$ with probability $\frac{2}{3}$, and to $s_3$ with probability $\frac{1}{3}$. From $s_2$ and $s_3$, the token always ... appear in the run? $\frac{1}{7}$ $\frac{2}{7}$ $\frac{3}{7}$ $\frac{5}{7}$ None of the above
Consider the transition system shown in the figure below with the initial state $s_1$. A token is initially placed at $s_1$, and it moves to $s_2$ with probability $\frac...
admin
404
views
admin
asked
Sep 1, 2022
Theory of Computation
tifr2022
theory-of-computation
finite-automata
probability
+
–
0
votes
0
answers
29
TIFR CSE 2022 | Part A | Question: 14
Suppose $w(t)=4 e^{i t}, x(t)=3 e^{i(t+\pi / 3)}, y(t)=3 e^{i(t-\pi / 3)}$ and $z(t)=3 e^{i(t+\pi)}$ are points that move in the complex plane as the time $t$ varies in $(-\infty, \infty)$. Let $c(t)$ ... $\frac{1}{2 \pi}$ $2 \pi$ $\sqrt{3} \pi$ $\frac{1}{\sqrt{3} \pi}$ $1$
Suppose $w(t)=4 e^{i t}, x(t)=3 e^{i(t+\pi / 3)}, y(t)=3 e^{i(t-\pi / 3)}$ and $z(t)=3 e^{i(t+\pi)}$ are points that move in the complex plane as the time $t$ varies in $...
admin
335
views
admin
asked
Sep 1, 2022
Calculus
tifr2022
calculus
differentiation
+
–
0
votes
1
answer
30
TIFR CSE 2022 | Part A | Question: 15
Fix $n \geq 4$. Suppose there is a particle that moves randomly on the number line, but never leaves the set $\{1,2, \ldots, n\}$. The initial probability distribution of the particle is $\pi$ i.e., the probability that particle is in location $i$ is given by $\pi(i)$. In the ... $\pi(1)=1$ and $\pi(i)=0$ for $i \neq 1$ $\pi(n)=1$ and $\pi(i)=0$ for $i \neq n$
Fix $n \geq 4$. Suppose there is a particle that moves randomly on the number line, but never leaves the set $\{1,2, \ldots, n\}$. The initial probability distribution of...
admin
482
views
admin
asked
Sep 1, 2022
Probability
tifr2022
probability
uniform-distribution
+
–
To see more, click for the
full list of questions
or
popular tags
.
Email or Username
Show
Hide
Password
I forgot my password
Remember
Log in
Register