Login
Register
@
Dark Mode
Profile
Edit my Profile
Messages
My favorites
Register
Activity
Q&A
Questions
Unanswered
Tags
Subjects
Users
Ask
Previous Years
Blogs
New Blog
Exams
Dark Mode
Filter
User GateAspirant999
Wall
Recent activity
All questions
All answers
Exams Taken
All Blogs
Questions by GateAspirant999
0
votes
1
answer
1
Time complexity of code given
asked
in
Algorithms
Sep 17, 2018
586
views
algorithms
sorting
time-complexity
numerical-answers
test-series
0
votes
0
answers
2
Time complexity of given code using "finite" geometric series
Solved!!!
asked
in
Mathematical Logic
Sep 15, 2018
178
views
time-complexity
algorithms
1
vote
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)
asked
in
Digital Logic
Aug 19, 2018
3.7k
views
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?
asked
in
Theory of Computation
Jul 6, 2018
8.9k
views
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?
asked
in
Theory of Computation
Jul 1, 2018
857
views
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)$ ?
asked
in
Set Theory & Algebra
May 30, 2018
257
views
discrete-mathematics
set-theory&algebra
1
vote
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?
asked
in
Databases
May 21, 2018
2.8k
views
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$?
asked
in
Databases
May 12, 2018
508
views
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?
asked
in
Programming
Mar 24, 2018
205
views
shortest-path
algorithms
graph-algorithms
1
vote
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
asked
in
Theory of Computation
Mar 2, 2018
673
views
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
asked
in
Theory of Computation
Mar 2, 2018
377
views
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, 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
352
views
test-series
regular-language
context-free-language
theory-of-computation
1
vote
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 ... no -ve edge weight cycle reachable from source node. Am I correct with this? or am I missing something here?
asked
in
Algorithms
Feb 1, 2018
2.9k
views
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?
asked
in
Theory of Computation
Dec 26, 2017
165
views
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\}$
asked
in
Theory of Computation
Dec 24, 2017
171
views
1
vote
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
asked
in
Theory of Computation
Dec 24, 2017
271
views
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
asked
in
Databases
Dec 1, 2017
711
views
1
vote
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?
asked
in
CO and Architecture
Jul 9, 2017
419
views
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).
asked
in
CO and Architecture
Jun 26, 2017
1.8k
views
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?
asked
in
Operating System
Feb 15, 2017
1.9k
views
operating-system
semaphore
process-synchronization
Page:
1
2
3
4
next »
Subscribe to GATE CSE 2023 Test Series
Subscribe to GO Classes for GATE CSE 2023
Quick search syntax
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
Recent Posts
DRDO Previous Year Papers
From Rank 4200 to 64: My Journey to Success in GATE CSE Exam
What are the key things to focus on during the final 10-15 days before the GATE exam to improve performance?
All India GO Classes Mock test
NTA UGC NET JRF December 2022 Apply Online Form 2023
Subjects
All categories
General Aptitude
(2.5k)
Engineering Mathematics
(9.3k)
Digital Logic
(3.3k)
Programming and DS
(5.8k)
Algorithms
(4.6k)
Theory of Computation
(6.7k)
Compiler Design
(2.3k)
Operating System
(5.0k)
Databases
(4.6k)
CO and Architecture
(3.8k)
Computer Networks
(4.6k)
Non GATE
(1.3k)
Others
(2.4k)
Admissions
(649)
Exam Queries
(842)
Tier 1 Placement Questions
(17)
Job Queries
(74)
Projects
(9)
Unknown Category
(853)
Recent Blog Comments
@amit166 can you share the reference of the...
Twist at every point Man
Diagonalization of a MatrixIf there is an...
"i applied to amazon for 6 times,flipkart 2...
The Memes were inserted perfectly😁😁