GATE – Sample Questions - CSE 3

1 What does the following algorithm approximate? (Assume m > 1, Î > 0). x = m; y-i; while (x - y > Î ) { x = (x + y) / 2 ; y = m/x ; } print (x) ; Options A) log m B) m 2 C) m 1/2 D) m 1/3 Your Answer ( Not Answered ) Correct Answer C 2 The problems 3-SAT and 2-SAT are Options A) both in P B) both NP-complete C) NP-complete and in P respectively D) undecidable and NP-complete respectively Your Answer ( Not Answered ) Correct Answer C 3 Consider a relation scheme R = (A, B, C, D, E, H) on which the following functional dependencies hold : (A ® B, BC ® D, E ® C, D ® A). What are the candidate keys of R? Options A) AE, BE B) AE, BE, DE C) AEH, BEH, BCH D) AEH, BEH, DEH Your Answer ( Not Answered ) Correct Answer D 4 A circuit outputs a digit in the form of 4 bits. 0 is represented by 0000,1 by 0001,..., 9 by 1001. A combinational circuit is to be designed which takes these 4 bits as input and outputs 1 if the digit ³ 5, and 0 otherwise. If only AND, OR and NOT gates may be used, what is the minimum number of gates required? Options A) 2 B) 3 C) 4 D) 5 Your Answer ( Not Answered ) Correct Answer C 5 If 73 x (in base-x number system) is equal to 54 y (in base-y number system), the possible values of x and y are Options A) 8, 16 B) 10, 12 C) 9, 13 D) 8, 11 Your Answer ( Not Answered ) Correct Answer D 6 In a packet switching network, packets are routed from source to destination along a single path having two intermediate nodes. If the message size is 24 bytes and each packet contains a header of 3 bytes, then the optimum packet size is Options A) 4 B) 6 C) 7 D) 9 Your Answer ( Not Answered ) Correct Answer D 7 Consider the following program fragment for reversing the digits in a given integer to obtain a new integer. Let n = d 1 d 2 ... d m . int n, rev; rev = 0; while (n > 0) { rev = rev * 10 + n % 10 ; n = n/10; } The loop invariant condition at the end of the ith iteration is: Options A) n = d 1 d 2 ... d m-i and rev = d m d m-1 ….d m-i+1 B) n = d m-i+1 ...d m-1 d m (or) rev = d m-i ...d 2 d 1 C) n ¹ rev D) n = d 1 d 2 ...d m (or) rev = d m ...d 2 d 1 Your Answer ( Not Answered ) Correct Answer A 8 Consider the following program segment for a hypothetical CPU having three user registers Rl, R2 and R3. Instruction Operation Instruction