Let A[1…n] be an array of n distinct numbers. If i < j and A[i] > A[j], then the pair (i, j) is called an inversion of A. What is the expected number of inversions in any permutation on n elements ?(A) n(n-1)/2(B) n(n-1)/4(C) n(n+1)/4(D) 2n[logn]

Let A[1…n] be an array of n distinct numbers. If i < j and A[i] > A[

1.	Let A[1…n] be an array of n distinct numbers. If i < j and A[i] > A[j], then the pair (i, j) is called an inversion of A. What is the expected number of inversions in any permutation on n elements ?(A) n(n-1)/2(B) n(n-1)/4(C) n(n+1)/4(D) 2n[logn]
Answer»

Discussion

No Comment Found

Related InterviewSolutions

Consider the following statements:(a) Revised simplex method requires lesser computations than the simplex method.(b) Revised simplex method automatically generates the inverse of the current basis matrix.(c) Less number of entries are needed in each table of revised simplex method than usual simplex method.Which of these statements are correct?(A) (a) and (b) only(B) (a) and (c) only(C) (b) and (c) only(D) (a), (b) and (c)
The region of feasible solution of a linear programming problem has a _____ property in geometry, provided the feasible solution of the problem exists.(A) concavity(B) convexity(C) quadratic(D) polyhedron
Let L = {0n1n|n ≥ 0} be a context free language.Which of the following is correct ?(A) L` is context free and Lk is not context free for any k ≥ 1.(B) L` is not context free and Lk is not context free for any k ≥ 1.(C) Both L` and Lk is for any k ≥ 1 are context free.(D) Both L` and Lk is for any k ≥ 1 are not context free.
Given a Turing MachineM = ({q0, q1, q2, q3}, {a, b}, {a, b, B}, δ, B, {q3})Where δ is a transition function defined asδ(q0, a) = (q1, a, R)δ(q1, b) = (q2, b, R)δ(q2, a) = (q2, a, R)δ(q3, b) = (q3, b, R)The language L(M) accepted by the Turing Machine is given as:(A) aa*b(B) abab(C) aba*b(D) aba*
Consider a source with symbols A, B, C, D with probabilities 1/2, 1/4, 1/8, 1/8 respectively. What is the average number of bits per symbol for the Huffman code generated from above information ?(A) 2 bits per symbol(B) 1.75 bits per symbol(C) 1.50 bits per symbol(D) 1.25 bits per symbol
Which of the following is used for the boundary representation of an image object?(A) Quad Tree(B) Projections(C) Run length coding(D) Chain codes
A software program that infers and manipulates existing knowledge in order to generate new knowledge is known as(A) Data dictionary(B) Reference mechanism(C) Inference engine(D) Control strategy
Compute the value of adding the following two fuzzy integers :A = {(0.3, 1), (0.6, 2), (1, 3), (0.7, 4), (0.2, 5)}B = {(0.5, 11), (1, 12), (0.5, 13)}Where fuzzy addition is defined asμA+B (z) = max x + y = z(min (μA(x), μB(x)))Then, f (A + B) is equal to(A) {(0.5, 12), (0.6, 13), (1, 14), (0.7, 15), (0.7, 16), (1, 17), (1, 18)}(B) {(0.5, 12), (0.6, 13), (1, 14), (1, 15), (1, 16), (1, 17), (1, 18)}(C) {(0.3, 12), (0.5, 13), (0.5, 14), (1, 15), (0.7, 16), (0.5, 17), (0.2, 18)}(D) {(0.3, 12), (0.5, 13), (0.6, 14), (1, 15), (0.7, 16), (0.5, 17), (0.2, 18)}
Let R and S be two fuzzy relations defined as:andThen, the resulting relation, T, which relates elements of universe X to elements of universe Z using max-min composition is given by(A) (1)(B) (2)(C) (3)(D) (4)
A perceptron has input weights W1 = – 3.9 and W2 = 1.1 with threshold value T = 0.3.What output does it give for the input x1 = 1.3 and x2 = 2.2 ?(A) – 2.65(B) – 2.30(C) 0(D) 1

Let A[1…n] be an array of n distinct numbers. If i &lt; j and A[i] &gt; A[j], then the pair (i, j) is called an inversion of A. What is the expected number of inversions in any permutation on n elements ?(A) n(n-1)/2(B) n(n-1)/4(C) n(n+1)/4(D) 2n[logn]

Discussion

No Comment Found

Related InterviewSolutions

Reply to Comment

Let A[1…n] be an array of n distinct numbers. If i < j and A[i] > A[j], then the pair (i, j) is called an inversion of A. What is the expected number of inversions in any permutation on n elements ?(A) n(n-1)/2(B) n(n-1)/4(C) n(n+1)/4(D) 2n[logn]