Dark Mode

Recent activity by GateAspirant999

6 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

commented in Databases Nov 11, 2018

15.4k views

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

comment edited in Databases Nov 11, 2018

15.2k views

1 answer

3

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

commented in Algorithms Sep 22, 2018

15.3k views

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}})$

commented in Algorithms Sep 21, 2018

11.3k views

1 answer

5

Time complexity of code given

commented in Algorithms Sep 18, 2018

599 views

0 answers

6

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

closed in Mathematical Logic Sep 15, 2018

180 views

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

commented in Digital Logic Aug 27, 2018

7.3k views

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)

edited in Digital Logic Aug 19, 2018

3.7k views

2 answers

9

How many minterms are present in 8 input EXOR gate ?

commented in Digital Logic Aug 18, 2018

3.0k views

3 answers

10

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?

commented in Theory of Computation Jul 7, 2018

9.0k views

1 answer

11

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?

commented in Theory of Computation Jul 1, 2018

861 views

1 answer

12

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)$ ?

commented in Set Theory & Algebra May 31, 2018

259 views

0 answers

13

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?

asked in Databases May 21, 2018

2.8k views

0 answers

14

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$?

asked in Databases May 12, 2018

508 views

2 answers

15

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

commented in Compiler Design Apr 7, 2018

2.2k views

0 answers

16

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?

asked in Programming Mar 24, 2018

206 views

1 answer

17

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 ... no -ve edge weight cycle reachable from source node. Am I correct with this? or am I missing something here?

commented in Algorithms Mar 18, 2018

2.9k views

1 answer

18

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 ?

commented in Algorithm Challenges Mar 15, 2018

1.6k views

1 answer

19

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

answer selected in Theory of Computation Mar 3, 2018

714 views

1 answer

20

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

commented in Theory of Computation Mar 3, 2018

382 views

1 answer

21

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, E ... A 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

asked in Theory of Computation Mar 2, 2018

357 views

5 answers

22

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 ____.

commented in Set Theory & Algebra Feb 14, 2018

12.4k views

7 answers

23

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)

commented in Set Theory & Algebra Feb 13, 2018

9.0k views

4 answers

24

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$.

comment edited in Set Theory & Algebra Feb 9, 2018

9.4k views

4 answers

25

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)$

comment edited in Set Theory & Algebra Feb 8, 2018

11.0k views

3 answers

26

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

commented in Set Theory & Algebra Feb 7, 2018

6.7k views

3 answers

27

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.

commented in Operating System Feb 2, 2018

17.5k views

1 answer

28

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?

commented in Digital Logic Jan 29, 2018

2.3k views

3 answers

29

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

answered in Digital Logic Jan 29, 2018

874 views

5 answers

30

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 __________

commented in Digital Logic Jan 28, 2018

9.4k views