Dark Mode

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

admin asked in DS Sep 1, 2022

by admin

538 views

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$

admin asked in Graph Theory Sep 1, 2022

by admin

928 views

1 vote

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.

admin asked in Algorithms Sep 1, 2022

by admin

815 views

1 vote

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

admin asked in Algorithms Sep 1, 2022

by admin

657 views

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 $

admin asked in DS Sep 1, 2022

by admin

577 views

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

admin asked in Graph Theory Sep 1, 2022

by admin

899 views

1 vote

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}$

admin asked in Compiler Design Sep 1, 2022

by admin

483 views

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

admin asked in Theory of Computation Sep 1, 2022

by admin

356 views

1 vote

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)$

admin asked in Combinatory Sep 1, 2022

by admin

324 views

1 vote

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.

admin asked in Algorithms Sep 1, 2022

by admin

356 views

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

admin asked in Algorithms Sep 1, 2022

by admin

419 views

1 vote

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

admin asked in Graph Theory Sep 1, 2022

by admin

353 views

1 vote

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:\; =$

admin asked in Algorithms Sep 1, 2022

by admin

283 views

1 vote

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$

admin asked in Graph Theory Sep 1, 2022

by admin

440 views

1 vote

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$

admin asked in Linear Algebra Sep 1, 2022

by admin

345 views

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

admin asked in Combinatory Sep 1, 2022

by admin

565 views

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$

admin asked in Probability Sep 1, 2022

by admin

772 views

1 vote

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

admin asked in Theory of Computation Sep 1, 2022

by admin

602 views

1 vote

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

admin asked in Linear Algebra Sep 1, 2022

by admin

686 views

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}$

admin asked in Probability Sep 1, 2022

by admin

445 views

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

admin asked in Calculus Sep 1, 2022

by admin

685 views

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

admin asked in Probability Sep 1, 2022

by admin

569 views

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

admin asked in Linear Algebra Sep 1, 2022

by admin

660 views

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|$

admin asked in Set Theory & Algebra Sep 1, 2022

by admin

390 views

1 vote

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)}$

admin asked in Probability Sep 1, 2022

by admin

563 views

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

admin asked in Set Theory & Algebra Sep 1, 2022

by admin

308 views

1 vote

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$

admin asked in Probability Sep 1, 2022

by admin

503 views

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

admin asked in Theory of Computation Sep 1, 2022

by admin

393 views

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$

admin asked in Calculus Sep 1, 2022

by admin

324 views

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$

admin asked in Probability Sep 1, 2022

by admin

461 views

To see more, click for the full list of questions or popular tags.

Recent questions tagged tifr2022