Related InterviewSolutions

• Suppose we run Dijkstra’s single source shortest-path algorithm on the following edge weighted directed graph with vertex P as the source. In what order do the nodes get included into the set of vertices for which the shortest path distances are finalized?(A) P, Q, R, S, T, U(B) P, Q, R, U, S, T(C) P, Q, R, U, T, S(D) P, Q, T, R, U, S
• A 4-stage pipeline has the stage delays as 150, 120, 160 and 140 nanoseconds respectively. Registers that are used between the stages have a delay of 5 nanoseconds each. Assuming constant clocking rate, the total time taken to process 1000 data items on this pipeline will be(A) 120.4 microseconds(B) 160.5 microseconds(C) 165.5 microseconds(D) 590.0 microseconds
• Which of the following grammar rules violate the requirements of an operator grammar ? P, Q, R are nonterminals, and r, s, t are terminals.1. P → Q R 2. P → Q s R3. P → ε 4. P → Q t R r (A) 1 only(B) 1 and 3 only(C) 2 and 3 only(D) 3 and 4 only
• Let A = 1111 1010 arid B = 0000 1010 be two 8-bit 2’s complement numbers. Their product in 2’s complement is(A) 1100 0100(B) 1001 1100(C) 1010 0101(D) 1101 0101
• A 4-bit carry lookahead adder, which adds two 4-bit numbers, is designed using AND, OR, NOT, NAND, NOR gates only. Assuming that all the inputs are available in both complemented and uncomplemented forms and the delay of each gate is one time unit, what is the overall propagation delay of the adder? Assume that the carry network has been implemented using two-level AND-OR logic.(A) 4 time units(B) 6 time units(C) 10 time units(D) 12 time units
• Let A, B, C, D be n × n matrices, each with non-­zero determinant. If ABCD = 1, then B-1 is(A) D-1C-1A-1(B) CDA(C) ADC(D) Does not necessarily exist
• The number of different n × n symmetric matrices with each element being either 0 or 1 is: (Note: power(2, x) is same as 2x)(A) power(2, n)(B) power(2, n2)(C) power(2, (n2 + n)/2)(D) power(2, (n2 – n)/2)
• The inclusion of which of the following sets intoS = {{1, 2}, {1, 2, 3}, {1, 3, 5}, (1, 2, 4), (1, 2, 3, 4, 5}}is necessary and sufficient to make S a complete lattice under the partial order defined by set containment ?(A) {1}(B) {1}, {2, 3}(C) {1}, {1, 3}(D) {1}, {1, 3}, (1, 2, 3, 4}, {1, 2, 3, 5)
• An examination paper has 150 multiple-choice questions of one mark each, with each question having four choices. Each incorrect answer fetches -0.25 mark. Suppose 1000 students choose all their answers randomly with uniform probability. The sum total of the expected marks obtained by all these students is:(A) 0(B) 2550(C) 7525(D) 9375
• Two n bit binary strings, S1 and S2, are chosen randomly with uniform probability. The probability that the Hamming distance between these strings (the number of bit positions where the two strings differ) is equal to d is(A) nCd /2n(B) nCd / d(C) d/2n(D) 1/2d