Recent activity by janakyMurthy / GATE Overflow for GATE CSE

3 answers

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

1 answer

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...

416 views

answered May 26, 2017

2 answers

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

answer selected May 26, 2017

1 answer

4

Subsequence Theorem From Rosen.
There is a theorem Every sequence of n^2 + 1 distinct real numbers contains a subsequence of length n + 1 that is either strictly increasing or strictly decreasing. Proof: Let a1, a2,...,an2+1 be a sequence of n^2 + 1 distinct real numbers.Associate ... ds must be greater than dt , which is a contradiction. My question is how n^2 ordered pair possible for (ik,dk) ??

There is a theoremEvery sequence of n^2 + 1 distinct real numbers contains a subsequence of length n + 1 thatis either strictly increasing or strictly decreasing.Proof: L...

1.5k views

answer selected May 14, 2017

1 answer

5

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

commented May 9, 2017

1 answer

6

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

commented Mar 31, 2017

1 answer

7

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

commented Mar 31, 2017

1 answer

8

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

answer edited Mar 30, 2017

0 answers

9

os, fork()
Consider the following program. #include <stdio.h> #include <unistd.h> int main() { fork(); fork(); fork(); printf("I am process %d and my parent is %d\n", getpid(), getppid()); return 0; } I can understand that at each fork ... of output where id of parent is printed as 1482. But there is no process created with id 1482. Can someone please explain why this happens?

Consider the following program.#include <stdio.h>#include <unistd.h>int main(){ fork(); fork(); fork(); printf("I am process %d and my parent is %d\n", getpid(), getp...

338 views

asked Nov 29, 2016

4 answers

10

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

7 answers

11

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

answered Oct 28, 2016

1 answer

12

GATE Overflow | Programming | Test 1 | Question: 30
Consider the following incomplete C function for reversing a singly linked list. node* reverse(node* trav){ if(trav->next) __________________ else { head -> next = null; head = trav; } return trav; } Here, head is a global pointer pointing to ... = trav; trav->next -> next = trav; trav -> next = trav; trav = reverse(trav->next);

Consider the following incomplete C function for reversing a singly linked list.node* reverse(node* trav){ if(trav->next) __________________ else { head - next = null; he...

1.6k views

commented Oct 28, 2016

1 answer

13

Huffman Encoding

2.5k views

commented Oct 26, 2016

2 answers

14

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...

891 views

answered Oct 26, 2016

1 answer

15

#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

2 answers

16

time complexity

472 views

answered Oct 26, 2016

1 answer

17

ace test series
how many times middle loops execute for bound =1,2,......n.

how many times middle loops execute for bound =1,2,......n.

745 views

commented Oct 26, 2016

1 answer

18

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

answered Oct 25, 2016

2 answers

19

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

answered Oct 25, 2016

9 answers

20

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