Answers by janakyMurthy / GATE Overflow for GATE CSE

5 votes

1

GATE CSE 2000 | Question: 15
Suppose you are given arrays $p [1......N]$ and $q [1......N]$ both uninitialized, that is, each location may contain an arbitrary value), and a variable count, initialized to $0$. Consider the following procedures $set$ and $is\_set$: set(i) { count ... $set(i)$ has not been called for some $i$, then regardless of what $p[i]$ contains, $is\_set(i)$ will return false.

Suppose you are given arrays $p [1......N]$ and $q [1......N]$ both uninitialized, that is, each location may contain an arbitrary value), and a variable count, initiali...

4.9k views

answered Jun 3, 2020

0 votes

2

Rosen Exercise
Let S(x) be the predicate “x is a student,” F(x) the predicate “x is a faculty member,” and A(x, y) the predicate “x has asked y a question,” where the domain consists of all people associated with your school. Express the following sentence using quantifiers: Some student has asked every faculty member a question.

Let S(x) be the predicate “x is a student,” F(x) the predicate“x is a faculty member,” and A(x, y) the predicate“x has asked y a question,” where the domain c...

423 views

answered May 26, 2017

0 votes

3

Kenneth Rosen Edition 7 Exercise 1.2 Question 35 (Page No. 24)
A detective has interviewed four witnesses to a crime. From the stories of the witnesses the detective has concluded that if the butler is telling the truth then so is the cook; the cook and the gardener cannot both ... four persons can the detective determine whether that person is telling the truth or lying ? Explain your reasoning.

A detective has interviewed four witnesses to a crime. From the stories of the witnesses the detective has concluded that if the butler is telling the truth then so is th...

4.1k views

answered May 26, 2017

0 votes

4

Graph theory and Applications Bondy and Murty Exercise Qn 1.9
A k partite graph is one where vertex set can be partitioned into k subsets so that no edge has both end in any one subset. A complete k partite graph is one that is simple and in which each vertex is joined to every other vertex that is not ... on n vertices then | E(G) | <= | E(Tm,n)|, with equality only if G isomorphic to Tm,n

A k partite graph is one where vertex set can be partitioned into k subsets so that no edge has both end in any one subset.A complete k partite graph is one that is simpl...

1.0k views

answered May 9, 2017

2 votes

5

peter linz .theorem 6.3
LET G be any context-free grammar with (lambda) not in L(G).Then there exist an equivalent grammar G' having no (lambda) production. Q.2-> let G be any CFG without (lambda production). Then there exist a CFG G' that does not have any unit production equivalent to G Unable to understand this

LET G be any context-free grammar with (lambda) not in L(G).Then there exist an equivalent grammar G' having no (lambda) production. Q.2- let G be any CFG without (lambda...

1.6k views

answered Mar 31, 2017

0 votes

6

IIT Kanpur Interview Written Test 2016 Question 2
Ms. Dany wants to clean the house having many rooms. She moves from one room to the next which takes 1 time unit. Each room has only one exit door. After some time she is bound to reach a room which she has cleaned already. Let ... be 'k'. Print 't' and 'k'.(do not condiser time taken to clean the room) (Hint : DFS)

Ms. Dany wants to clean the house having many rooms. She moves from one room to the next which takes 1 time unit. Each room has only one exit door. After some time she is...

2.1k views

answered Mar 30, 2017

3 votes

7

IIT Kanpur Interview Written Test 2016 Question 1
Implement a^b mod m where a,b and m can be huge. (Hint : O(log n))

Implement a^b mod m where a,b and m can be huge. (Hint : O(log n))

1.4k views

answered Mar 30, 2017

15 votes

8

GATE CSE 2012 | Question: 8
A process executes the code fork(); fork(); fork(); The total number of child processes created is $3$ $4$ $7$ $8$

A process executes the codefork(); fork(); fork();The total number of child processes created is$3$$4$$7$$8$

13.0k views

answered Nov 27, 2016

41 votes

9

GATE CSE 2001 | Question: 1.16
Let $f(n) = n^2 \log n$ and $g(n) = n(\log n)^{10}$ be two positive functions of $n$. Which of the following statements is correct? $f(n) = O(g(n)) \text{ and } g(n) \neq O(f(n))$ $g(n) = O(f(n)) \text{ and } f(n) \neq O(g(n))$ $f(n) \neq O(g(n)) \text{ and } g(n) \neq O(f(n))$ $f(n) =O(g(n)) \text{ and } g(n) = O(f(n))$

Let $f(n) = n^2 \log n$ and $g(n) = n(\log n)^{10}$ be two positive functions of $n$. Which of the following statements is correct?$f(n) = O(g(n)) \text{ and } g(n) \neq ...

18.9k views

answered Oct 28, 2016

2 votes

10

Dfs
Consider the vertices $V1$ and $V2$ that are simultaneously on the function call stack at some point during the execution of depth -first search from vertex $S$ in a digraph.Which of the following must be true? I. There exist directed path from $s$ to $V_1$ and directed path ... from $V_1$ to $V_2$ then there exist a directed path from $V_2$ to $V_1$ . Which of the above statement is/are true?

Consider the vertices $V1$ and $V2$ that are simultaneously on the function call stack at some point during the execution of depth -first search from vertex $S$ in a dig...

896 views

answered Oct 26, 2016

5 votes

11

#Algorithm # DFS
Let G be a graph with n vertices and m edges. a. True or false: All its DFS forests (for traversals starting at different vertices) will have the same number of trees? b. True or false: All its DFS forests will have the same number of tree edges and the same number of back edges?

Let G be a graph with n vertices and m edges.a. True or false: All its DFS forests (for traversals starting at different vertices) will have the same number of trees?b. T...

2.7k views

answered Oct 26, 2016

1 votes

12

time complexity

475 views

answered Oct 26, 2016

0 votes

13

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.3k views

answered Oct 25, 2016

2 votes

14

Union Find
What is Union Find algorithm? Which type of algo we can search with Union Find algo?

What is Union Find algorithm? Which type of algo we can search with Union Find algo?

1.1k views

answered Oct 25, 2016

100 votes

15

GATE CSE 2016 Set 1 | Question: 38
Consider the weighted undirected graph with $4$ vertices, where the weight of edge $\{i,j\}$ is given by the entry $W_{ij}$ in the matrix $W$ ... integer value of $x$, for which at least one shortest path between some pair of vertices will contain the edge with weight $x$ is ___________.

Consider the weighted undirected graph with $4$ vertices, where the weight of edge $\{i,j\}$ is given by the entry $W_{ij}$ in the matrix $W$. W=$\begin{bmatrix} 0&2 &8 &...

24.0k views

answered Apr 29, 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