Dark Mode

Answers by Himanshu1

4 votes

31

Probability
In a hash table of size 6 currently the locations 0,2,4 and 5 are occupied. The probability of a new record going into location 1 with a hash function resolving collisions by linear probing is (assume uniform hashing) a)2/3 b)1/3 c)1 d) 1/6

answered in Programming in C Dec 18, 2015

722 views

3 votes

32

How does partitioning step acts as a conquering step in quick sort ?
T(n)=aT(n/b) +f(n) here f(n) is the cost of conquering the sub-problems i.e. cost of merging all the sub-problems in order to solve the problem but in case of partioning we are dividng the array around a particular pivot ... the time complexity of quick-sort why do we take O(n) time for f(n) ,how is acting as a conquering step?

answered in Algorithms Dec 15, 2015

470 views

1 vote

33

Patterson Chap 1 Foundtion Q 2
Calculate the total time required to transfer a 1000-KB file in the following cases, assuming an RTT of 50 ms, a packet size of 1 KB data, and an initial 2 × RTT of “handshaking” before data is sent: (a) The ... can send four (23−1), and so on. (A justification for such an exponential increase will be given in Chapter 6.)

answered in Computer Networks Dec 14, 2015

11.7k views

1 vote

34

TIFR CSE 2013 | Part B | Question: 15
Let $G$ be an undirected graph with $n$ vertices. For any subset $S$ of vertices, the set of neighbours of $S$ consists of the union of $S$ and the set of vertices $S'$ that are connected to some vertex in $S$ by an edge of $G$. The graph $G$ has the nice ... $O \left(\sqrt{n}\right)$ but not $O (\log n)$ $O (n)$ but not $O \left(\sqrt{n}\right)$

answered in Algorithms Dec 13, 2015

1.4k views

75 votes

35

GATE CSE 1992 | Question: 02,xiii
For a context free grammar, FOLLOW(A) is the set of terminals that can appear immediately to the right of non-terminal $A$ in some "sentential" form. We define two sets LFOLLOW(A) and RFOLLOW(A) by replacing the word "sentential" ... FOLLOW(A) and RFOLLOW(A) are always the same. All the three sets are identical. All the three sets are different.

answered in Compiler Design Dec 10, 2015

8.0k views

11 votes

36

Combination
For a game in which 2 partners oppose 2 other partners, six men are available. If every possible pair must play against every other pair, the number of games to be played is 9a) 36 (b) 45 (c) 42 (d) 90

answered in Combinatory Dec 9, 2015

2.5k views

59 votes

37

TIFR CSE 2015 | Part B | Question: 4
First, consider the tree on the left. On the right, the nine nodes of the tree have been assigned numbers from the set $\left\{1, 2,\ldots,9\right\}$ so that for every node, the numbers in its left subtree and right subtree lie in disjoint intervals (that is, all numbers in one subtree ... $2^{4}.3^{2}.5.9=6480$ $2^{3}.3.5.9=1080$ $2^{4}=16$ $2^{3}.3^{3}=216$

answered in DS Dec 8, 2015

4.1k views

1 vote

38

toc
for DCFL there exists LL(k) or not?

answered in Theory of Computation Dec 5, 2015

1.1k views

1 vote

39

which of the following statements is correct regarding Regular language?
1.Every Ragular Language have an equivalent LR(0)grammer. 2. Every DCFL have an equivalent LR(0) grammer

answered in Theory of Computation Dec 5, 2015

1.1k views

10 votes

40

In how many ways can the entrepreneur assign 5 different tasks to 3 employees if each should get atleast 1 task ?

answered in Combinatory Dec 3, 2015

5.9k views

0 votes

41

GATE CSE 2003 | Question: 61
In a permutation \(a_1 ... a_n\), of n distinct integers, an inversion is a pair \((a_i, a_j)\) such that \(i < j\) and \(a_i > a_j\). If all permutations are equally likely, what is the expected number of inversions in a randomly chosen permutation of \(1. . . n\)? \(\frac{n(n-1)}{2}\) \(\frac{n(n-1)}{4}\) \(\frac{n(n+1)}{4}\) \(2n[\log_2n]\)

answered in Algorithms Dec 2, 2015

20.3k views

2 votes

42

answered in Digital Logic Dec 1, 2015

610 views

0 votes

43

longest common subsequence
For X= BDCABA and Y=ABCBDAB find length of lcs and no of such lcs..(solve it using table method)

answered in Algorithms Dec 1, 2015

9.2k views

2 votes

44

associative cache
Consider a 32 bit processor that has an on chip 16Kbyte 4 way set associative cache. assume that cache has a size of four 32 bit words. the set no in the cache to which the word from memory location FFFAE8FA is mapped_________

answered in CO and Architecture Nov 30, 2015

751 views

0 votes

45

Hashing function
Consider a hashing function that resolves collision by quadratic probing. Assume the address space is indexed from 1 to 8.If a collision occurs at position 4, then the location which will never be probed is..

answered in Algorithms Nov 30, 2015

783 views

48 votes

46

TIFR CSE 2014 | Part B | Question: 9
Given a set of $n$ distinct numbers, we would like to determine the smallest three numbers in this set using comparisons. Which of the following statements is TRUE? These three elements can be determined using $O\left(\log^{2}n\right)$ ... $O(n)$ comparisons. None of the above.

answered in Algorithms Nov 29, 2015

9.8k views

3 votes

47

combinatory
How many ways are there for a horse race with 4 horses to finish if ties are possible?(any number of horses may tie)

answered in Combinatory Nov 27, 2015

978 views

2 votes

48

probability
Explain this question . what they mean ? A six faced die is so biased that, when thrown, it is twice as likely to show an even number than an odd number. if it is thrown twice, what is the probability that sum of two numbers thrown is odd ans = 4/9

answered in Probability Nov 27, 2015

671 views

64 votes

49

TIFR CSE 2014 | Part B | Question: 19
Consider the following tree with $13$ nodes. Suppose the nodes of the tree are randomly assigned distinct labels from $\left\{1, 2,\ldots,13\right\}$, each permutation being equally likely. What is the probability that the labels form a min-heap (i.e., every node receives the ... $\frac{2}{13}$ $\frac{1}{2^{13}}$

answered in DS Nov 24, 2015

5.6k views

1 vote

50

total probability
A bag contains 3 balls. Given that one of the balls is red and the other two balls can be either red or non-red..what is the probability of picking up a red ball?

answered in Quantitative Aptitude Nov 23, 2015

658 views

9 votes

51

TIFR CSE 2013 | Part A | Question: 10
Three men and three rakhsasas arrive together at a ferry crossing to find a boat with an oar, but no boatman. The boat can carry one or at the most two persons, for example, one man and one rakhsasas, and each man or rakhsasas can row. But if at any ... any mishap, what is the minimum number of times that the boat must cross the river? $7$ $9$ $11$ $13$ $15$

answered in Analytical Aptitude Nov 21, 2015

1.6k views

1 vote

52

TIFR CSE 2013 | Part A | Question: 20
Consider a well functioning clock where the hour, minute and the seconds needles are exactly at zero. How much time later will the minutes needle be exactly one minute ahead ($1/60$ th of the circumference) of the hours needle and the seconds needle again ... of $1/60$ th of the circumference. $144$ minutes $66$ minutes $96$ minutes $72$ minutes $132$ minutes

answered in Quantitative Aptitude Nov 21, 2015

1.7k views

7 votes

53

TIFR CSE 2014 | Part A | Question: 2
A body at a temperature of $30$ Celsius is immersed into a heat bath at $0$ Celsius at time $t = 0$. The body starts cooling at a rate proportional to the temperature difference. Assuming that the heat bath does not change in temperature throughout the process, calculate the ... $\dfrac{\log 29}{\log 25}$ $\large e^{5}$ $1 + \log_{6} 5$ None of the above

answered in Quantitative Aptitude Nov 21, 2015

840 views

93 votes

54

GATE IT 2007 | Question: 25
What is the largest integer $m$ such that every simple connected graph with $n$ vertices and $n$ edges contains at least $m$ different spanning trees ? $1$ $2$ $3$ $n$

answered in Graph Theory Nov 18, 2015

21.4k views

23 votes

55

GATE IT 2007 | Question: 80
Let $P_{1},P_{2},\ldots,P_{n}$ be $n$ points in the $xy-$plane such that no three of them are collinear. For every pair of points $P_{i}$ and $P_{j}$, let $L_{ij}$ be the line passing through them. Let $L_{ab}$ be the line ... or the smallest $y$-coordinate among all the points The difference between $x$-coordinates $P_{a}$ and $P_{b}$ is minimum None of the above

answered in Linear Algebra Nov 18, 2015

5.1k views

5 votes

56

GATE IT 2006 | Question: 11
If all the edge weights of an undirected graph are positive, then any subset of edges that connects all the vertices and has minimum total weight is a Hamiltonian cycle grid hypercube tree

answered in Graph Theory Nov 18, 2015

8.7k views

37 votes

57

GATE IT 2004 | Question: 36
If matrix $X = \begin{bmatrix} a & 1 \\ -a^2+a-1 & 1-a \end{bmatrix}$ and $X^2 - X + I = O$ ($I$ is the identity matrix and $O$ is the zero matrix), then the inverse of $X$ is $\begin{bmatrix} 1-a &-1 \\ a^2& a \end{bmatrix}$ ... $\begin{bmatrix} -a &1 \\ -a^2+a-1& 1-a \end{bmatrix}$ $\begin{bmatrix} a^2-a+1 &a \\ 1& 1-a \end{bmatrix}$

answered in Linear Algebra Nov 16, 2015

4.2k views

40 votes

58

GATE IT 2004 | Question: 15
Let $x$ be an integer which can take a value of $0$ or $1$. The statement if (x == 0) x = 1; else x = 0; is equivalent to which one of the following ? $x = 1 + x;$ $x = 1 - x;$ $x = x - 1;$ $x = 1\% x;$

answered in Programming in C Nov 16, 2015

9.6k views

14 votes

59

GATE CSE 1996 | Question: 17
Let $G$ be the directed, weighted graph shown in below figure We are interested in the shortest paths from $A$. Output the sequence of vertices identified by the Dijkstra's algorithm for single source shortest path when the algorithm is started at node $A$ Write down ... vertices in the shortest path from $A$ to $E$ What is the cost of the shortest path from $A$ to $E$?

answered in Algorithms Nov 12, 2015

7.5k views

25 votes

60

TIFR CSE 2013 | Part B | Question: 8
Which one of the following languages over the alphabet ${0, 1}$ is regular? The language of balanced parentheses where $0, 1$ are thought of as $(,)$ respectively. The language of palindromes, i.e. bit strings $x$ that read the same from left to right as well as right to ... $(c)$ above. $\left \{ 0^{m} 1^{n} | 1 \leq m \leq n\right \}$

answered in Theory of Computation Nov 7, 2015

4.1k views

Page: