Questions by GateAspirant999

0 votes

1 answer

1

Time complexity of code given

asked in Algorithms Sep 17, 2018

586 views

0 votes

0 answers

2

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

asked in Mathematical Logic Sep 15, 2018

178 views

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Questions by GateAspirant999

Subscribe to GATE CSE 2023 Test Series

Subscribe to GO Classes for GATE CSE 2023

Subjects

Questions by GateAspirant999

Subscribe to GATE CSE 2023 Test Series

Subscribe to GO Classes for GATE CSE 2023

Recent Posts

Subjects

Recent Blog Comments