Recent questions tagged descriptive / GATE Overflow for GATE CSE

0 votes

0 answers

91

ISI 2019 | PCB Mathematics | Question: 10
Let $f_{1}:[0,4] \rightarrow[0,4]$ be defined by $f_{1}(x)=3-(x / 2)$. Define $f_{n}(x)=$ $f_{1}\left(f_{n-1}(x)\right)$ for $n \geq 2$. Prove that $\displaystyle{}\lim _{n \rightarrow \infty} f_{n}(0)$ exists. Find the set of all $x$ such that $\displaystyle{}\lim _{n \rightarrow \infty} f_{n}(x)$ exists and also find the corresponding limits.

Let $f_{1}:[0,4] \rightarrow[0,4]$ be defined by $f_{1}(x)=3-(x / 2)$. Define $f_{n}(x)=$ $f_{1}\left(f_{n-1}(x)\right)$ for $n \geq 2$.Prove that $\displaystyle{}\lim _{...

admin

71 views

admin asked Aug 8, 2022

0 votes

0 answers

92

ISI 2019 | PCB Mathematics | Question: 11
Let $m$ be a fixed integer greater than $2.$ Prove that all simple graphs having $n\;(n \geq 3)$ vertices and with $m$ edges are connected if and only if $m>\left(\begin{array}{c}n-1 \\ 2\end{array}\right)$.

Let $m$ be a fixed integer greater than $2.$ Prove that all simple graphs having $n\;(n \geq 3)$ vertices and with $m$ edges are connected if and only if $m>\left(\begin{...

admin

150 views

admin asked Aug 8, 2022

0 votes

0 answers

93

ISI 2019 | PCB Mathematics | Question: 12
Suppose the collection $\left\{A_{1}, \cdots, A_{k}\right\}$ forms a group under matrix multiplication, where each $A_{i}$ is an $n \times n$ real matrix. Let $\displaystyle{}A=\sum_{i=1}^{k} A_{i}$. Show that $A^{2}=k A$. If the trace of $A$ is zero, then show that $A$ is the zero matrix.

Suppose the collection $\left\{A_{1}, \cdots, A_{k}\right\}$ forms a group under matrix multiplication, where each $A_{i}$ is an $n \times n$ real matrix. Let $\displayst...

admin

119 views

admin asked Aug 8, 2022

0 votes

0 answers

94

ISI 2019 | PCB Mathematics | Question: 13
Let $A$ be an $n \times n$ integer matrix whose entries are all even. Show that the determinant of $A$ is divisible by $2^{n}$. Hence or otherwise, show that if $B$ is an $n \times n$ matrix whose entries are $\pm 1$, then the determinant of $B$ is divisible by $2^{n-1}$.

Let $A$ be an $n \times n$ integer matrix whose entries are all even. Show that the determinant of $A$ is divisible by $2^{n}$. Hence or otherwise, show that if $B$ is an...

admin

70 views

admin asked Aug 8, 2022

0 votes

0 answers

95

ISI 2019 | PCB Mathematics | Question: 15
Let $n, r, s$ be positive integers, each greater than $2.$ Prove that $n^{r}-1$ divides $n^{s}-1$ if and only if $r$ divides $s.$

Let $n, r, s$ be positive integers, each greater than $2.$ Prove that $n^{r}-1$ divides $n^{s}-1$ if and only if $r$ divides $s.$

admin

74 views

admin asked Aug 8, 2022

0 votes

1 answer

96

ISI 2019 | PCB Mathematics | Question: 17
Show that $5|x|+x(x-2) \geq 0$ for every real number $x.$

Show that $5|x|+x(x-2) \geq 0$ for every real number $x.$

admin

212 views

admin asked Aug 8, 2022

0 votes

0 answers

97

ISI 2019 | PCB Mathematics | Question: 19
Let $G$ be a finite group and $H$ the only subgroup of $G$ of order $|H|$. Prove that $H$ is normal in $G.$

Let $G$ be a finite group and $H$ the only subgroup of $G$ of order $|H|$. Prove that $H$ is normal in $G.$

admin

157 views

admin asked Aug 8, 2022

0 votes

0 answers

98

ISI 2019 | PCB Mathematics | Question: 20
Let $H$ and $K$ be subgroups of a group $G$ of finite indices $(\text{i.e.}, [G: H]<$ $\infty$ and $[G: K]<\infty).$ Prove that $H \cap K$ is also of finite index $(\text{i.e.}, [G: H \cap K]<\infty).$

Let $H$ and $K$ be subgroups of a group $G$ of finite indices $(\text{i.e.}, [G: H]<$ $\infty$ and $[G: K]<\infty).$ Prove that $H \cap K$ is also of finite index $(\text...

admin

70 views

admin asked Aug 8, 2022

5 votes

1 answer

99

ISI 2019 | PCB Mathematics | Question: 22
If $\alpha, \beta, \gamma$ are the roots of the equation $x^{3}+6 x+1=0$, then prove that $ \frac{\alpha}{\beta}+\frac{\beta}{\alpha}+\frac{\beta}{\gamma}+\frac{\gamma}{\beta}+\frac{\gamma}{\alpha}+\frac{\alpha}{\gamma}=-3. $

If $\alpha, \beta, \gamma$ are the roots of the equation $x^{3}+6 x+1=0$, then prove that $$ \frac{\alpha}{\beta}+\frac{\beta}{\alpha}+\frac{\beta}{\gamma}+\frac{\gamma}{...

admin

227 views

admin asked Aug 8, 2022

0 votes

0 answers

100

ISI 2019 | PCB Mathematics | Question: 23
Let $X \sim \operatorname{Bin}(n, p)$, and $Y \sim \operatorname{Poisson}\; (\lambda)$. Let $ T=X_{1}+X_{2}+\cdots+X_{Y}, $ with $X_{i} \text{'s i. i. d}.\; \operatorname{Bin}(n, p)\;($and independent to $Y),$ ... $X).$ Compare Expectations of $T$ and $S$ and Variances of $T$ and $S.$

Let $X \sim \operatorname{Bin}(n, p)$, and $Y \sim \operatorname{Poisson}\; (\lambda)$. Let $$ T=X_{1}+X_{2}+\cdots+X_{Y}, $$ with $X_{i} \text{'s i. i. d}.\; \operatorna...

admin

91 views

admin asked Aug 8, 2022

1 votes

1 answer

101

ISI 2019 | PCB CS | Question: 1
Let $A$ be a sorted array containing $n$ distinct integers, such that, for all $1 \leq i<j \leq n$, we have $A[i]<A[j]$. Note that the integers stored in the array $A$ ... time of the algorithm should be asymptotically better than $O(n)$. Prove the correctness of your algorithm and state its asymptotic time complexity.

Let $A$ be a sorted array containing $n$ distinct integers, such that, for all $1 \leq i<j \leq n$, we have $A[i]<A[j]$. Note that the integers stored in the array $A$ ar...

admin

165 views

admin asked Aug 8, 2022

0 votes

0 answers

102

ISI 2019 | PCB CS | Question: 3
When we add a pair of two-bit binary numbers, say $a b$ and $c d$, we get a number of at most three bits, say $p q r$. Using standard operators of Boolean algebra, namely $\operatorname{AND}\;(\wedge), \operatorname{OR}\; (\vee)$ and $\operatorname{NOT}\;(\neg)$, derive the Boolean expressions of $p, q$ and $r$ in terms of $a, b, c$ and $d$.

When we add a pair of two-bit binary numbers, say $a b$ and $c d$, we get a number of at most three bits, say $p q r$. Using standard operators of Boolean algebra, namely...

admin

97 views

admin asked Aug 8, 2022

0 votes

0 answers

103

ISI 2019 | PCB CS | Question: 4
In a binary tree $T$, for a node $v$, the $\text{LEFT-HEIGHT} (v)$ is the length of the longest path from $v$ to any leaf in the left subtree of $v$. If $v$ has no left child then $\text{LEFT-HEIGHT} (v)=0$ ... Design an efficient algorithm that, given a binary tree, enumerates all the nodes which are properly balanced.

In a binary tree $T$, for a node $v$, the $\text{LEFT-HEIGHT} (v)$ is the length of the longest path from $v$ to any leaf in the left subtree of $v$. If $v$ has no left c...

admin

102 views

admin asked Aug 8, 2022

1 votes

1 answer

104

ISI 2019 | PCB CS | Question: 5
Consider a stack machine where the only available workspace is a stack whose elements are unsigned integers. We will denote the configuration of the stack by a sequence. For example $[a, b, c, d]$ represents a stack with $a$ being the ... $a b$.

Consider a stack machine where the only available workspace is a stack whose elements are unsigned integers. We will denote the configuration of the stack by a sequence. ...

admin

417 views

admin asked Aug 8, 2022

0 votes

0 answers

105

ISI 2019 | PCB CS | Question: 6
Consider the alphabet $\Sigma=\{0,1,2, \ldots, 9, \#\}$, and the language of strings of the form $x \# y \# z$, where $x, y$ and $z$ are strings of digit such that when viewed as numbers, satisfy the equation $x+y=z$. For example, the string $123 \# 45 \# 168$ is in this language because $123+45=168$. Is this language regular? Justify your answer.

Consider the alphabet $\Sigma=\{0,1,2, \ldots, 9, \#\}$, and the language of strings of the form $x \# y \# z$, where $x, y$ and $z$ are strings of digit such that when v...

admin

178 views

admin asked Aug 8, 2022

0 votes

0 answers

106

ISI 2019 | PCB CS | Question: 7
Recall that in go-back-$N$ protocol, the transmitting window size is $N$ and the receiver window size is $1.$ Consider a pipelined, reliable transport protocol that uses go-back-$N$ with cumulative acknowledgment. Assume that the timeouts trigger retransmissions (but note ... $1 \mathrm{~Gb} / \mathrm{s}$. The bottleneck link rate is $2 \mathrm{~Gb} / \mathrm{s}$.

Recall that in go-back-$N$ protocol, the transmitting window size is $N$ and the receiver window size is $1.$ Consider a pipelined, reliable transport protocol that uses ...

admin

167 views

admin asked Aug 8, 2022

0 votes

0 answers

107

ISI 2019 | PCB CS | Question: 8
Let us assume that a disk scheduling algorithm is applied on a storage disk to access several cylinders (numbered as $0,1, \ldots, n$ ... first the disk head accesses all the cylinders while moving toward cylinder $0$ and then the disk head moves toward the other end.

Let us assume that a disk scheduling algorithm is applied on a storage disk to access several cylinders (numbered as $0,1, \ldots, n$ arranged in ascending order) for som...

admin

164 views

admin asked Aug 8, 2022

0 votes

0 answers

108

ISI 2019 | PCB CS | Question: 9
Consider a byte addressable memory with $16$ bit addresses and a $2$- way set associative $\mathrm{L} 1$ cache of size $8 \mathrm{ kB}$ (kilobyte). Each cache line is $4$ words long. A process sequentially accesses the following memory ... replacement policy is used, indicate whether the cache access will result in a hit or a miss for each of the above addresses.

Consider a byte addressable memory with $16$ bit addresses and a $2$- way set associative $\mathrm{L} 1$ cache of size $8 \mathrm{ kB}$ (kilobyte). Each cache line is $4$...

admin

216 views

admin asked Aug 8, 2022

0 votes

1 answer

109

ISI 2019 | PCB CS | Question: 10
Let $R$ be a relation with functional dependencies $\mathcal{F}$. For any subset of attributes $X \subseteq R$, the closure of $X$ is defined as the set $ X^{+}=\{A \in R \mid X \rightarrow A \text { holds with respect to } \mathcal{F}\} . $ For two non-empty ... each of the following statements: $\left(Y^{+} Z\right)^{+}=(Y Z)^{+}$ $(Y Z)^{+}=Y^{+} Z^{+}$

Let $R$ be a relation with functional dependencies $\mathcal{F}$. For any subset of attributes $X \subseteq R$, the closure of $X$ is defined as the set$$ X^{+}=\{A \in R...

admin

87 views

admin asked Aug 8, 2022

0 votes

2 answers

110

ISI 2019 | PCB CS | Question: 11
Consider an array of length $n$ consisting only of positive and negative integers. Design an algorithm to rearrange the array so that all the negative integers appear before all the positive integers, using $O(n)$ time and only constant amount of extra space.

Consider an array of length $n$ consisting only of positive and negative integers. Design an algorithm to rearrange the array so that all the negative integers appear bef...

admin

360 views

admin asked Aug 8, 2022

1 votes

1 answer

111

ISI 2019 | PCB CS | Question: 12
You can climb up a staircase of $n$ stairs by taking steps of one or two stairs at a time. Formulate a recurrence relation for counting $a_{n},$ the number of distinct ways in which you can climb up the staircase. Mention the boundary conditions for your recurrence relation. Find a closed form expression for $a_{n}$ by solving your recurrence.

You can climb up a staircase of $n$ stairs by taking steps of one or two stairs at a time.Formulate a recurrence relation for counting $a_{n},$ the number of distinct way...

admin

102 views

admin asked Aug 8, 2022

0 votes

0 answers

112

ISI 2019 | PCB CS | Question: 13
An $n$-variable Boolean function $f:\{0,1\}^{n} \rightarrow\{0,1\}$ is called symmetric if its value depends only on the number of $1 \text{'s}$ in the input. Let $\sigma_{n}$ denote the number of such functions. Calculate the value of $\sigma_{4}$. Derive an expression for $\sigma_{n}$ in terms of $n$.

An $n$-variable Boolean function $f:\{0,1\}^{n} \rightarrow\{0,1\}$ is called symmetric if its value depends only on the number of $1 \text{'s}$ in the input. Let $\sigma...

admin

59 views

admin asked Aug 8, 2022

0 votes

0 answers

113

ISI 2019 | PCB CS | Question: 14
Let the valid moves along a staircase be $U$ (one step up) and $D$ (one step down). For example, the string $s=U U D U$ represents the sequence of moves as two steps up, then one step down, and then again one step up. Suppose a person ... to the base of the staircase after the final step. Show that $L$ is not regular. Write a context free grammar for accepting $L$.

Let the valid moves along a staircase be $U$ (one step up) and $D$ (one step down). For example, the string $s=U U D U$ represents the sequence of moves as two steps up, ...

admin

77 views

admin asked Aug 8, 2022

2 votes

2 answers

114

ISI 2019 | PCB CS | Question: 15
Consider a max-heap of $n$ distinct integers, $n \geq 4$, stored in an array $\mathcal{A}[1 \ldots n]$. The second minimum of $\mathcal{A}$ is the integer that is less than all integers in $\mathcal{A}$ except the minimum of $\mathcal{A}$. Find all possible array indices of $\mathcal{A}$ in which the second minimum can occur. Justify your answer.

Consider a max-heap of $n$ distinct integers, $n \geq 4$, stored in an array $\mathcal{A}[1 \ldots n]$. The second minimum of $\mathcal{A}$ is the integer that is less th...

admin

165 views

admin asked Aug 8, 2022

0 votes

0 answers

115

ISI 2019 | PCB CS | Question: 16
The following function computes an array $\textsf{SPF},$ where, for any integer $1<1<1000, \textsf{SPF[i]}$ is the smallest prime factor of $\textsf{i}.$ For example, $\textsf{SPF[6]}$ is $2,$ and $\textsf{SPF[11]}$ is $11.$ There are five missing parts in the following code, ... ){ /* Blank 4 */ if (SPF[j] == j) { SPF[j] = _ _ _ _ _; /* Blank 5 */ } } } } }

The following function computes an array $\textsf{SPF},$ where, for any integer $1<1<1000, \textsf{SPF[i]}$ is the smallest prime factor of $\textsf{i}.$ For example, $\t...

admin

67 views

admin asked Aug 8, 2022

0 votes

0 answers

116

ISI 2019 | PCB CS | Question: 17
A context switch from a process $P_{old}$ to a process $P_{new }$ consists of the following steps: - Step I: saving the context of $P_{old};$ Step II: running the scheduling algorithm to pick $P_{new};$ ... each process requires exactly one $\mathrm{CPU}$ burst of $20 \mathrm{~ms}$ and no $\mathrm{I} / \mathrm{O}$ burst.

A context switch from a process $P_{old}$ to a process $P_{new }$ consists of the following steps: -Step I: saving the context of $P_{old};$ Step II: running the scheduli...

admin

70 views

admin asked Aug 8, 2022

0 votes

1 answer

117

ISI 2019 | PCB CS | Question: 18
Consider a $5$-stage instruction pipeline. The stages and the corresponding stage delays are given below. Instruction Stage delay Fetch instruction (FI) 3 ns Decode instruction (DI) 4 ns Fetch operand (FO) 7 ns Execute instruction (EI) 10 ns Write ... flow through the pipeline stages in this processor. Calculate the time (in ns) needed to execute the program.

Consider a $5$-stage instruction pipeline. The stages and the corresponding stage delays are given below. InstructionStage delayFetch instruction (FI)3 nsDecode instruct...

admin

217 views

admin asked Aug 8, 2022

0 votes

0 answers

118

ISI 2019 | PCB CS | Question: 19
The data link layer uses a fixed-size sliding window protocol, where the window size for the connection is equal to twice the bandwidth-delay product of the network path. Consider the following three scenarios, in each of which only the given parameter changes as specified ( ... the round trip time $R$ increases to $1.8 R;$ the window size $W$ decreases to $W / 3.$

The data link layer uses a fixed-size sliding window protocol, where the window size for the connection is equal to twice the bandwidth-delay product of the network path....

admin

80 views

admin asked Aug 8, 2022

0 votes

0 answers

119

ISI 2019 | PCB CS | Question: 20
Consider two $n \times 1$ vectors u and v, stored as tables $\mathrm{U(ind, val)}$ and $\mathrm{V(ind, val)}$ with the same schema. A row $\left(i, u_{i}\right)$ of table $\mathrm{U}$ specifies that the $i$-th element of vector u ... a relational algebra expression or an $\text{SQL}$ query to compute the sum u $+$ v of the two vectors u and v. Explain your solution.

Consider two $n \times 1$ vectors u and v, stored as tables $\mathrm{U(ind, val)}$ and $\mathrm{V(ind, val)}$ with the same schema. A row $\left(i, u_{i}\right)$ of tabl...

admin

99 views

admin asked Aug 8, 2022

0 votes

1 answer

120

ISI 2021 | PCB CS | Question: 2
Let $P$ be a set of $n$ real numbers. For any two real numbers $a$ and $b$ $(a<b),$ define $ R(a, b)=|\{x \in P \mid a \leq x \leq b\}| . $ Design a suitable data structure $\mathcal{D}$ to store $P$ ... your data structure $\mathcal{D}$. Justify that $O(\log n)$ time is sufficient for reporting $R(a, b)$ using your data structure $\mathcal{D}$.

Let $P$ be a set of $n$ real numbers. For any two real numbers $a$ and $b$ $(a<b),$ define $$ R(a, b)=|\{x \in P \mid a \leq x \leq b\}| . $$Design a suitable data struct...

admin

376 views

admin asked Aug 8, 2022

tags	tag:apple
author	user:martin
title	title:apple
content	content:apple
exclude	-tag:apple
force match	+apple
views	views:100
score	score:10
answers	answers:2
is accepted	isaccepted:true
is closed	isclosed:true