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 | 1.1k 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 | 683 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 | 855 views

+1 vote

1 answer

4

Kurose Exercise

asked Mar 3, 2017 in Computer Networks | 216 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 | 160 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 | 655 views

0 votes

1 answer

7

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

asked Jan 15, 2017 in Calculus | 165 views

+1 vote

1 answer

8

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

asked Dec 20, 2016 in Algorithms | 98 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 | 207 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 | 68 views

0 votes

0 answers

11

Gate Computer Science group Fb post

asked Nov 29, 2016 in Set Theory & Algebra | 147 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 28, 2016 in Operating System | 184 views

+8 votes

1 answer

13

Virtual Gate Test Series: Computer Networks - Bottleneck Bandwidth

asked Nov 20, 2016 in Computer Networks | 700 views

+3 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 | 189 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 | 183 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 | 207 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 | 92 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 19, 2016 in Theory of Computation | 345 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 15, 2016 in Theory of Computation | 113 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 15, 2016 in Theory of Computation | 183 views