GATE CSE
For all GATE CSE Questions
Toggle navigation
GATE Overflow
Facebook Login
Google Login
or
Email or Username
Password
Remember
Login
Register

I forgot my password
All Activity
Questions
Unanswered
Tags
Subjects
Users
Ask
Previous
Blogs
New Blog
Exams
First time here? Checkout the
FAQ
!
x
×
Close
Use the google search bar on side panel. It searches through all previous GATE/other questions.
Recent activity by jothee
User jothee
Wall
Recent activity
All questions
All answers
Exams Taken
All Blogs
User jothee
Wall
Recent activity
All questions
All answers
Exams Taken
All Blogs
1
answer
1
UGCNETJune2014III72
Four bits are used for packed sequence numbering in a slinding window protocol used in a computer network. What is the maximum window size? 4 8 15 16
asked
Jan 6
in
Others

30
views
ugcnetjune2014iii
0
answers
2
UGCNETJune2014III17
Assume that a program will experience 200 failures in infinite time. It has now experienced 100 failures. The initial failure intensity was 20 failures/CPU hr. Then the current failure intensity will be 5 failured/CPU hr 10 failured/CPU hr 20 failured/CPU hr 40 failured/CPU hr
asked
Jan 6
in
Others

34
views
ugcnetjune2014iii
0
answers
3
UGCNETJune2014III16
Software testing is the process of establishing that errors are not present the process of establishing confidence that a program does what it is supposed to do the process of executing a program to show that it is working as per specifications the process of executing a program with the intent of finding errors
asked
Jan 6
in
Others

21
views
ugcnetjune2014iii
0
answers
4
UGCNETJune2014III15
Let L be aby language. Define even (W) as the strings obtained by extracting from W the letters in the evennumbered positions and even(L) = { even (W) $\mid$ W $\in$ L}. We define another language Chop (L) by removing the two leftmost ... Chop(L) are regular Even(L) is not regular and Chop(L) is regular Both even(L) and Chop(L) are not regular
asked
Jan 6
in
Others

22
views
ugcnetjune2014iii
0
answers
5
UGCNETJune2014III14
Which one of the following describes the syntax of prolog program? Rules and facts are terminated by full stop(.) Rules and facts are terminated by semi colon(;) Variables names must start with upper case alphabets. Variables names must start with lower case alphabets. I, II III, IV I, III II, IV
asked
Jan 5
in
Others

11
views
ugcnetjune2014iii
0
answers
6
UGCNETJune2014III07
Given $U=\{1, 2, 3, 4, 5, 6, 7 \} \\ A =\{(3, 0.7), (5, 1), (6, 0.8) \}$ then $\tilde{A}$ will be: (where $\sim \rightarrow$ complement) $\{(4, 0.7), (2, 1), (1, 0.8)\}$ $\{(4, 0.3), (5, 0), (6, 0.2)\}$ $\{(1, 1), (2, 1), (3, 0.3), (4, 1), (6, 0.2), (7, 1) \}$ $\{(3, 0.3), (6, 0.2)\}$
asked
Jan 5
in
Others

18
views
ugcnetjune2014iii
2
answers
7
UGCNETJune2014II05
Match the following : List  I List  II a. Physical layer i. Allow resources to network access b. Datalink layer ii. Move packets from one destination to other c. Network layer iii. Process to process message delivery d. Transport layer iv. Transmission of bit stream e. ... ; eiii ai; biii; cii; dv; eiv ai; bii; civ; diii; ev
edited
Jan 3
in
Computer Networks

89
views
ugcnetjune2014ii
computernetworks
networklayering
1
answer
8
CMI2016B7ai
Consider the funciton $M$ defined as follows: $M(n) = \begin{cases} n10 & \text{ if } n > 100 \\ M(M(n+11)) & \text{ if } n \leq 100 \end{cases}$ Compute the following: M(101)
asked
Dec 31, 2016
in
Others

18
views
cmi2016
descriptive
0
answers
9
CMI2016B7b
Consider the funciton $M$ defined as follows: $M(n) = \begin{cases} n10 & \text{ if } n > 100 \\ M(M(n+11)) & \text{ if } n \leq 100 \end{cases}$ Give a constant time algorithm that computes $M(n)$ on input $n$. (A contanttime algorithm is one whose running time is independent of the input $n$)
asked
Dec 31, 2016
in
Others

8
views
cmi2016
descriptive
1
answer
10
CMI2016B7aiii
Consider the funciton $M$ defined as follows: $M(n) = \begin{cases} n10 & \text{ if } n > 100 \\ M(M(n+11)) & \text{ if } n \leq 100 \end{cases}$ Compute the following: M(87)
asked
Dec 31, 2016
in
Others

18
views
cmi2016
descriptive
2
answers
11
CMI2016B7aii
Consider the funciton $M$ defined as follows: $M(n) = \begin{cases} n10 & \text{ if } n > 100 \\ M(M(n+11)) & \text{ if } n \leq 100 \end{cases}$ Compute the following: M(99)
asked
Dec 31, 2016
in
Others

33
views
cmi2016
descriptive
0
answers
12
CMI2016B6
An automatic spelling checker works as follows. Given a word $w$, first check if $w$ is found in the dictionary. If $w$ is not in the dictionary, compute a dictionary entry that is close to $w$. For instance if the user types $\mathsf{ocurrance ... alignments of $x$ and $y$. What is the running time of your algorithm (in terms of the lengths of $x$ and $y$)?
asked
Dec 31, 2016
in
Others

8
views
cmi2016
descriptive
0
answers
13
CMI2016B5
For a string $x=a_0a_1 \ cdots a_{n1}$ over the alphabet $\{0, 1, 2\}$, define $val(x)$ to be the value of $x$ interpreted as a ternary number, where $a_0$ is the most significant digit. More formally, $val(x)$ is given by $$ \Sigma_{0 \leq ... automaton that accepts exactly the set of strings $ x \in \{0, 1, 2\}^*$ such that $val(x)$ is divisible by 4.
asked
Dec 30, 2016
in
Others

12
views
cmi2016
descriptive
0
answers
14
CMI2016B4
Let $\Sigma  \{0, 1\}$. Let $A, \: B$ be arbitrary subsets of $\Sigma^*$. We define the following operatins on such sets: $$ A+B := \{ w \in \Sigma^* \mid w \in A \text{ or } w \in B \}$$ $$A \cdot B := \{ uv \in \ ... B +2(A \cdot B)$ for all choices of $A$ and $B$? If yes, give a proof. If not, provide suitable $A$ and $B$ for which this equation fails.
asked
Dec 30, 2016
in
Others

11
views
cmi2016
descriptive
0
answers
15
CMI2016B3
An undirected graph canbe converted into a directed graph by choosing a direction for every edge. Here is an example: Show that for every undirected graph, there is a way of choosing directions for its edges so that the resulting directed graph has no directed cycles.
asked
Dec 30, 2016
in
Others

11
views
cmi2016
descriptive
0
answers
16
CMI2016B2b
A $\textit{simple path}$ (respectively cycle) in a graph is a path (respectively cycle) in which no edge or vertex os repeated. The $length$ of such a path (respectively cycle) is the number of edges in the path (respectively cycle). Let ... an undirected graph with minimum degree $k \geq 2$. Show that $G$ contains a simple cycle of length at least $k+1$.
asked
Dec 30, 2016
in
Others

7
views
cmi2016
descriptive
0
answers
17
CMI2016B2a
A $\textit{simple path}$ (respectively cycle) in a graph is a path (respectively cycle) in which no edge or vertex os repeated. The $length$ of such a path (respectively cycle) is the number of edges in the path (respectively cycle). Let $G$ be an undirected graph with minimum degree $k \geq 2$. Show that $G$ contains a simple path of length at least $k$.
asked
Dec 30, 2016
in
Others

5
views
cmi2016
descriptive
0
answers
18
CMI2016B1
A group of war prisoners are trying to escape from a prison. They have thoroughly planned teh escape from the prison itself, and after that they hope to find shelter in a nearby village. However, the village (marked as $B$, see ... assuming that soldiers do not change their locations ($Hint$: Model this as a graph, with soldiers represented by the vertices.)
asked
Dec 30, 2016
in
Others

13
views
cmi2016
descriptive
1
answer
19
CMI2016A10
Which of the following relationships holds in general between the $scope$ of a variable and the $lifetime$ of a variable (in a language like C or Java)? The scope of a variable is contained in the lifetime of the variable The scope of ... as the lifetime of the variable The lifetime of a variable is disjoint from the scope of the variable None of the above
asked
Dec 30, 2016
in
Others

25
views
cmi2016
0
answers
20
CMI2016A9
ScamTel has won a state government contract to connect 17 cities by highspeed fibre optic links. Each link will connect a pair of cities so that the entire network is connectedthere is a path from each city to every otehr city. The cotract ... if $any$ single link fails. What is the minimum number of links that ScamTel needs to set up? 34 32 17 16
asked
Dec 30, 2016
in
Others

7
views
cmi2016
0
answers
21
CMI2016A8
An advertisement for a tennis magazine states, "If I'm not playin tennis, I'm watching tennis. And If I'm not watching tennis, I'm reading about tennis." We can assume that the speaker can do at most one of these activities at a time. What is the speaker doing? Playing tennis Watcging tennis Reading about tennis None of the above
asked
Dec 30, 2016
in
Others

9
views
cmi2016
1
answer
22
CMI2016A7
Varsha lives alone and dislikes cooking, so she goes out for dinner every evening. She has two favourite restaurants, $\textit{Dosa Paradise}$ and $\textit{Kababs Unlimited}$, to which she travels by local train. The train to $\textit{Dosa Paradise}$ runs every 10 minutes, ... textit{Kababs Unlimited}$? $\frac{1}{5}$ $\frac{1}{3}$ $\frac{2}{5}$ $\frac{1}{2}$
asked
Dec 30, 2016
in
Others

27
views
cmi2016
0
answers
23
CMI2016A6
In the code fragment given below, $\mathsf{start}$ and $\mathsf{end}$ are integer values and $\mathsf{prime(x)}$ is a function that returns $\mathsf{true}$ if $\mathsf{x}$ is a prime number and $\mathsf{false}$ otherwise. i:=0; j:=0; k:=0; from (m := start; ... the end of the loop: k == ij. k == ji. k == ji. Depends on $\mathsf{start}$ and $\mathsf{end}$
asked
Dec 30, 2016
in
Others

7
views
cmi2016
1
answer
24
CMI2016A5
A dodecahedron is a regular solid with 12 faces, each face being a regular pentagon. How many edges are there? And how many vertices? 60 edges and 20 vertices 30 edges and 20 vertices 60 edges and 50 vertices 30 edges and 50 vertices
asked
Dec 30, 2016
in
Others

17
views
cmi2016
1
answer
25
CMI2016A4
Consider a weighted undirected graph $G$ with positive edge weights. Let $(u, v)$ be an edge in the graph. It is known that the shortest path from a vertex $s$ to $u$ has weight 53 and the shortest path from $s$ to to $v$ has weight 65. Which of the statements is ... of $(u, v) = 12$ Weight of $(u, v) \geq 12$ Nothing can be said about the weight of $(u, v)$
asked
Dec 30, 2016
in
Others

15
views
cmi2016
1
answer
26
CMI2016A3
For a regular expression $e$, let $L(e)$ be the language generated by $e$. If $e$ is an expression that has no Kleene star $*$ occuring in it, which of the following is true about $e$ in general? $L(e)$ is empty $L(e)$ is finite Complement of $L(e)$ is empty Both $L(e)$ and its complement are infinite
asked
Dec 30, 2016
in
Others

13
views
cmi2016
1
answer
27
CMI2016A2
The symbol $\mid$ reads as "divides", and $\nmid$ as "does not divide". For instance, $2 \: \mid \:6$ and $2 \: \nmid \: 5$ are both true. Consider the following statements. There exists a positive integer $a$ such that $(2 ... you say about these statements? Only i is true Only ii is true Both i and ii are true Neither i nor ii is true
asked
Dec 30, 2016
in
Others

28
views
cmi2016
1
answer
28
CMI2016A1
In a connected undirected graph, the distance between two vertices is the number of edges in the shortest path between them. Suppose we denote bt $P$ the following property: $\textit{there exists a vertex that is a neighbour of all other vertices}$. ... about these statements? Only i is true Only ii is true Both i and ii are true Neither i nor ii is true
asked
Dec 30, 2016
in
Others

13
views
cmi2016
1
answer
29
TIFR2016B15
Let $G$ be an undirected graph. For a pair $(x, y)$ of distinct vertices of $G$, let $\mathsf{mincut}(x, y)$ be the least number of edges that should be delted from $G$ so that the resulting graph has no $xy$ path. Let $a, b, ... are possible but neither ii nor iii ii and iv are possible but neither i not iii iii and iv are possible but neither i nor ii
asked
Dec 29, 2016
in
Others

32
views
tifr2016
1
answer
30
TIFR2016B14
Consider a family $\mathcal{F}$ of subsets of $\{1, 2, \dots , n\}$ such that for any two distinct sets $A$ and $B$ in $\mathcal{F}$ we have: $A \subset B$ or $ B \subset A$ or $A \cap B = \emptyset$. Which of the following statements is TRUE? ... 2^{n1}$ and there exists a family $\mathcal{F}$ such that $\mid \mathcal{F} \mid =2^{n1}$ None of the above
asked
Dec 29, 2016
in
Others

59
views
tifr2016
1
answer
31
TIFR2016B13
An undorected graph $G = (V, E)$ is said to be $k$colourable if there exists a mapping $c: V \rightarrow \{1, 2, \dots k \}$ such that for every edge $\{u, v\} \in E$ we have $c(u) \neq c(v)$. Which of the ... is the maximum degree in $G$ There is a polynomial time algorithm to check if $G$ is 2colourable If $G$ has no triangle then it is 3colourable
asked
Dec 29, 2016
in
Others

15
views
tifr2016
0
answers
32
TIFR2016B12
A computer program computes a function $\: f \: \{0, 1\}^* \times \{0, 1\}^* \rightarrow \{0, 1\}^*$. Suppose $f(a, b)$ ahs length $\mid b \mid ^2$, where $\mid a \mid$ and $\mid b \mid$ are the lengths of $a$ and $b$. Suppose, using this program, the ... \leq n^2$ $n^2 < t \leq n^{\log_2 n}$ $ n^{\log_2 n} < t \leq 2^{(2n)}$ $2^{(2n)} < t$
asked
Dec 29, 2016
in
Others

21
views
tifr2016
0
answers
33
TIFR2016B11
Let $n \geq 4$ be an integer. Regard the set $\mathbb{R}^n$ as a vector space over $\mathbb{R}$. Consider the following undirected graph $H$. $$ V(H) = \{S \subseteq \mathbb{R}^n : \: S \text{ is a ... an inifinite number of vertices The diameter of $H$ is infinite $H$ is conneceted $H$ contains an infinite clique $H$ contains an infinite independent set
asked
Dec 29, 2016
in
Others

19
views
tifr2016
0
answers
34
TIFR2016B10
A $vertex \: cover$ in an undirected graph $G$ is a subset $ C \subseteq V(G)$ such that every edge of $G$ has an endpoint in $C$. An independent set in $G$ is a subset $I \subseteq V(G)$ such that no edge has both its endpoints in $I$. Which of the ... mid E(G)\mid /2$ $\mid C \mid \: \: \geq \: \: \mid V(G)\mid /2$ $C$ intersects every independent set
asked
Dec 29, 2016
in
Others

11
views
tifr2016
1
answer
35
TIFR2016B9
Which of the following graphs DOES NOT have an Eulerian circuit? (Recall that an Eulerian circuit in an undirected graph is a walk in the graph that starts at a vertex ans returns to the vertex after tracelling on each edge exactly once.) $K_{9, 9}$ $K_{8, 8}$ $K_{12, 12}$ $K_9$ ... \{ \{i, j\} : 1 \leq i < j \leq 5 \: or \: 5 \leq i < j \leq 9 \}.$$
asked
Dec 29, 2016
in
Others

36
views
tifr2016
1
answer
36
TIFR2016B8
Consider the following language $$\mathsf{PRIMES} = \Biggl\{ \underbrace{111 \dots 11}_{p \: \text{ times} } : \: p \: \text{ is prime } \Biggl\}$$ Then, which of the following is TRUE? $\mathsf{PRIMES}$ is regular $\mathsf{ ... is decidable in polynomial time $\mathsf{PRIMES}$ is context free but not regular $\mathsf{PRIMES}$ is NPcomplete and P $\neq$ NP
asked
Dec 29, 2016
in
Others

31
views
tifr2016
0
answers
37
TIFR2016B6
A subset $X$ of $\mathbb{R}^n$ is convex if for all $x, y \in X$ and all $\lambda \in (0, 1)$, we have $\lambda x + (1 \lambda)y \in X$. If $X$ is a convex set, which of the following statements is necessarily TRUE? For every $ x \in X$ there ... )/n \in X$ If $x \in X$, then $\lambda x \in X$ for all scalars $\lambda$ If $x, y \in X$, then $xy \in X$
asked
Dec 28, 2016
in
Others

9
views
tifr2016
1
answer
38
TIFR2016B5
Consider the recursive function $\mathsf{mc91}$. int mc91(int n) { print n if (n > 100) { return n10; } else { return mc91(mc91(n+11)); } } Let $\mathsf{Out}=\{n : \text{ there is an } x \in \{0, 1, \dots , 100 \} \text{ such that } n \text{ is one of the ... }$ $\{ n: 0 \leq n \leq 110 \}$ $\{ n: 0 \leq n \leq 111 \}$ $\{ n: 0 \leq n < + \infty \}$
asked
Dec 28, 2016
in
Others

37
views
tifr2016
1
answer
39
TIFR2016B4
In the following, $A$ stands fors a set of apples, and $S(x, y)$ stands for "$x$ is sweeter than $y$. Let $$\Psi \equiv \exists x : x \in A$$ $$\Phi \equiv \forall x \in A : \exists y \in A : S(x, y).$$ Which of the following statements implies that there are ... \neg S(x, x)] \wedge [\forall x, y, z \in A : S(x, y) \wedge S(y, z) \rightarrow s(x, z)]$
asked
Dec 28, 2016
in
Mathematical Logic

131
views
tifr2016
mathematicallogic
firstorderlogic
1
answer
40
TIFR2016B3
Assume $P \neq NP$. Which of the following is not TRUE? 2SAT in NP 2SAT in coNP 3SAT is polynmialtime reducible to 2SAT 4SAT is polynmialtime reducible to 3SAT 2SAT in P
asked
Dec 28, 2016
in
Others

15
views
tifr2016
19,237
questions
24,127
answers
53,273
comments
20,326
users