Questions by Utk / GATE Overflow for GATE CSE

2 votes

1 answer

1

Probability IITB (RA) 2016
This question was asked in IITB (RA) 2016 admissions. Three person A, B and C each have a bag of five different coloured balls. All three bags have balls from same five colours. A grabs B and C's bag and took two balls without ... took two balls and put them in his bag without looking. What is the probability that all three bags have different coloured balls?

This question was asked in IITB (RA) 2016 admissions.Three person A, B and C each have a bag of five different coloured balls. All three bags have balls from same five co...

997 views

asked May 19, 2016

4 votes

2 answers

2

Conditional Probability IITB (RA) 2016
This question was asked in IITB (RA) admissions 2016. I have two blue dice, with which I play a game. If I throw a double six (i.e. if I get two six on both the dices) then I win the game. I separately throw a red dice. If I get ... rolled the three die. I turn around to you and said, "I won!". What is the probability that I actually won the game?

This question was asked in IITB (RA) admissions 2016.I have two blue dice, with which I play a game. If I throw a double six (i.e. if I get two six on both the dices) the...

1.0k views

asked May 19, 2016

1 votes

1 answer

3

MadeEasy Test Series: Algorithms - Asymptotic Notations
Let $f(n)$ = Ω(n) and g(n) = O(f(n)). Then g(n) = _______ [Assume n>0 ] (a.) Ω(n) (b.) O(n) (c.) θ(n) (d.) Ω(1) According to me, the answer should be (b.) since, f(n) has lowest bound n and g(n) has f(n) as upper bound. Answer given is (d.) I am confused about the answer.

Let $f(n)$ = Ω(n) and g(n) = O(f(n)). Then g(n) = _______ [Assume n>0 ](a.) Ω(n)(b.) O(n)(c.) θ(n)(d.) Ω(1) According to me, the answer should be (b.) since, f(n) has...

620 views

asked Feb 1, 2016

2 votes

2 answers

4

Tuple Relational Calculus
I believe since the variable 't' is a free variable, so option three should also be right. Second option is also correct?

I believe since the variable 't' is a free variable, so option three should also be right. Second option is also correct?

625 views

asked Jan 22, 2016

1 votes

2 answers

5

MadeEasy Test Series: Algorithms - Time Complexity
$T(n)=2T(\frac{n}{2})+n\log n$ for n>=2 and T(1)=0, then T(n) is (a.) $O(n)$ (b.) $O(n \log n)$ (c.) $O( n (\log n)^{2})$ (d.) $O(n^{2})$ Answer given is (c.) The solution is done using subsitution, n = $2^{k}$ But if we do with Master's theorem, then we will get option (b.) and this a case for Master's theorem, right?

$T(n)=2T(\frac{n}{2})+n\log n$ for n>=2 and T(1)=0, then T(n) is(a.) $O(n)$(b.) $O(n \log n)$(c.) $O( n (\log n)^{2})$(d.) $O(n^{2})$ Answer given is (c.) The solution is...

502 views

asked Jan 20, 2016

3 votes

1 answer

6

MadeEasy Test Series: Theory Of Computation - Decidability
Consider the following languages A={<M>|M is a TM and |L(M)| >= 3} B={<M>|M is a TM that accepts some string} Which of the following is correct? (a.) A is decidable, B is partially decidable (b.) A is ... decidable (c.) Both A and B are decidable (d.) Both A and B are partially decidable Answer given : (d.) But how?

Consider the following languagesA={<M>|M is a TM and |L(M)| >= 3}B={<M>|M is a TM that accepts some string}Which of the following is correct?(a.) A is decidable, B is par...

759 views

asked Jan 19, 2016

1 votes

1 answer

7

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

asked Jan 16, 2016

0 votes

1 answer

8

MadeEasy Test Series: Operating System - Process
A process spends 20% of its execution time waiting for completion of I/O operation. If there are 4 such processes in memory at once, then the probability of CPU time wasted is _. (Assuming all I/O operations are overlapped) Answer ... with waiting time 't', then probability of CPU time utilization is $t^{n}$. How is this formula coming?

A process spends 20% of its execution time waiting for completion of I/O operation. If there are 4 such processes in memory at once, then the probability of CPU time wast...

864 views

asked Jan 16, 2016

5 votes

1 answer

9

Computing the dual of the boolean function
Suppose, $f(A,B,C,D) = \sum m(0,2,4,6)$ is a boolean expression, expressed in minterm form. How can I calculate and express the dual of the function? I have tried the method using the exact definition, but it turns out to be very cumbersome and prone to errors. Any other method?

Suppose, $f(A,B,C,D) = \sum m(0,2,4,6)$ is a boolean expression, expressed in minterm form. How can I calculate and express the dual of the function?I have tried the meth...

6.8k views

asked Jan 16, 2016

4 votes

1 answer

10

Mathematical Logic Meaning of the given statements
Which predicate logic means, "There are at most two men in class"? $\forall x\forall y((Male(x)\wedge Male(y))\rightarrow (x=y \vee y=x)$ ... How do I know the meaning of the statements? I want to know the working steps.

Which predicate logic means, "There are at most two men in class"?$\forall x\forall y((Male(x)\wedge Male(y))\rightarrow (x=y \vee y=x)$$\exists x \exists y (Male(x)\wedg...

709 views

asked Jan 14, 2016

2 votes

2 answers

11

Minimum number of states in the DFA
What is the minimum number of states in the DFA for accepting the strings $(a+b)^{*}a(a+b)(a+b)$ I draw the following DFA The minimum number of states is 4. The answer given is 8. How is it possible? Please explain.

What is the minimum number of states in the DFA for accepting the strings $(a+b)^{*}a(a+b)(a+b)$I draw the following DFA The minimum number of states is 4. The answer giv...

16.2k views

asked Jan 13, 2016

0 votes

1 answer

12

Different possible integer solutions for the given function
How many integer solutions exist for the given equation $x+y+z=15$ subject to the constraint that $0\leq x,y,z\leq 10$? I tried the brute force method and listed the possible solution sets for the above equation, ... should be 16 * 6 = 96 possible solutions. The answer given was 3666, derived using Generating functions. Please explain.

How many integer solutions exist for the given equation $x+y+z=15$ subject to the constraint that $0\leq x,y,z\leq 10$?I tried the brute force method and listed the possi...

691 views

asked Jan 13, 2016

1 votes

3 answers

13

The boolean expression f(x,y,z) in its canonical form for the decoder circuit shown below is
Note : the bubbles are NOT gates

Note : the bubbles are NOT gates

3.4k views

asked Jan 11, 2016

0 votes

2 answers

14

A digital circuit which compares two numbers A2A1A0 and B2B1B0 is shown in figure
How it is that EXNOR is a odd function?

How it is that EXNOR is a odd function?

1.2k views

asked Jan 11, 2016

1 votes

2 answers

15

Integration in Sinx and Cosx
My answer is coming 0. Please explain.

My answer is coming 0. Please explain.

2.2k views

asked Jan 11, 2016

1 votes

1 answer

16

MadeEasy Test Series: Algorithms - Dynamic Programming
Given an array of n numbers, give an algorithm for finding a contiguous subsequence A(i) ...A(j) for which the sum of elements is maximum. Eg. [-2, 11, -4, 13, -5, 2] → 20 If dynamic programming approach is used then what is time complexity and space complexity? (a ... b.) O(n), O(n) (c.) O(n3), O(n) (d.) O(n2), O(1) Given answer is option (b.)

Given an array of n numbers, give an algorithm for finding a contiguous subsequence A(i) ...A(j) for which the sum of elements is maximum.Eg. [-2, 11, -4, 13, -5, 2] → ...

1.2k views

asked Jan 11, 2016

1 votes

1 answer

17

Execution time on a pipelined processor, given execution time on a non-pipelined processor
A program executes on a non-pipelined processor in time t. The same program is executed on a m-stage pipelined processor, with each stage delay d. Then, how it is that the execution time of the program ... have this term "t / m". I can't understand the logic behind this term. Please explain.

A program executes on a non-pipelined processor in time t. The same program is executed on a m-stage pipelined processor, with each stage delay d. Then, how it is that th...

578 views

asked Jan 7, 2016

2 votes

1 answer

18

Number of different possible orders for traversing to a particular node in a Binary Search Tree
When searching for the key value 50 in a binary search tree, node containing the key values 10, 30, 40, 70, 90, 120, 150, 175 are traversed, in any order. The number of different orders passing ... these keys values can occur on the search path from the root to node containing the value 50 are ________.

When searching for the key value 50 in a binary search tree, node containing the key values 10, 30, 40, 70, 90, 120, 150, 175 are traversed, in any order. The number of d...

682 views

asked Jan 4, 2016

1 votes

1 answer

19

Language and its compliment
Given $(L')^* = (L^*)' where ' is complement operation. $L$ is ? $ \phi, \{\epsilon \}$ and $ \Sigma^*$ $\{\epsilon \}$ and $\Sigma^*$ $ \phi $ and $\{\epsilon \} $ $L$ is not any of $\phi, \{\ ... $\Sigma^*$ Please someone explain the meaning of ∅ and comp(∅) also. This question got me confused over the meaning of ∈ also.

Given $(L')^* = (L^*)' where ' is complement operation.$L$ is ?$ \phi, \{\epsilon \}$ and $ \Sigma^*$$\{\epsilon \}$ and $\Sigma^*$$ \phi $ and $\{\epsilon \} $$L$ is no...

568 views

asked Jan 4, 2016

0 votes

1 answer

20

Given the unordered linked list as a queue, what operations would take O(1) time?
My doubt is that the single list queue is the form : 1->2->3->4->5->6->7->8->9->NULL with 1 as the rear node and 9 as the front node. Also, in a queue, addition ... I just want to confirm whether my answer was right or the answer given. Source : testbook.com live test on 3rd January, 2016

My doubt is that the single list queue is the form : 1->2->3->4->5->6->7->8->9->NULL with 1 as the rear node and 9 as the front node. Also, in a queue, addition takes fro...

612 views

asked Jan 4, 2016

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