Questions by Shreya Roy - GATE Overflow

+14 votes

3 answers

1

ISI Entrance Exam MTech (CS)
Consider all possible trees with $n$ nodes. Let $k$ be the number of nodes with degree greater than $1$ in a given tree. What is the maximum possible value of $k$?

asked Apr 6, 2017 in Graph Theory | 963 views

+1 vote

1 answer

2

IIITH-PGEE
how many way we can select 4 candies from 6 different groups?

asked Mar 16, 2017 in Set Theory & Algebra | 540 views

0 votes

2 answers

3

ROM Size to build the combinational circuit
Specify the size of a ROM (number of words and number of bits per word) that will accommodate the truth table for the following combinational circuit : a code converter from a 4-digit BCD number to a binary number.

asked Mar 10, 2017 in Digital Logic | 713 views

+1 vote

1 answer

4

Kurose Exercise

asked Mar 2, 2017 in Computer Networks | 160 views

+1 vote

1 answer

5

IIT Kanpur written
If a graph has k-independent components, it it n-k+1 colorable

asked Feb 28, 2017 in Algorithms | 146 views

+3 votes

1 answer

6

IIT Kanpur written test
Number of distinct BFS, DFS trees in a complete graph ?

asked Feb 28, 2017 in Algorithms | 367 views

0 votes

1 answer

7

Test Series
https://gateoverflow.in/?qa=blob&qa_blobid=4549376166631720003

asked Jan 14, 2017 in Calculus | 146 views

0 votes

0 answers

8

Doubt
What is Dijkstra's algorithm running time using sorted array?

asked Dec 20, 2016 in Algorithms | 73 views

0 votes

1 answer

9

GateCse Fb post
How many equivalence relations with exactly 3 equivalence classes are there on a set with 5 elements?

asked Dec 14, 2016 in Set Theory & Algebra | 189 views

0 votes

1 answer

10

Doubt
To change mode from privileged(kernel) to nonprivileged(user) is privileged instruction always necessary or it is architecture dependent?

asked Dec 12, 2016 in Operating System | 56 views

0 votes

0 answers

11

Gate Computer Science group Fb post

asked Nov 29, 2016 in Set Theory & Algebra | 129 views

0 votes

0 answers

12

Doubt
Code for Producer: while (true) { /* produce an item in nextProduced */ while (counter == BUFFER.SIZE) ; /* do nothing */ wait(mutex); buffer[in] = nextProduced; in = (in + 1) % BUFFER-SIZE; counter++; signal(mutex); } Code for consumer ... BUFFER_SIZE; counter--; signal(mutex); } Can this be an alternative solution for bound buffer problem(where only one semaphore is used instead of three)?

asked Nov 27, 2016 in Operating System | 124 views

+8 votes

1 answer

13

Virtual Gate Test Series: Computer Networks - Bottleneck Bandwidth

asked Nov 19, 2016 in Computer Networks | 680 views

+2 votes

1 answer

14

Gatebook TOC
Let M be a single-tape deterministic TM with tape alphabet { blank, 0, 1 }, and let C denote the ( possibly infinite ) computation of M starting with a blank tape. The input to each problem is M, together with a positive integer n. Which of the following problems is(are) decidable ... tape cells during the company C (A). III only (B). I and II only (C).I and III only (D).I,II and III

asked Nov 19, 2016 in Theory of Computation | 139 views

+1 vote

2 answers

15

Theory of computation Gatebook
Which of the following problems is(are) decidable ? I. Given a (finite) string W, is W a prefix of the decimal expansion of $\pi$ II. Given a Program and an input, is the programs output the decimal expansion of $\pi$ III. Given a Program and an input a ... prorams output always the same for every prifix (A). I only (B). II only (C). I and II only (D). III only

asked Nov 19, 2016 in Theory of Computation | 157 views

+1 vote

0 answers

16

Theory of Computation
Which of the following statements is Decidable? S1: The set of all TM's that given an input eventually write a non blank symbol on their tapes S2: The set of all TM's that given an input visits an arbitrary state q (A). S1 only (B). S2 only (C). Both (D). None

asked Nov 19, 2016 in Theory of Computation | 194 views

+2 votes

0 answers

17

Theory of Computation
There is a CFG with only 2 variables, and a single terminal, and 2 only productions (No unit, epsilon, useless products, left recursion,). What would be the max number of productions if that gets converted into GNF (A). 2 (B). <=4 (C). <=8 (D). None

asked Nov 19, 2016 in Theory of Computation | 62 views

+3 votes

2 answers

18

TOC Gatebook
Let L = {xy | xwy L1, |x| = |w| = |y|}. Then L is(L1 is regular) (A). Regular (B). Non regular (C). May be regular (D). None

asked Nov 18, 2016 in Theory of Computation | 312 views

0 votes

1 answer

19

Gatebook Test
Which of the following languages are decidable? (A). The set of TM's whose languages contain 0* (B). The set of all TM's that accept same language by visiting at most 100 distinct tape cells (C). The set of pairs of TM's that generate the same language (D). The set of TM's whose language are not empty

asked Nov 14, 2016 in Theory of Computation | 104 views

+2 votes

1 answer

20

GBook
L = {B(N)#B(N+1) : B(N) represents binary pattern for given N. Example B(5)=101, N>=1}. Then which of the following is true for L? (A). L is regular (B). L is CFL but not regular (C). L is Recursive but not CFL (D). L is recursive enumerable but not recursive

asked Nov 14, 2016 in Theory of Computation | 165 views

+1 vote

0 answers

21

Gatebook
Let L={x | x ϵ (0+1)* ,If x_{i}(bit at ith position of x)=1 then each of the next i positions must be a 1} then L is (A). R.E but not Recursive (B). CFL but not regular (C). Recursive but not C.F.L (D). Regular

asked Nov 14, 2016 in Theory of Computation | 84 views

+4 votes

1 answer

22

GB TOC Q13
Which of the following is not regular? (A). {/n>=0 and input alphabet is {a,b}} (B). where i+j+k>100 & k>50 (C). where i+j+k>100 & j+k>50 (D). None of the above

asked Nov 14, 2016 in Theory of Computation | 215 views

0 votes

2 answers

23

Gate Computer Science FB group post
A hash table has space for 100 records .what is the probability of collision before it is 5% full?? a. 0.25 b. 0.10 c. 0.40 d. 0.20

asked Nov 7, 2016 in Algorithms | 317 views

+1 vote

1 answer

24

MadeEasy Test Series: Combinatory - Permutations And Combinations
Number of 10 bit binary string where the string contains 3 consecutive 0's or 3 consecutive 1's?

asked Sep 16, 2016 in Combinatory | 117 views