Recent activity by GateAspirant999 / GATE Overflow for GATE CSE

7 answers

1

GATE CSE 2006 | Question: 68
Consider the relation enrolled (student, course) in which (student, course) is the primary key, and the relation paid (student, amount) where student is the primary key. Assume no null values and no foreign keys or integrity constraints. ... strictly fewer rows than Query$2$ There exist databases for which Query$4$ will encounter an integrity violation at runtime

Consider the relation enrolled (student, course) in which (student, course) is the primary key, and the relation paid (student, amount) where student is the primary key. ...

20.4k views

commented Nov 11, 2018

6 answers

2

GATE CSE 2014 Set 2 | Question: 54
SQL allows duplicate tuples in relations, and correspondingly defines the multiplicity of tuples in the result of joins. Which one of the following queries always gives the same answer as the nested query shown below: select * from R where a in (select S.a from S) select R. ... a from S) as S1 where R.a=S1.a select R.* from R,S where R.a=S.a and is unique R

SQL allows duplicate tuples in relations, and correspondingly defines the multiplicity of tuples in the result of joins. Which one of the following queries always gives t...

19.5k views

comment edited Nov 11, 2018

1 answer

3

T(n)=2T(floor(sqrt(n))+log n
the solution of recurrence relation T(n)=2T(floor(sqrt(n))+log n

the solution of recurrence relationT(n)=2T(floor(sqrt(n))+log n

18.7k views

commented Sep 22, 2018

2 answers

4

T(n) = T(n-1) + T(n/2) + n
Consider the recurrence relation T(n) = T(n-1) + T(n/2) + n Which of the following is a good tight upper bound on T(n) (a) $\Theta (n^{2})$ (b) $\Theta (n^{2}\log n)$ (c) $\Theta (2^{(\log n)^{2}})$ (d) $\Theta (n^{(\log n)^{2}})$

Consider the recurrence relation T(n) = T(n-1) + T(n/2) + nWhich of the following is a good tight upper bound on T(n)(a) $\Theta (n^{2})$(b) $\Theta (n^{2}\log n)$(c) $\T...

13.9k views

commented Sep 20, 2018

1 answer

5

Time complexity of code given

967 views

commented Sep 17, 2018

0 answers

6

Time complexity of given code using "finite" geometric series
Solved!!!

Solved!!!

261 views

closed Sep 15, 2018

1 answer

7

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 Aug 27, 2018

1 answer

8

Adder delay
A full adder circuit takes 20 ns to generate the carry-out bit and 40 ns for the sum bit. When 4, 1 bit full adders are cascaded, the maximum rate of additions per second will be $\text{____} \times 10^6 $sec. Usual Solution given The ... calculate the total time taken to perform one round of four bit addition. Right? (Similar old question: https://gateoverflow.in/83500/digitals)

A full adder circuit takes 20 ns to generate the carry-out bit and 40 ns for the sum bit. When 4, 1 bit full adders are cascaded, the maximum rate of additions per second...

4.4k views

edited Aug 19, 2018

3 answers

9

Language of strings not containing 101
Can someone show how we can systematically come up with regular expression for language not containing string 101 on alphabet {0,1} by first creating DFA and then converting it to regular expression?

Can someone show how we can systematically come up with regular expression for language not containing string 101 on alphabet {0,1} by first creating DFA and then convert...

14.3k views

commented Jul 6, 2018

1 answer

10

Simplifying regular expressions
What is regex for the DFA: I am coming up with following two: 1. b*a(a+b)* and 2. b*a(b+ab*a)*+b*ab*a(ab*a+b)* Both seems to be correct to me. For X1, we have regex b*a(b+ab*a) For X2, we have regex b*ab*a(ab*a ... question: I want to know if I can simplify regex 2 to regex 1 by regex identities, but not by any other approach say by dfa minimization. Is it possible?

What is regex for the DFA:I am coming up with following two:1. b*a(a+b)* and2. b*a(b+ab*a)*+b*ab*a(ab*a+b)*Both seems to be correct to me. For X1, we have regex b*a(b+ab*...

1.2k views

commented Jul 1, 2018

1 answer

11

Understanding points about countable sets from wikipedia
I am struggling to understand following points made on wikipedia page of counting sets: Let S be a set. The following statements are equivalent: S is countable, i.e. there exists an injective function f : S → N. Either S is empty or ... $(2)\implies (3)$ ?

I am struggling to understand following points made on wikipedia page of counting sets:Let S be a set. The following statements are equivalent:S is countable, i.e. there ...

403 views

commented May 31, 2018

0 answers

12

Understanding multiversion timestamp ordering protocol in database systems
I was reading multiversion timestamp ordering protocol from the book Database Systems Concepts by Korth. It can be explained in simpler words as follows: Each data item version $Q$ has two timestamps associated with it: W-timestamp: ... I am wrong and it was indeed asked in previous year GATE paper?) Can we safely skip it?

I was reading multiversion timestamp ordering protocol from the book Database Systems Concepts by Korth. It can be explained in simpler words as follows:Each data item ve...

3.1k views

asked May 20, 2018

0 answers

13

Understanding theta join operation
Q.1. Does theta join operator requires following union compatibility requirements?: Same number of columns Domain of corresponding columns should be same I feel no, since I came across following fact: $\sigma_\theta( R_1\times R_2)=R_1⋈_\theta R_2$ ... as shown above, does it mean columns of resultant relation will contain ALL columns from both $R_1$ and $R_2$?

Q.1. Does theta join operator requires following union compatibility requirements?:Same number of columnsDomain of corresponding columns should be sameI feel no, since I ...

640 views

asked May 12, 2018

2 answers

14

CMI2012-A-09
Consider the following programming errors: Type mismatch in an expression. Array index out of bounds. Use of an uninitialized variable in an expression. Which of these errors will typically be caught at compile-time by a modern compiler. I, II and III I and II I and III None of them

Consider the following programming errors:Type mismatch in an expression.Array index out of bounds.Use of an uninitialized variable in an expression.Which of these errors...

2.9k views

commented Apr 7, 2018

0 answers

15

Equality of shortest path tree for given node as a root and
I have a small doubt. Chapter 25 All pairs shortest path of CLRS says following: To solve the all-pairs shortest-paths problem on an input adjacency matrix, we need to compute not only the shortest-path weights but also a predecessor ... isnt both things (shortest-paths tree with root $i$ and predecessor subgraph of $G$ for $i$) the same?

I have a small doubt.Chapter 25 All pairs shortest path of CLRS says following:To solve the all-pairs shortest-paths problem on an input adjacency matrix, we need to comp...

348 views

asked Mar 24, 2018

1 answer

16

Negative edge weights in Dijkstra
All text books and online resources say Dijkstra's algorithm need all non negative edge weights However I feel a bit different, especially after coming across problem asking to build shortest path tree from node aa in following graph: My shortest path ... -ve edge weight cycle reachable from source node. Am I correct with this? or am I missing something here?

All text books and online resources say Dijkstra's algorithm need all non negative edge weightsHowever I feel a bit different, especially after coming across problem aski...

3.5k views

commented Mar 18, 2018

1 answer

17

what is the best time complexity to find maximum product of exactly k elements in an array ?
According to me first we sort the array in O(nlogn) time and then in O(k) time , find the product , so total time complexity is O(nlogn) , so am I right or can it be done in lesser time ?

According to me first we sort the array in O(nlogn) time and then in O(k) time , find the product , so total time complexity is O(nlogn) , so am I right or can it be done...

2.2k views

commented Mar 15, 2018

1 answer

18

Language accepted by given NFA
Language accepted by following NFA and number of states in DFA accepting that Language are: $\{a^n|n=2k,kϵN\}$ and 2 $\{a^{2n}|n=2k,kϵN\}$ and 2 $\{a^n|n=2k,kϵ N\}$ and 3 $\{a^{2n}|n=2k,kϵ N\}$ and 3

Language accepted by following NFA and number of states in DFA accepting that Language are:$\{a^n|n=2k,kϵN\}$ and 2$\{a^{2n}|n=2k,kϵN\}$ and 2$\{a^n|n=2k,kϵ N\}$ and 3...

1.1k views

answer selected Mar 3, 2018

1 answer

19

Finding whether given languages are regular or context free
Given $L_1=\{a^nb^nc^n | n\geq 0\}$ $L_2 =\{a^nb^mc^k|k=n+m \text{ and }n,m\geq 0 \}$ $L_3 =\{a^nb^mc^k|n,m,k \geq 0 \}$ Assume $L_4=L_1 (L_3)^*$ $L_5=(L_1\cap L_2)\cup L_3 $ Which of the following ... is regular and L5 is not regular B. L4 is CFL and L5 is not CFL C. Both L4, L5 are regular D. Both L4, L5 are CFL but not regular

Given$L_1=\{a^nb^nc^n | n\geq 0\}$$L_2 =\{a^nb^mc^k|k=n+m \text{ and }n,m\geq 0 \}$$L_3 =\{a^nb^mc^k|n,m,k \geq 0 \}$Assume $L_4=L_1 (L_3)^*$$L_5=(L_1\cap L_2)\cup L_3...

537 views

commented Mar 3, 2018

1 answer

20

Language of left, right, top and down steps
Consider the infinite two-dimensional grid $G=\{(m,n)|\text{m and n are integers} \}$ Thus every point in G has 4 neighbours, North, South, East and West, obtained by varying m or n by $\pm 1$. Starting at origin (0,0), a string of command letters N, S ... and B are CFLs $L'$ is context free A. 1,2 and 3 only B. 3 and 4 only C. 4 only D. 1 and 2 only

Consider the infinite two-dimensional grid $G=\{(m,n)|\text{m and n are integers} \}$Thus every point in G has 4 neighbours, North, South, East and West, obtained by vary...

531 views

asked Mar 2, 2018

6 answers

21

GATE CSE 2014 Set 3 | Question: 50
There are two elements $x,\:y$ in a group $(G,*)$ such that every element in the group can be written as a product of some number of $x$'s and $y$'s in some order. It is known that $x*x=y*y=x*y*x*y=y*x*y*x=e$ where $e$ is the identity element. The maximum number of elements in such a group is ____.

There are two elements $x,\:y$ in a group $(G,*)$ such that every element in the group can be written as a product of some number of $x$'s and $y$'s in some order. It is ...

15.6k views

commented Feb 14, 2018

7 answers

22

GATE IT 2007 | Question: 23
A partial order $P$ is defined on the set of natural numbers as follows. Here $\frac{x}{y}$ denotes integer division. $(0, 0) \in P.$ $(a, b) \in P$ if and only if $(a \% 10) \leq (b \% 10$) and $(\frac{a}{10},\frac{b}{10})\in P.$ ... $P$? (i) and (iii) (ii) and (iv) (i) and (iv) (iii) and (iv)

A partial order $P$ is defined on the set of natural numbers as follows. Here $\frac{x}{y}$ denotes integer division.$(0, 0) \in P.$$(a, b) \in P$ if and only if $(a \% 1...

11.4k views

commented Feb 13, 2018

4 answers

23

GATE CSE 1998 | Question: 11
Suppose $A = \{a, b, c, d\}$ and $\Pi_1$ is the following partition of A $\Pi_1 = \left\{\left\{a, b, c\right\}\left\{d\right\}\right\}$ List the ordered pairs of the equivalence relations induced by $\Pi_1$. Draw the graph of the above ... $\left\langle\left\{\Pi_1, \Pi_2, \Pi_3, \Pi_4\right\}, \text{ refines } \right\rangle$.

Suppose $A = \{a, b, c, d\}$ and $\Pi_1$ is the following partition of A$\Pi_1 = \left\{\left\{a, b, c\right\}\left\{d\right\}\right\}$List the ordered pairs of the equiv...

11.6k views

comment edited Feb 9, 2018

5 answers

24

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

comment edited Feb 8, 2018

4 answers

25

GATE IT 2006 | Question: 2
For the set $N$ of natural numbers and a binary operation $f : N \times N \to N,$ an element $z \in N$ is called an identity for $f,$ if $f (a, z) = a = f(z, a),$ for all $a \in N.$ Which of the following binary operations have an identity? $f (x, y) = x + y - 3$ $f (x, y) = \max(x, y)$ $f (x, y) = x^y$ I and II only II and III only I and III only None of these

For the set $N$ of natural numbers and a binary operation $f : N \times N \to N,$ an element $z \in N$ is called an identity for $f,$ if $f (a, z) = a = f(z, a),$ for all...

9.6k views

commented Feb 7, 2018

3 answers

26

GATE CSE 2014 Set 1 | Question: 20
Which one of the following is FALSE? User level threads are not scheduled by the kernel. When a user level thread is blocked, all other threads of its process are blocked. Context switching between user level threads is faster than context switching between kernel level threads. Kernel level threads cannot share the code segment.

Which one of the following is FALSE?User level threads are not scheduled by the kernel.When a user level thread is blocked, all other threads of its process are blocked.C...

24.8k views

commented Feb 2, 2018

1 answer

27

Maximum clock frequency for the circuit
In the following digital circuit shown above, the worst case delay is of 30 nsec and the AND gate has delay of 10 nsec. The maximum clock frequency of the circuit to operate is _ MHz. I calculated as follows : ... the flip-flop delay once? The solution gives the frequency as 14.2 MHz, adding the delay due to flip-flop twice. Why?

In the following digital circuit shown above, the worst case delay is of 30 nsec and the AND gate has delay of 10 nsec. The maximum clock frequency of the circuit to oper...

3.0k views

commented Jan 29, 2018

3 answers

28

MADEEASY
The 3-bit ripple counter (shown below) is to be designed as a MOD 4 counter What is the best architecture of the ‘Logic gate’? A. a 3-bit input AND gate B. a 2-input AND gate C. a NOT gate D. a wire connection (no logic gate needed) Ans is given D but i think ans should be C Please Explain

The 3-bit ripple counter (shown below) is to be designed as a MOD 4 counterWhat is the best architecture of the ‘Logic gate’?A. a 3-bit input AND gateB. a 2-input AND...

1.1k views

answered Jan 29, 2018

5 answers

29

Total propagation delay in Carry look ahead adderIn a 4-b
In a 4-bit carry look ahead adder, the propagation delay of Ex-OR gate is 20ns ,AND and OR gates is 10 ns.The sum and carry output of full adder takes 20ns and 10ns respectively.The total propagation delay of the above adder in ns is __________

In a 4-bit carry look ahead adder, the propagation delay of Ex-OR gate is 20ns ,AND and OR gates is 10 ns.The sum and carry output of full adder takes 20ns and 10ns respe...

12.0k views

commented Jan 28, 2018

4 answers

30

GATE CSE 2005 | Question: 20
Normally user programs are prevented from handling I/O directly by I/O instructions in them. For CPUs having explicit I/O instructions, such I/O protection is ensured by having the I/O instruction privileged. In a CPU with memory mapped I/ ... /O protection is ensured by a hardware trap I/O protection is ensured during system configuration I/O protection is not possible

Normally user programs are prevented from handling I/O directly by I/O instructions in them. For CPUs having explicit I/O instructions, such I/O protection is ensured by ...

11.5k views

commented Jan 22, 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