GATE 2003 CS Solution Keys

I have posted these solution keys here because all the books, available in the market, have lots of wrong solutions. Most of the students, like me, find themselves in dilemma and waste a lot of time in finding the correct keys. These solution keys are those which I had corrected while preparing for GATE Computer Science 2012 Exam. You will find most of these solution keys to be correct, except few for which I could not find the correct solution. Still I suggest you that please keep your mind open while using these keys.

GATE 2003 CS Solution Keys

 1.   B
2.   A
3.   D
4.   C
5.   B
6.   B
7.   A
8.   C
9.   A
10.   D
11.   C
12.   A
13.   D
14.   A
15.   D
16.   C
17.   B
18.   C
19.   C
20.   A
21.   D
22.   A
23.   C
24.   A
25.   A
26.   C
27.   D
28.   D
29.   D
30.   A
31.   D
32.   D
33.   C
34.   B
35.   B
36.   A
37.   A
38.   C
39.   B
40.   D
41.   B
42.   B
43.   C
44.   B
45.   C
46.   A
47.   D
48.   B
49.   A
50.   C
51.   C
52.   C
53.   A
54.   A
55.   B
56.   D
57.   D
58.   B
59.   C
60.   C
61.   B
62.   D
63.   B
64.   C
65.   B
66.   B
67.   B
68.   B
69.   B
70.   D
71.   C
72.   B
73.   D
74.   A
75.   D
76.   C
77.   A
78.   D
79.   B
80.   B
81.   C
82.   D
83.   C
84.   B
85.   D
86.   C
87.   D
88.   B
89.   A
90.   B

Comments 13

  2. Post
    Author

  3. For question 59 I believe B is the correct answer.
    t=newtemp() is the only statement that generates a temporary variable.
    E.place=id.place is just an assignment. It doesn’t generate any code.

    Reply

  4. Answer for Q. 12 should be A,
    As per the definition:
    A decision problem C is NP-complete if:

    1. C is in NP, and
    2.Every problem in NP is reducible to C in polynomial time.

    Question does not talk about problem being in NP.

    Reply
    1. Post
      Author

    2. isnt it when a npc problm is polynomial time reducible into sm unkwn problm thn
      that unkwn will be nph problm and when
      there is a polynomial time reduction from unkwn to npc then that unkwn will be np problm
      by these two results we can say now that unknown problm is npc problm.
      so answr should be c.. wt u think???

      Reply
      1. Post
        Author

    3. 1.
      The problem is polynomial time reducible to 3-SAT.
      Means if 3-SAT is solvable in polynomial time then so it the problem.
      Now we know 3-SAT is solvable in non-determistic poloynomial time, hence we can use the answer, and solve the unknow in NDP time.

      2. Every problem is NPC is reducible to each other.

      3. A problem in NP-Hard is not an decision problem, it should be a optimization problem.

      Thus the answer should be C.

      Reply

  5. u can think like that… if a problm is npc thn surly it will be np. and np ,p both can reduce from right to left.i.e. if right side is p or np thn the left one will also p or np resp. so the above problm will also belongs to np and nph which says it is npc

    Reply

  6. some facts abt nXn nultiplier (for question no.11):

    In array multiplier, consider two binary numbers A and B, of n bits each. There are n^2 summands that are produced in parallel by a set of nXn AND gates. total delay due to AND gate is n.

    total delay due to Adder would be (2N+1)

    So in array multiplier worst case delay would be (2n+1).

    Reply

    1. Array multiplier – Refer Computer organization hamacher pg 378. for nxn array total delay is 6*(n-1) – 1. Total delay is in O(n)

      Reply

  7. The point 3 is not correct.
    3. Is not correct.

    An NP-Hard problem can be a decision, search or optimization problem.
    The criteria is it may not be NP, and a NPC problem (like 3-SAT ) is polynomial time reducible to it. So that it can be used to solve any NPC in polynomial time.

    But in our question since the unknow problem is polynomial time reducible to 3-SAT, the problem is in NP.

    Hence it must be NPC.

    Reply

  8. Hey Ankur,

    I had a small doubt regarding Q.No 14

    as per my knowledge the ans should be D(none of the above)coz,

    if you take 010 as input string option A can never generate this string, so option A is eliminated

    if you take 01 as input string option B can never generate this string
    so option B is also eliminated

    option C is eliminated for the obvious reason coz it contains 10 as sub string while the given string can accept epsilon,

    Hence the only option seems correct here is None of the above.

    please correct me if I am wrong…..!!

    Reply

Leave a Reply

Your email address will not be published.