Recent activity by Musa / GATE Overflow for GATE CSE

5 answers

1

ISRO2014-33
The following Finite Automaton recognizes which of the given languages? $\{ 1, 0 \}^* \{ 0 1 \}$ $\{ 1,0\}^*\{ 1\}$ $\{ 1 \} \{1, 0\}^*\{ 1 \}$ $1^*0^*\{0,1\}$

The following Finite Automaton recognizes which of the given languages?$\{ 1, 0 \}^* \{ 0 1 \}$$\{ 1,0\}^*\{ 1\}$$\{ 1 \} \{1, 0\}^*\{ 1 \}$$1^*0^*\{0,1\}$

5.5k views

answer edited Aug 2, 2021

3 answers

2

GATE CSE 1987 | Question: 2n
State whether the following statements are TRUE or FALSE: A relation $r$ with schema $(X, Y)$ satisfies the function dependency $X \rightarrow Y$, The tuples $\langle 1, 2\rangle$ and $\langle 2, 2 \rangle$ can both be in $r$ simultaneously.

State whether the following statements are TRUE or FALSE:A relation $r$ with schema $(X, Y)$ satisfies the function dependency $X \rightarrow Y$, The tuples $\langle 1, 2...

3.6k views

answered Dec 9, 2020

3 answers

3

GATE CSE 2004 | Question: 54
$A$ and $B$ are the only two stations on an Ethernet. Each has a steady queue of frames to send. Both $A$ and $B$ attempt to transmit a frame, collide, and $A$ wins the first backoff race. At the end of this successful transmission by $A$, both $A$ ... attempt to transmit and collide. The probability that $A$ wins the second backoff race is: $0.5$ $0.625$ $0.75$ $1.0$

$A$ and $B$ are the only two stations on an Ethernet. Each has a steady queue of frames to send. Both $A$ and $B$ attempt to transmit a frame, collide, and $A$ wins the f...

16.9k views

answered Nov 28, 2020

4 answers

4

GATE CSE 2005 | Question: 14
The grammar $A \rightarrow AA \mid (A) \mid \epsilon$ is not suitable for predictive-parsing because the grammar is: ambiguous left-recursive right-recursive an operator-grammar

The grammar $A \rightarrow AA \mid (A) \mid \epsilon$ is not suitable for predictive-parsing because the grammar is:ambiguousleft-recursiveright-recursivean operator-gram...

23.5k views

answer edited Nov 28, 2020

5 answers

5

GATE IT 2004 | Question: 81
In a sliding window $ARQ$ scheme, the transmitter's window size is $N$ and the receiver's window size is $M$. The minimum number of distinct sequence numbers required to ensure correct operation of the $ARQ$ scheme is $\min (M, N)$ $\max (M, N)$ $M + N$ $MN$

In a sliding window $ARQ$ scheme, the transmitter's window size is $N$ and the receiver's window size is $M$. The minimum number of distinct sequence numbers required to ...

10.5k views

answered Nov 24, 2020

11 answers

6

GATE CSE 2015 Set 3 | Question: 36
Two hosts are connected via a packet switch with $10^7$ bits per second links. Each link has a propagation delay of $20$ microseconds. The switch begins forwarding a packet $35$ microseconds after it receives the same. If $10000$ bits of ... between the transmission of the first bit of data and the reception of the last bit of the data in microseconds is ______.

Two hosts are connected via a packet switch with $10^7$ bits per second links. Each link has a propagation delay of $20$ microseconds. The switch begins forwarding a pack...

33.0k views

commented Nov 23, 2020

3 answers

7

GATE CSE 2003 | Question: 19, ISRO2009-24
Suppose the numbers $7, 5, 1, 8, 3, 6, 0, 9, 4, 2$ ... $9 \ 8 \ 6 \ 4 \ 2 \ 3 \ 0 \ 1 \ 5 \ 7$

Suppose the numbers $7, 5, 1, 8, 3, 6, 0, 9, 4, 2$ are inserted in that order into an initially empty binary search tree. The binary search tree uses the usual ordering o...

23.5k views

answered Nov 19, 2020

9 answers

8

GATE CSE 2013 | Question: 44
Consider the following operation along with Enqueue and Dequeue operations on queues, where $k$ is a global parameter. MultiDequeue(Q){ m = k while (Q is not empty) and (m > 0) { Dequeue(Q) m = m – 1 } } What is the worst case time complexity of a sequence of $n$ queue operations on an initially empty queue? $Θ(n)$ $Θ(n + k)$ $Θ(nk)$ $Θ(n^2)$

Consider the following operation along with Enqueue and Dequeue operations on queues, where $k$ is a global parameter.MultiDequeue(Q){ m = k while (Q is not empty) and (m...

31.3k views

commented Nov 17, 2020

11 answers

9

GATE IT 2007 | Question: 30
Suppose you are given an implementation of a queue of integers. The operations that can be performed on the queue are: $isEmpty (Q)$ - returns true if the queue is empty, false otherwise. $delete (Q)$ - deletes the element at the front of the queue ... the front of the queue $Q$ and inserts it at the rear keeping the other elements in the same order Empties the queue $Q$

Suppose you are given an implementation of a queue of integers. The operations that can be performed on the queue are:$isEmpty (Q)$ — returns true if the queue is empty...

16.3k views

answered Nov 17, 2020

8 answers

10

GATE CSE 1998 | Question: 2.14
Let $A$ be a two dimensional array declared as follows: A: array [1 …. 10] [1 ….. 15] of integer; Assuming that each integer takes one memory location, the array is stored in row-major order and the first element of the array is stored at location $100$, what is the address of the element $A[i][j]$? $15i+j+84$ $15j+i+84$ $10i+j+89$ $10j+i+89$

Let $A$ be a two dimensional array declared as follows:A: array [1 …. 10] [1 ….. 15] of integer;Assuming that each integer takes one memory location, the array is sto...

29.8k views

answered Nov 16, 2020

4 answers

11

GATE CSE 2006 | Question: 57
Consider this C code to swap two integers and these five statements: the code void swap (int *px, int *py) { *px = *px - *py; *py = *px + *py; *px = *py - *px; } S1: will generate a compilation error S2: may generate a ... procedure correctly for some but not all valid input pointers S5: may add or subtract integers and pointers S1 S2 and S3 S2 and S4 S2 and S5

Consider this C code to swap two integers and these five statements: the codevoid swap (int *px, int *py) { *px = *px - *py; *py = *px + *py; *px = *py - *px; }S1...

21.0k views

answered Nov 14, 2020

6 answers

12

GATE IT 2004 | Question: 65
The semaphore variables full, empty and mutex are initialized to $0$, $n$ and $1$, respectively. Process P1 repeatedly adds one item at a time to a buffer of size $n$, and process P2 repeatedly removes one item at a time from the same buffer using the programs given below. In ... P(empty), V(full) P(empty), V(full), P(empty), V(full) P(empty), V(full), P(full), V(empty)

The semaphore variables full, empty and mutex are initialized to $0$, $n$ and $1$, respectively. Process P1 repeatedly adds one item at a time to a buffer of size $n$, an...

7.1k views

answered Nov 12, 2020

4 answers

13

GATE CSE 1999 | Question: 20-b
Consider the following solution to the producer-consumer problem using a buffer of size 1. Assume that the initial value of count is 0. Also assume that the testing of count and assignment to count are atomic operations. Producer: Repeat Produce an ... item; Forever; Show that in this solution it is possible that both the processes are sleeping at the same time.

Consider the following solution to the producer-consumer problem using a buffer of size 1. Assume that the initial value of count is 0. Also assume that the testing of co...

3.5k views

answer edited Nov 6, 2020

8 answers

14

GATE CSE 2012 | Question: 32
Fetch_And_Add(X,i) is an atomic Read-Modify-Write instruction that reads the value of memory location $X$, increments it by the value $i$, and returns the old value of $X$. It is used in the pseudocode shown below to implement ... take on a non-zero value when the lock is actually available works correctly but may starve some processes works correctly without starvation

Fetch_And_Add(X,i) is an atomic Read-Modify-Write instruction that reads the value of memory location $X$, increments it by the value $i$, and returns the old value of $X...

30.0k views

commented Nov 5, 2020

3 answers

15

GATE CSE 1991 | Question: 11,a
Consider the following scheme for implementing a critical section in a situation with three processes $P_i, P_j$ and $P_k$. Pi; repeat flag[i] := true; while flag [j] or flag[k] do case turn of j: if flag [j] then begin flag [i] ... j; flag [i] := false non-critical section until false; Does the scheme ensure mutual exclusion in the critical section? Briefly explain.

Consider the following scheme for implementing a critical section in a situation with three processes $P_i, P_j$ and $P_k$.Pi; repeat flag[i] := true; while flag [j] or f...

4.1k views

commented Nov 4, 2020

4 answers

16

GATE IT 2004 | Question: 14
Which one of the following is NOT shared by the threads of the same process ? Stack Address Space File Descriptor Table Message Queue

Which one of the following is NOT shared by the threads of the same process ?StackAddress SpaceFile Descriptor TableMessage Queue

13.9k views

answer edited Nov 2, 2020

5 answers

17

GATE CSE 1995 | Question: 2.6
The sequence __________ is an optimal non-preemptive scheduling sequence for the following jobs which leaves the CPU idle for ________ unit(s) of time. ... $\{2, 1, 3\}, 0$ $\{3, 2, 1\}, 0$ $\{1, 2, 3\}, 5$

The sequence __________ is an optimal non-preemptive scheduling sequence for the following jobs which leaves the CPU idle for ________ unit(s) of time.$$\small \begin{arr...

16.4k views

answer edited Nov 2, 2020

5 answers

18

GATE CSE 2002 | Question: 2.21
Which combination of the following features will suffice to characterize an OS as a multi-programmed OS? More than one program may be loaded into main memory at the same time for execution If a program waits for certain events such as I/O, another program is immediately scheduled ... is immediately scheduled for execution. (a) (a) and (b) (a) and (c) (a), (b) and (c)

Which combination of the following features will suffice to characterize an OS as a multi-programmed OS?More than one program may be loaded into main memory at the same t...

12.8k views

answered Nov 1, 2020

6 answers

19

GATE CSE 2005 | Question: 55
Consider the languages: $L_1 = \left\{ a^nb^nc^m \mid n,m >0\right\}$ and $ L_2 = \left\{a^nb^mc^m\mid n, m > 0\right\}$ Which one of the following statements is FALSE? $L_1 \cap L_2$ is a context-free language $L_1 \cup L_2$ is a context-free language $L_1 \text{ and } L_2$ are context-free languages $L_1 \cap L_2$ is a context sensitive language

Consider the languages:$L_1 = \left\{ a^nb^nc^m \mid n,m >0\right\}$ and $ L_2 = \left\{a^nb^mc^m\mid n, m 0\right\}$Which one of the following statements is FALSE?$L_1...

8.7k views

answered Oct 17, 2020

7 answers

20

GATE CSE 2015 Set 1 | Question: 33
Consider the following pseudo code, where $x$ and $y$ are positive integers. begin q := 0 r := x while r ≥ y do begin r := r - y q := q + 1 end end The post condition that needs to be satisfied after the program terminates is $\{ r = qx + y \wedge r < y\}$ ... $\{ y = qx + r \wedge 0 < r < y\}$ $\{ q + 1 < r - y \wedge y > 0\}$

Consider the following pseudo code, where $x$ and $y$ are positive integers.begin q := 0 r := x while r ≥ y do begin r := r - y q := q + 1 end endThe post condition tha...

15.6k views

answered Oct 13, 2020

3 answers

21

GATE CSE 2016 Set 2 | Question: 42
Consider the following two statements: If all states of an NFA are accepting states then the language accepted by the NFA is $\Sigma_{}^{*}$. There exists a regular language $A$ such that for all languages $B$, $A \cap B$ is regular. Which one of the following is CORRECT? Only I is true Only II is true Both I and II are true Both I and II are false

Consider the following two statements:If all states of an NFA are accepting states then the language accepted by the NFA is $\Sigma_{}^{*}$.There exists a regular languag...

25.6k views

answered Oct 13, 2020

3 answers

22

GATE CSE 2007 | Question: 7
Which of the following is TRUE? Every subset of a regular set is regular Every finite subset of a non-regular set is regular The union of two non-regular sets is not regular Infinite union of finite sets is regular

Which of the following is TRUE?Every subset of a regular set is regularEvery finite subset of a non-regular set is regularThe union of two non-regular sets is not regular...

15.4k views

answered Oct 12, 2020

7 answers

23

GATE CSE 2001 | Question: 2.14
Consider an undirected, unweighted graph $G$. Let a breadth-first traversal of $G$ be done starting from a node $r$. Let $d(r,u)$ and $d(r,v)$ be the lengths of the shortest paths from $r$ to $u$ and $v$ respectively in $G$. If $u$ is visited before $v$ during the breadth- ... correct? $d(r,u) < d(r,v)$ $d(r,u) > d(r,v)$ $d(r,u) \leq d(r,v)$ None of the above

Consider an undirected, unweighted graph $G$. Let a breadth-first traversal of $G$ be done starting from a node $r$. Let $d(r,u)$ and $d(r,v)$ be the lengths of the short...

14.1k views

answered Oct 4, 2020

9 answers

24

GATE CSE 2003 | Question: 62
In a permutation $a_1\ldots a_n$, of $n$ distinct integers, an inversion is a pair $(a_i, a_j)$ such that $i < j$ and $a_i > a_j.$ What would be the worst case time complexity of the Insertion Sort algorithm, if the inputs are restricted to permutations of $1. . . n$ with at most $n$ inversions? $\Theta(n^2)$ $\Theta(n\log n)$ $\Theta(n^{1.5})$ $\Theta(n)$

In a permutation $a_1\ldots a_n$, of $n$ distinct integers, an inversion is a pair $(a_i, a_j)$ such that $i < j$ and $a_i a_j.$What would be the worst case time complex...

19.8k views

answered Sep 24, 2020

5 answers

25

GATE CSE 2008 | Question: 84
Consider the following C program that attempts to locate an element $x$ in an array $Y[ \ ]$ using binary search. The program is erroneous. f (int Y[10] , int x) { int i, j, k; i= 0; j = 9; do { k = (i+ j) / 2; if( Y[k] < x) i = k;else j = k; } while (Y[k] != x ... $Y$ is $[2 \ 4 \ 6 \ 8 \ 10 \ 12 \ 14 \ 16 \ 18 \ 20]$ and $ 2 < x < 20$ and $x$ is even

Consider the following C program that attempts to locate an element $x$ in an array $Y[ \ ]$ using binary search. The program is erroneous. f (int Y[10] , int x) { int i,...

21.4k views

answered Sep 20, 2020

4 answers

26

GATE CSE 2020 | Question: 2
For parameters $a$ and $b$, both of which are $\omega(1)$, $T(n) = T(n^{1/a})+1$, and $T(b)=1$. Then $T(n)$ is $\Theta (\log_a \log _b n)$ $\Theta (\log_{ab} n$) $\Theta (\log_{b} \log_{a} \: n$) $\Theta (\log_{2} \log_{2} n$)

For parameters $a$ and $b$, both of which are $\omega(1)$, $T(n) = T(n^{1/a})+1$, and $T(b)=1$. Then $T(n)$ is$\Theta (\log_a \log _b n)$ $\Theta (\log_{ab} n$)$\Thet...

19.5k views

answered Sep 19, 2020

2 answers

27

GATE CSE 2016 Set 2 | Question: 39
The given diagram shows the flowchart for a recursive function $A(n)$. Assume that all statements, except for the recursive calls, have $O(1)$ time complexity. If the worst case time complexity of this function is $O(n^{\alpha})$, then the least possible value (accurate up to two decimal positions) of $\alpha$ is ________. Flow chart for Recursive Function $A(n)$.

The given diagram shows the flowchart for a recursive function $A(n)$. Assume that all statements, except for the recursive calls, have $O(1)$ time complexity. If the wor...

16.4k views

commented Sep 19, 2020

4 answers

28

GATE CSE 2012 | Question: 18
Let $W(n) $ and $A(n)$ denote respectively, the worst case and average case running time of an algorithm executed on an input of size $n$. Which of the following is ALWAYS TRUE? $A(n) = \Omega (W(n))$ $A(n) = \Theta (W(n))$ $A(n) = \text{O} (W(n))$ $A(n) = \text{o} (W(n))$

Let $W(n) $ and $A(n)$ denote respectively, the worst case and average case running time of an algorithm executed on an input of size $n$. Which of the following is ALWA...

14.4k views

answered Sep 10, 2020

5 answers

29

GATE CSE 2014 Set 3 | Question: 2
Let $X$ and $Y$ be finite sets and $f:X \to Y$ be a function. Which one of the following statements is TRUE? For any subsets $A$ and $B$ of $X, |f(A \cup B)| = |f(A)| + |f(B)|$ For any subsets $A$ and $B$ of $X, f(A \cap B) = f(A) \cap f(B)$ For any subsets $A$ ... $S$ and $T$ of $Y, f^{-1}(S \cap T) = f^{-1}(S) \cap f^{-1}(T)$

Let $X$ and $Y$ be finite sets and $f:X \to Y$ be a function. Which one of the following statements is TRUE?For any subsets $A$ and $B$ of $X, |f(A \cup B)| = |f(A)| + |f...

14.1k views

commented Sep 8, 2020

8 answers

30

GATE CSE 2014 Set 2 | Question: 50
Consider the following relation on subsets of the set $S$ of integers between $1$ and $2014$. For two distinct subsets $U$ and $V$ of $S$ we say $U\:<\:V$ if the minimum element in the symmetric difference of the two sets is in $U$. Consider the ... $S1$ is true and $S2$ is false $S2$ is true and $S1$ is false Neither $S1$ nor $S2$ is true

Consider the following relation on subsets of the set $S$ of integers between $1$ and $2014$. For two distinct subsets $U$ and $V$ of $S$ we say $U\:<\:V$ if the minimum ...

15.9k views

commented Sep 8, 2020

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