Recent questions tagged gatecse-2006 / GATE Overflow for GATE CSE

77 votes

9 answers

61

GATE CSE 2006 | Question: 25
Let $S = \{1, 2, 3,\ldots, m\}, m >3.$ Let $X_1,\ldots,X_n$ be subsets of $S$ each of size $3.$ Define a function $f$ from $S$ to the set of natural numbers as, $f(i)$ is the number of sets $X_j$ that contain the element $i.$ That is $f(i)=\left | \left\{j \mid i\in X_j \right\} \right|$ then $ \sum_{i=1}^{m} f(i)$ is: $3m$ $3n$ $2m+1$ $2n+1$

Let $S = \{1, 2, 3,\ldots, m\}, m >3.$ Let $X_1,\ldots,X_n$ be subsets of $S$ each of size $3.$ Define a function $f$ from $S$ to the set of natural numbers as, $f(i)$ is...

Rucha Shelke

11.1k views

Rucha Shelke asked Sep 18, 2014

58 votes

7 answers

62

GATE CSE 2006 | Question: 24
Given a set of elements $N = {1, 2, ..., n}$ and two arbitrary subsets $A⊆N$ and $B⊆N$, how many of the n! permutations $\pi$ from $N$ to $N$ satisfy $\min(\pi(A)) = \min(\pi(B))$, where $\min(S)$ is the smallest integer in the set of integers $S$, and $\pi$(S) is the set of ... $n! \frac{|A ∩ B|}{|A ∪ B|}$ $\dfrac{|A ∩ B|^2}{^n \mathrm{C}_{|A ∪ B|}}$

Given a set of elements $N = {1, 2, ..., n}$ and two arbitrary subsets $A⊆N$ and $B⊆N$, how many of the n! permutations $\pi$ from $N$ to $N$ satisfy $\min(\pi(A)) = ...

Rucha Shelke

11.3k views

Rucha Shelke asked Sep 18, 2014

44 votes

5 answers

63

GATE CSE 2006 | Question: 23
$F$ is an $n\times n$ real matrix. $b$ is an $n\times 1$ real vector. Suppose there are two $n\times 1$ vectors, $u$ and $v$ such that, $u ≠ v$ and $Fu = b, Fv = b$. Which one of the following statements is false? Determinant of $F$ is zero. There are an infinite number of solutions to $Fx = b$ There is an $x≠0$ such that $Fx = 0$ $F$ must have two identical rows

$F$ is an $n\times n$ real matrix. $b$ is an $n\times 1$ real vector. Suppose there are two $n\times 1$ vectors, $u$ and $v$ such that, $u ≠ v$ and $Fu = b, Fv = b$. Wh...

Rucha Shelke

10.1k views

Rucha Shelke asked Sep 17, 2014

25 votes

8 answers

64

GATE CSE 2006 | Question: 22
Let $E, F$ and $G$ be finite sets. Let $X = (E ∩ F) - (F ∩ G)$ and $Y = (E - (E ∩ G)) - (E - F)$. Which one of the following is true? $X ⊂ Y$ $X ⊃ Y$ $X = Y$ $X - Y ≠ \emptyset$ and $Y - X ≠ \emptyset$

Let $E, F$ and $G$ be finite sets. Let$X = (E ∩ F) - (F ∩ G)$ and$Y = (E - (E ∩ G)) - (E - F)$.Which one of the following is true?$X ⊂ Y$$X ⊃ Y$$X = Y$$X - Y �...

Rucha Shelke

6.7k views

Rucha Shelke asked Sep 17, 2014

36 votes

7 answers

65

GATE CSE 2006 | Question: 21
For each element in a set of size $2n$, an unbiased coin is tossed. The $2n$ coin tosses are independent. An element is chosen if the corresponding coin toss was a head. The probability that exactly $n$ elements are chosen is $\frac{^{2n}\mathrm{C}_n}{4^n}$ $\frac{^{2n}\mathrm{C}_n}{2^n}$ $\frac{1}{^{2n}\mathrm{C}_n}$ $\frac{1}{2}$

For each element in a set of size $2n$, an unbiased coin is tossed. The $2n$ coin tosses are independent. An element is chosen if the corresponding coin toss was a head. ...

Rucha Shelke

8.2k views

Rucha Shelke asked Sep 17, 2014

69 votes

9 answers

66

GATE CSE 2006 | Question: 20, ISRO2015-17
Consider the following log sequence of two transactions on a bank account, with initial balance $12000,$ that transfer $2000$ to a mortgage payment and then apply a $5\%$ interest. T1 start T1 B old $=12000$ new $=10000$ ... $3$ because transaction T1 has committed We can apply redo and undo operations in arbitrary order because they are idempotent

Consider the following log sequence of two transactions on a bank account, with initial balance $12000,$ that transfer $2000$ to a mortgage payment and then apply a $5\%$...

Rucha Shelke

28.1k views

Rucha Shelke asked Sep 17, 2014

51 votes

6 answers

67

GATE CSE 2006 | Question: 19
Let $L_1=\{0^{n+m}1^n0^m\mid n,m\geq 0 \}$, $L_2=\{0^{n+m}1^{n+m}0^m\mid n,m\geq 0\}$ and $L_3=\{0^{n+m}1^{n+m}0^{n+m}\mid n,m\geq 0\} $. Which of these languages are NOT context free? $L_1$ only $L_3$ only $L_1$ and $L_2$ $L_2$ and $L_3$

Let$L_1=\{0^{n+m}1^n0^m\mid n,m\geq 0 \}$,$L_2=\{0^{n+m}1^{n+m}0^m\mid n,m\geq 0\}$ and$L_3=\{0^{n+m}1^{n+m}0^{n+m}\mid n,m\geq 0\} $. Which of these languages are NOT c...

Rucha Shelke

15.5k views

Rucha Shelke asked Sep 17, 2014

41 votes

5 answers

68

GATE CSE 2006 | Question: 18
We are given a set $X = \{X_1,\ldots,X_n\}$ where $X_i=2^i$. A sample $S\subseteq X$ is drawn by selecting each $X_i$ independently with probability $P_i = \frac{1}{2}$ . The expected value of the smallest number in sample $S$ is: $\left(\frac{1}{n}\right)$ $2$ $\sqrt n$ $n$

We are given a set $X = \{X_1,\ldots,X_n\}$ where $X_i=2^i$. A sample $S\subseteq X$ is drawn by selecting each $X_i$ independently with probability $P_i = \frac{1}{2...

Rucha Shelke

16.1k views

Rucha Shelke asked Sep 17, 2014

59 votes

7 answers

69

GATE CSE 2006 | Question: 17
An element in an array $X$ is called a leader if it is greater than all elements to the right of it in $X$. The best algorithm to find all leaders in an array solves it in linear time using a left to right pass of the array solves it in linear time using ... pass of the array solves it using divide and conquer in time $\Theta (n\log n)$ solves it in time $\Theta( n^2)$

An element in an array $X$ is called a leader if it is greater than all elements to the right of it in $X$. The best algorithm to find all leaders in an array solves it i...

Rucha Shelke

18.0k views

Rucha Shelke asked Sep 17, 2014

21 votes

5 answers

70

GATE CSE 2006 | Question: 16, ISRO-DEC2017-27
Let S be an NP-complete problem and Q and R be two other problems not known to be in NP. Q is polynomial time reducible to S and S is polynomial-time reducible to R. Which one of the following statements is true? R is NP-complete R is NP-hard Q is NP-complete Q is NP-hard

Let S be an NP-complete problem and Q and R be two other problems not known to be in NP. Q is polynomial time reducible to S and S is polynomial-time reducible to R. Whic...

Rucha Shelke

18.1k views

Rucha Shelke asked Sep 17, 2014

35 votes

10 answers

71

GATE CSE 2006 | Question: 15
Consider the following C-program fragment in which $i$, $j$ and $n$ are integer variables. for( i = n, j = 0; i > 0; i /= 2, j +=i ); Let $val(j)$ denote the value stored in the variable $j$ after termination of the for loop. Which one of the following is true? $val(j)=\Theta(\log n)$ $val(j)=\Theta (\sqrt{n})$ $val(j)=\Theta( n)$ $val(j)=\Theta (n\log n)$

Consider the following C-program fragment in which $i$, $j$ and $n$ are integer variables. for( i = n, j = 0; i 0; i /= 2, j +=i );Let $val(j)$ denote the value stored i...

Rucha Shelke

19.5k views

Rucha Shelke asked Sep 17, 2014

39 votes

4 answers

72

GATE CSE 2006 | Question: 14, ISRO2011-14
Which one of the following in place sorting algorithms needs the minimum number of swaps? Quick sort Insertion sort Selection sort Heap sort

Which one of the following in place sorting algorithms needs the minimum number of swaps?Quick sortInsertion sortSelection sortHeap sort

Rucha Shelke

25.4k views

Rucha Shelke asked Sep 17, 2014

67 votes

4 answers

73

GATE CSE 2006 | Question: 13
A scheme for storing binary trees in an array $X$ is as follows. Indexing of $X$ starts at $1$ instead of $0$. the root is stored at $X[1]$. For a node stored at $X[i]$, the left child, if any, is stored in $X[2i]$ and the right child, if any, in $X[2i+1]$. To be able to store any binary tree on n vertices the minimum size of $X$ should be $\log_2 n$ $n$ $2n+1$ $2^n-1$

A scheme for storing binary trees in an array $X$ is as follows. Indexing of $X$ starts at $1$ instead of $0$. the root is stored at $X $. For a node stored at $X[i]$, th...

Rucha Shelke

17.3k views

Rucha Shelke asked Sep 17, 2014

59 votes

7 answers

74

GATE CSE 2006 | Question: 12
To implement Dijkstra’s shortest path algorithm on unweighted graphs so that it runs in linear time, the data structure to be used is: Queue Stack Heap B-Tree

To implement Dijkstra’s shortest path algorithm on unweighted graphs so that it runs in linear time, the data structure to be used is:QueueStackHeapB-Tree

Rucha Shelke

31.7k views

Rucha Shelke asked Sep 16, 2014

32 votes

7 answers

75

GATE CSE 2006 | Question: 11
Consider a weighted complete graph $G$ on the vertex set $\{v_1,v_2,.....v_n\}$ such that the weight of the edge $(v_i, v_j)$ is $2|i-j|$. The weight of a minimum spanning tree of $G$ is: $n-1$ $2n-2$ $\begin{pmatrix} n \\ 2 \end{pmatrix}$ $n^2$

Consider a weighted complete graph $G$ on the vertex set $\{v_1,v_2,.....v_n\}$ such that the weight of the edge $(v_i, v_j)$ is $2|i-j|$. The weight of a minimum spanni...

Rucha Shelke

14.9k views

Rucha Shelke asked Sep 16, 2014

44 votes

5 answers

76

GATE CSE 2006 | Question: 10
In a binary max heap containing $n$ numbers, the smallest element can be found in time $O(n)$ $O(\log n)$ $O(\log \log n)$ $O(1)$

In a binary max heap containing $n$ numbers, the smallest element can be found in time $O(n)$ $O(\log n)$ $O(\log \log n)$ $O(1)$

Rucha Shelke

20.8k views

Rucha Shelke asked Sep 16, 2014

41 votes

11 answers

77

GATE CSE 2006 | Question: 09, ISRO2009-35
A CPU has $24$-$bit$ instructions. A program starts at address $300$ (in decimal). Which one of the following is a legal program counter (all values in decimal)? $400$ $500$ $600$ $700$

A CPU has $24$-$bit$ instructions. A program starts at address $300$ (in decimal). Which one of the following is a legal program counter (all values in decimal)?$400$$500...

Rucha Shelke

16.1k views

Rucha Shelke asked Sep 16, 2014

70 votes

5 answers

78

GATE CSE 2006 | Question: 8
You are given a free running clock with a duty cycle of $50\%$ and a digital waveform $f$ which changes only at the negative edge of the clock. Which one of the following circuits (using clocked D flip-flops) will delay the phase of $f$ by $180°$?

You are given a free running clock with a duty cycle of $50\%$ and a digital waveform $f$ which changes only at the negative edge of the clock. Which one of the following...

Rucha Shelke

18.7k views

Rucha Shelke asked Sep 16, 2014

29 votes

6 answers

79

GATE CSE 2006 | Question: 7
Consider the following grammar $S \rightarrow S * E$ $S \rightarrow E$ $E \rightarrow F + E$ $E \rightarrow F$ $F \rightarrow id$ Consider the following LR(0) items corresponding to the grammar above $S \rightarrow S *.E$ $E \rightarrow F. + E$ ... will appear in the same set in the canonical sets-of-items for the grammar? i and ii ii and iii i and iii None of the above

Consider the following grammar$S \rightarrow S * E$$S \rightarrow E$$E \rightarrow F + E$$E \rightarrow F$$F \rightarrow id$Consider the following LR(0) items corres...

Rucha Shelke

11.7k views

Rucha Shelke asked Sep 16, 2014

39 votes

4 answers

80

GATE CSE 2006 | Question: 06, ISRO2009-14
Consider three CPU-intensive processes, which require $10$, $20$ and $30$ time units and arrive at times $0$, $2$ and $6$, respectively. How many context switches are needed if the operating system implements a shortest remaining time first scheduling algorithm? Do not count the context switches at time zero and at the end. $1$ $2$ $3$ $4$

Consider three CPU-intensive processes, which require $10$, $20$ and $30$ time units and arrive at times $0$, $2$ and $6$, respectively. How many context switches are nee...

Rucha Shelke

16.0k views

Rucha Shelke asked Sep 16, 2014

26 votes

4 answers

81

GATE CSE 2006 | Question: 5
For which one of the following reasons does internet protocol(IP) use the time-to-live(TTL) field in IP datagram header? Ensure packets reach destination within that time Discard packets that reach later than that time Prevent packets from looping indefinitely Limit the time for which a packet gets queued in intermediate routers

For which one of the following reasons does internet protocol(IP) use the time-to-live(TTL) field in IP datagram header?Ensure packets reach destination within that timeD...

Rucha Shelke

11.4k views

Rucha Shelke asked Sep 16, 2014

33 votes

5 answers

82

GATE CSE 2006 | Question: 4
A relation $R$ is defined on ordered pairs of integers as follows: $(x,y)R(u,v) \text{ if } x<u \text{ and } y>v$ Then $R$ is: Neither a Partial Order nor an Equivalence Relation A Partial Order but not a Total Order A total Order An Equivalence Relation

A relation $R$ is defined on ordered pairs of integers as follows: $$(x,y)R(u,v) \text{ if } x<u \text{ and } y>v$$ Then $R$ is: Neither a Partial Order nor an Equivale...

Rucha Shelke

7.7k views

Rucha Shelke asked Sep 16, 2014

43 votes

5 answers

83

GATE CSE 2006 | Question: 3
The set $\{1,2,3,5,7,8,9\}$ under multiplication modulo $10$ is not a group. Given below are four possible reasons. Which one of them is false? It is not closed $2$ does not have an inverse $3$ does not have an inverse $8$ does not have an inverse

The set $\{1,2,3,5,7,8,9\}$ under multiplication modulo $10$ is not a group. Given below are four possible reasons. Which one of them is false?It is not closed$2$ does no...

Rucha Shelke

9.9k views

Rucha Shelke asked Sep 16, 2014

36 votes

4 answers

84

GATE CSE 2006 | Question: 2
Let $X,Y,Z$ be sets of sizes $x, y$ and $z$ respectively. Let $W = X \times Y$ and $E$ be the set of all subsets of $W$. The number of functions from $Z$ to $E$ is $z^{2^{xy}}$ $z \times 2^{xy}$ $z^{2^{x+y}}$ $2^{xyz}$

Let $X,Y,Z$ be sets of sizes $x, y$ and $z$ respectively. Let $W = X \times Y$ and $E$ be the set of all subsets of $W$. The number of functions from $Z$ to $E$ is$z^{2^{...

Rucha Shelke

7.1k views

Rucha Shelke asked Sep 16, 2014

30 votes

3 answers

85

GATE CSE 2006 | Question: 1, ISRO2009-57
Consider the polynomial $p(x) = a_0 + a_1x + a_2x^2 + a_3x^3$ , where $a_i \neq 0$, $\forall i$. The minimum number of multiplications needed to evaluate $p$ on an input $x$ is: 3 4 6 9

Consider the polynomial $p(x) = a_0 + a_1x + a_2x^2 + a_3x^3$ , where $a_i \neq 0$, $\forall i$. The minimum number of multiplications needed to evaluate $p$ on an input ...

gatecse

11.5k views

gatecse asked Sep 15, 2014

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