Recent activity by Alakhator / GATE Overflow for GATE CSE

3 answers

1

GATE IT 2007 | Question: 49
Consider the following grammars. Names representing terminals have been specified in capital letters. ... $G_1$ and $G_2$ are regular Both $G_1$ and $G_2$ are context-free but neither of them is regular

Consider the following grammars. Names representing terminals have been specified in capital letters.$$\begin{array}{llll}\hline \text{$G1$ :} & \text{stmnt} & \text{$\...

12.8k views

commented Jan 15, 2020

17 answers

2

GATE CSE 2004 | Question: 62
A 4-bit carry look ahead adder, which adds two 4-bit numbers, is designed using AND, OR, NOT, NAND, NOR gates only. Assuming that all the inputs are available in both complemented and uncomplemented forms and the delay of each gate is one time ... the carry network has been implemented using two-level AND-OR logic. 4 time units 6 time units 10 time units 12 time units

A 4-bit carry look ahead adder, which adds two 4-bit numbers, is designed using AND, OR, NOT, NAND, NOR gates only. Assuming that all the inputs are available in both com...

32.6k views

commented Jan 3, 2020

2 answers

3

GATE CSE 1994 | Question: 7
An array $A$ contains $n$ integers in locations $A[0], A[1], \dots A[n-1]$. It is required to shift the elements of the array cyclically to the left by $K$ places, where $1\leq K \leq n-1$. An incomplete algorithm for doing this in linear time, without using another array ... j]:=____; j:=(j+K) mod n; if j<min then min:=j; end; A[(n+i-K)mod n]:=____; i:=______; end;

An array $A$ contains $n$ integers in locations $A[0], A , \dots A[n-1]$. It is required to shift the elements of the array cyclically to the left by $K$ places, where $1...

4.0k views

comment edited Nov 29, 2019

5 answers

4

GATE IT 2008 | Question: 76
A binary tree with $n > 1$ nodes has $n_1$, $n_2$ and $n_3$ nodes of degree one, two and three respectively. The degree of a node is defined as the number of its neighbours. $n_3$ can be expressed as $n_1 + n_2 - 1$ $n_1 -2$ $[((n_1 + n_2)/2)]$ $n_2 - 1$

A binary tree with $n 1$ nodes has $n_1$, $n_2$ and $n_3$ nodes of degree one, two and three respectively. The degree of a node is defined as the number of its neighbo...

16.9k views

commented Nov 24, 2019

8 answers

5

GATE CSE 2014 Set 3 | Question: 39
Suppose we have a balanced binary search tree $T$ holding $n$ numbers. We are given two numbers $L$ and $H$ and wish to sum up all the numbers in $T$ that lie between $L$ and $H$. Suppose there are $m$ such numbers in $T$. If the tightest upper bound on the time to compute the sum is $O(n^a\log^bn+m^c\log^dn)$, the value of $a+10b+100c+1000d$ is ______.

Suppose we have a balanced binary search tree $T$ holding $n$ numbers. We are given two numbers $L$ and $H$ and wish to sum up all the numbers in $T$ that lie between $L$...

31.5k views

commented Nov 23, 2019

1 answer

6

GATE CSE 1999 | Question: 15
What will be the output of the following program assuming that parameter passing is call by value call by reference call by copy restore procedure P{x, y, z}; begin y:y+1; z: x+x; end; begin a:= b:= 3; P(a+b, a, a); Print(a); end

What will be the output of the following program assuming that parameter passing iscall by valuecall by referencecall by copy restoreprocedure P{x, y, z}; begin y:y+1; z:...

5.9k views

commented Nov 17, 2019

7 answers

7

GATE CSE 2010 | Question: 54
Consider a network with $6$ routers $\textbf{R1}$ to $\textbf{R6}$ connected with links having weights as shown in the following diagram. All the routers use the distance vector based routing algorithm to update their routing tables. Each router starts with its ... stabilize, how many links in the network will never be used for carrying any data? $4$ $3$ $2$ $1$

Consider a network with $6$ routers $\textbf{R1}$ to $\textbf{R6}$ connected with links having weights as shown in the following diagram.All the routers use the distance ...

23.7k views

commented Nov 10, 2019

10 answers

8

GATE CSE 2007 | Question: 69
The distance between two stations $M$ and $N$ is $L$ kilometers. All frames are $K$ bits long. The propagation delay per kilometer is $t$ seconds. Let $R$ bits/second be the channel capacity. Assuming that the processing delay is negligible, the $\text{minimum}$ number ... $\lceil \log_2 \frac{2LtR +K}{K} \rceil$ $\lceil \log_2 \frac{2LtR +2K}{2K} \rceil$

The distance between two stations $M$ and $N$ is $L$ kilometers. All frames are $K$ bits long. The propagation delay per kilometer is $t$ seconds. Let $R$ bits/second be ...

18.2k views

commented Nov 2, 2019

2 answers

9

GATE CSE 1998 | Question: 1.20
Which of the following is true? Unless enabled, a CPU will not be able to process interrupts. Loop instructions cannot be interrupted till they complete. A processor checks for interrupts before executing a new instruction. Only level triggered interrupts are possible on microprocessors.

Which of the following is true?Unless enabled, a CPU will not be able to process interrupts.Loop instructions cannot be interrupted till they complete.A processor checks ...

11.8k views

commented Oct 22, 2019

4 answers

10

GATE CSE 2004 | Question: 63
Consider the following program segment for a hypothetical CPU having three user registers $R_1, R_2$ and $R_3.$ ... after executing the HALT instruction, the return address (in decimal) saved in the stack will be $1007$ $1020$ $1024$ $1028$

Consider the following program segment for a hypothetical CPU having three user registers $R_1, R_2$ and $R_3.$ $$\begin{array}{|l|l|c|} \hline \text {Instruction} & \t...

29.1k views

commented Oct 19, 2019

12 answers

11

GATE CSE 2015 Set 2 | Question: 48
A half adder is implemented with XOR and AND gates. A full adder is implemented with two half adders and one OR gate. The propagation delay of an XOR gate is twice that of an AND/OR gate. The propagation delay of an AND/OR gate is ... adder is implemented by using four full adders. The total propagation time of this $4$-bit binary adder in microseconds is ______.

A half adder is implemented with XOR and AND gates. A full adder is implemented with two half adders and one OR gate. The propagation delay of an XOR gate is twice that o...

62.0k views

commented Oct 3, 2019

14 answers

12

GATE CSE 2012 | Question: 12
What is the complement of the language accepted by the NFA shown below? Assume $\Sigma = \{a\}$ and $\epsilon$ is the empty string. $\phi$ $\{\epsilon\}$ $a^*$ $\{a , \epsilon\}$

What is the complement of the language accepted by the NFA shown below?Assume $\Sigma = \{a\}$ and $\epsilon$ is the empty string.$\phi$$\{\epsilon\}$$a^*$$\{a , \epsilon...

19.3k views

commented Jul 7, 2019

4 answers

13

MadeEasy Test Series: Operating System - Resource Allocation

1.3k views

answered Jul 5, 2019

9 answers

14

GATE CSE 2010 | Question: 41
Let $w$ be any string of length $n$ in $\{0,1\}^*$. Let $L$ be the set of all substrings of $w$. What is the minimum number of states in non-deterministic finite automation that accepts $L$? $n-1$ $n$ $n+1$ $2^{n-1}$

Let $w$ be any string of length $n$ in $\{0,1\}^*$. Let $L$ be the set of all substrings of $w$. What is the minimum number of states in non-deterministic finite automati...

24.0k views

commented Jul 4, 2019

3 answers

15

GATE CSE 1998 | Question: 1.23
How many sub strings of different lengths (non-zero) can be formed from a character string of length $n$? $n$ $n^2$ $2^n$ $\frac{n(n+1)}{2}$

How many sub strings of different lengths (non-zero) can be formed from a character string of length $n$?$n$$n^2$$2^n$$\frac{n(n+1)}{2}$

14.5k views

commented Jun 26, 2019

1 answer

16

Insertion sort on small arrays in merge sort
Although merge sort runs in Θ(n lg n) worst-case time, and insertion sort runs in Θ(n 2 ) worst-case time, the constant factors in insertion sort make it faster for small n. Thus, it makes sense to ... for which the modified algorithm has the same asymptotic running time as standard merge sort? d.How should we choose k in practice?

Although merge sort runs in Θ(n lg n) worst-case time, and insertion sort runs in Θ(n 2 ) worst-case time, the constant factors in insertion sort make it fast...

2.0k views

commented Jun 23, 2019

1 answer

17

Clock frequency required for proper operation of ripple counter
An 8 stage ripple counter uses a flip flop with propagation delay of 75 ns. The pulse width of strobe is 50ns. The frequency of input signal which can be used for proper operation of counter is? (A) 1 MHz (B) 500 MHz (C) 1.5 MHz (D) 2 MHz

An 8 stage ripple counter uses a flip flop with propagation delay of 75 ns. The pulse width of strobe is 50ns. The frequency of input signal which can be used for proper ...

7.9k views

commented Jun 23, 2019

7 answers

18

GATE CSE 2000 | Question: 1.21
Let $m[0]\ldots m[4]$ be mutexes (binary semaphores) and $P[0]\ldots P[4]$ be processes. Suppose each process $P[i]$ executes the following: wait (m[i]); wait (m(i+1) mod 4]); ........... release (m[i]); release (m(i+1) mod 4]); This could cause Thrashing Deadlock Starvation, but not deadlock None of the above

Let $m[0]\ldots m[4]$ be mutexes (binary semaphores) and $P[0]\ldots P[4]$ be processes. Suppose each process $P[i]$ executes the following:wait (m[i]); wait (m(i+1) mod ...

22.1k views

commented Jun 22, 2019

14 answers

19

GATE CSE 1997 | Question: 6.8
Each Process $P_i, i = 1\ldots 9$ is coded as follows repeat P(mutex) {Critical section} V(mutex) forever The code for $P_{10}$ is identical except it uses V(mutex) in place of P(mutex). What is the largest number of processes that can be inside the critical section at any moment? $1$ $2$ $3$ None

Each Process $P_i, i = 1\ldots 9$ is coded as followsrepeat P(mutex) {Critical section} V(mutex) foreverThe code for $P_{10}$ is identical except it uses V(mutex) in plac...

25.1k views

commented Jun 21, 2019

3 answers

20

GATE CSE 2009 | Question: 32
In the following process state transition diagram for a uniprocessor system, assume that there are always some processes in the ready state: Now consider the following statements: If a process makes a transition $D$, it would result in another process making ... -preemptive scheduling. Which of the above statements are TRUE? I and II I and III II and III II and IV

In the following process state transition diagram for a uniprocessor system, assume that there are always some processes in the ready state:Now consider the following sta...

18.9k views

commented Jun 18, 2019

1 answer

21

Expression of Q is to be calculated

263 views

asked May 18, 2019

12 answers

22

GATE CSE 2017 Set 1 | Question: 04
Consider the following functions from positive integers to real numbers: $10$, $\sqrt{n}$, $n$, $\log_{2}n$, $\frac{100}{n}$. The CORRECT arrangement of the above functions in increasing order of asymptotic complexity is: $\log_{2}n$, $\frac{100}{n}$, $10$, $\sqrt{n}$, $n$ ... $\sqrt{n}$, $\log_{2}n$, $n$ $\frac{100}{n}$, $\log_{2}n$, $10$, $\sqrt{n}$, $n$

Consider the following functions from positive integers to real numbers:$10$, $\sqrt{n}$, $n$, $\log_{2}n$, $\frac{100}{n}$.The CORRECT arrangement of the above functions...

17.8k views

commented May 18, 2019

1 answer

23

Moore machine example
plzz expain this machine how it is working machine is Addition of two binary numbers

plzz expain this machine how it is working machine is Addition of two binary numbers

3.3k views

answered May 18, 2019

1 answer

24

Conversion of E-NFA to DFA

833 views

commented May 15, 2019

1 answer

25

GATE 2015 SET-2 Q 29
Let the random variable X represent the number of times a fair coin needs to be tossed till two consecutive heads appear for the first time. The expectation of X is _______.

Let the random variable X represent the number of times a fair coin needs to be tossed till two consecutive heads appear for the first time. The expectation of X is _____...

3.9k views

commented May 14, 2019

1 answer

26

Fog and gof function

1.1k views

answered Jan 8, 2019

0 answers

27

Context Free language
Is this language context-free language? L= { a^n b^n c^m / n>m}

Is this language context-free language?L= { a^n b^n c^m / n>m}

323 views

commented Nov 11, 2018

2 answers

28

Push Down Automata
Construct a PDA for set of strings over {a,b,c,d} such that L={ a^i b^j c^k d^l / i=k or j=l , i,j,k,l >=1}

Construct a PDA for set of strings over {a,b,c,d} such thatL={ a^i b^j c^k d^l / i=k or j=l , i,j,k,l >=1}

894 views

asked Nov 11, 2018

2 answers

29

Set associative mapping
What is the number of multiplexers required in set associative mapping hardware ? Given set bits are S, tag bits are T and word bits are W.

What is the number of multiplexers required in set associative mapping hardware ? Given set bits are S, tag bits are T and word bits are W.

684 views

asked Oct 19, 2018

0 answers

30

Dijkstra Algorithm
Dijkstra always give wrong answer with negative edge cycle. ( True / False )

Dijkstra always give wrong answer with negative edge cycle. ( True / False )

269 views

asked Oct 13, 2018

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