Login
Register
Dark Mode
Brightness
Profile
Edit Profile
Messages
My favorites
My Updates
Logout
Filter
Profile
Wall
Recent activity
All questions
All answers
Exams Taken
All Blogs
Questions by GateAspirant999
0
votes
1
answer
1
Time complexity of code given
1.0k
views
asked
Sep 16, 2018
Algorithms
algorithms
sorting
time-complexity
numerical-answers
test-series
+
–
0
votes
0
answers
2
Time complexity of given code using "finite" geometric series
Solved!!!
Solved!!!
264
views
asked
Sep 15, 2018
Mathematical Logic
time-complexity
algorithms
+
–
1
votes
1
answer
3
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.5k
views
asked
Aug 19, 2018
Digital Logic
digital-logic
adder
combinational-circuit
digital-circuits
+
–
0
votes
3
answers
4
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.5k
views
asked
Jul 6, 2018
Theory of Computation
theory-of-computation
regular-expression
+
–
0
votes
1
answer
5
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.3k
views
asked
Jul 1, 2018
Theory of Computation
theory-of-computation
regular-expression
finite-automata
regular-language
+
–
0
votes
1
answer
6
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 ...
420
views
asked
May 29, 2018
Set Theory & Algebra
discrete-mathematics
set-theory&algebra
+
–
1
votes
0
answers
7
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
Databases
databases
concurrency
transaction-and-concurrency
+
–
0
votes
0
answers
8
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 ...
652
views
asked
May 12, 2018
Databases
natural-join
relational-algebra
databases
sql
+
–
0
votes
0
answers
9
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...
356
views
asked
Mar 24, 2018
Programming in C
shortest-path
algorithms
graph-algorithms
+
–
1
votes
1
answer
10
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
asked
Mar 2, 2018
Theory of Computation
finite-automata
non-determinism
theory-of-computation
+
–
0
votes
1
answer
11
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...
550
views
asked
Mar 2, 2018
Theory of Computation
regular-language
context-free-language
+
–
2
votes
1
answer
12
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...
547
views
asked
Mar 2, 2018
Theory of Computation
test-series
regular-language
context-free-language
theory-of-computation
+
–
1
votes
1
answer
13
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.6k
views
asked
Feb 1, 2018
Algorithms
dijkstras-algorithm
shortest-path
+
–
0
votes
0
answers
14
What is the family of language described?
Let $L_1$ and $L_2$ are two languages and both of them are accepted by DPDA. If $L=L_1-L_2$ is any languange , then what is the smallest language family $L'$ belongs to?
Let $L_1$ and $L_2$ are two languages and both of them are accepted by DPDA. If $L=L_1-L_2$ is any languange , then what is the smallest language family $L'$ belongs to?
335
views
asked
Dec 26, 2017
0
votes
0
answers
15
Which of given languages is/are DCFL / CLF?
DCFL or CFL? $L_1=\{0^n1^{2n} | n>=1\}$ $L_2=\{1^{2n}0^n | n>=1\}$
DCFL or CFL?$L_1=\{0^n1^{2n} | n>=1\}$$L_2=\{1^{2n}0^n | n>=1\}$
268
views
asked
Dec 24, 2017
1
votes
0
answers
16
Automata P problems
Which of the following problems is/are P-problems? I. Equivalence of DFA's II. Equivalence of NFA III. Equivalence of RE (a) Only I (b) Only I and II (c) Only II and III (d) All
Which of the following problems is/are P-problems?I. Equivalence of DFA'sII. Equivalence of NFAIII. Equivalence of RE(a) Only I(b) Only I and II(c) Only II and III(d) All...
404
views
asked
Dec 24, 2017
0
votes
0
answers
17
Characterisitics of weak entities
In E-R model , weak entity meets which of the following conditions Weak entity existence dependent i.e. weak entity cannot exist without the entity with which it has a relationship weak entity has a primary key that is partially or totally derived from the parent in the relationship Both (1) and (2) Neither 1 nor 2
In E-R model , weak entity meets which of the following conditionsWeak entity existence dependent i.e. weak entity cannot exist without the entity with which it has a rel...
837
views
asked
Dec 1, 2017
1
votes
1
answer
18
Number of stall cycles in case of branch misprediction
Consider that branch outcomes are determined in the EX stage and the pipeline uses some prediction mechanism. If the misprediction happens, how many stall cycles gets introduced per mispredicted branch instruction?
Consider that branch outcomes are determined in the EX stage and the pipeline uses some prediction mechanism. If the misprediction happens, how many stall cycles gets int...
543
views
asked
Jul 9, 2017
CO and Architecture
co-and-architecture
pipelining
stall
+
–
2
votes
1
answer
19
Dealing with ALU-ALU forwarding
Consider two instruction sequences: a. SW R16,-100(R6) LW R4, 8(R16) ADD R5,R4,R4 b. OR R1,R2,R3 OR R2,R1,R3 OR R1,R1,R2 Add NOP instructions to this code to eliminate hazards if there is ALU-ALU forwarding only (no forwarding from the MEM to the EX stage).
Consider two instruction sequences:a. SW R16,-100(R6) LW R4, 8(R16) ADD R5,R4,R4b. OR R1,R2,R3 OR R2,R1,R3 OR R1,R1,R2Add NOP instructions to this code to eli...
2.4k
views
asked
Jun 26, 2017
CO and Architecture
co-and-architecture
pipelining
operand-forwarding
+
–
3
votes
3
answers
20
Finding initial values of counting semaphore
Below are four concurrent processes and three counting semaphores. What must be the initial values of the three semaphores, so that output “TGE” is obtained?
Below are four concurrent processes and three counting semaphores.What must be the initial values of the three semaphores, so that output “TGE” is obtained?
2.6k
views
asked
Feb 14, 2017
Operating System
operating-system
semaphore
process-synchronization
+
–
Page:
1
2
3
4
next »
Email or Username
Show
Hide
Password
I forgot my password
Remember
Log in
Register
