Saturday, February 18, 2012

GATE 2012 CS solution

I had appeared in GATE 2008 and 2009. After that I had not been interested much in GATE. However this time (GATE 2012) a close friend of mine appeared for the same, which got me interested again. Here is a solution set to the GATE 2012 Computer Science paper. I have solved question from Algorithms, Automata, C programming, Probability ... in short, the topics that I enjoyed enough to remember them after 2 years.

As I mentioned earlier, I have not appeared in for the examination. I got the question GATE 2012 CS and IT question set C from a fellow netizen. Please download the paper first as I will be using that as the reference for objective type answers.

2 years earlier I had posted solutions to GATE 2009 CS question paper. Comments and suggestions from that post made me realize the importance of explaining every answer. Feel free to ask questions if you need further clarifications.

GATE 2012 Computer Science and IT solutions to question set C
  1. b
  2. -
  3. -
  4. b
    • Draw the sine graph for the interval. Only one minima at 3*pi/2 where sin(x) = -1
  5. c
    • fork() will spawn off a new child process every call. Three calls to fork() results in 8 processes, out of which one is original, other 7 are children.
  6. b
  7. a
    • Obviously. Look at f(X,Y) and compare it with X
  8. c
    • Balanced binary search trees require log (number of elements) time to search
    • log (n*2^n) = log (n) + log(2^n) = O(n)
  9. -
  10. c
    • Standard switch case behaviour called "fall through", when the break statement is not there
  11. c
    • Look into any DB book, I studied Navathe.
  12. -
  13. c
    • Do the checking manually
  14. c or d
    • 1 is false, 3 and 4 are true
    • not sue about 2
  15. -
  16. -
  17. c
    • follows from definition of CDF
  18. -
  19. d
    • 4 bit multiplier requires 2x4 = 8 bit input, i.e. 2^8 set of inputs
    • multiplication of two 4-bit numbers will result in at most 8-bit result, so 8 bits for every multiplication
    • 2^8 * 8 = 2^11 bits = 2 Kbits
  20. c
    • Average case is at lease as good as worst case
      • A(n) better than W(n) :: Quicksort
      • A(n) same as W(n) :: Heapsort
  21. c
    • Draw it and find out. They key thing is "any embedding of G on the plane"
  22. d
    • T(n-1) for moving n-1 disk to aux from source
    • 1 for moving the n-th disk to destination
    • T(n-1) for moving n-1 disk back to source from aux
  23. b
  24. -
  25. c
  26. -
  27. --
  28. -
  29. b
    • examine the cases:
      • P(6 in first throw) = 1/6
      • P(1 in first throw followed by 5 or 6 in second throw) = (1/6)*(2/6)
      • P(2 in first throw followed by 4, 5 or 6 in second throw) = (1/6)*(3/6)
      • P(3 in first throw followed by 3,4, 5 or 6 in second throw) = (1/6)*(4/6)
    •  summing up = (1/6)*(1+2/6+3/6+4/6) = 5/12
  30. -
  31. -
  32. b
    • b'd' -- group the 4 corners
    • b'c' -- group the a'b' columns to 2 cells with the top 2 cells in ab' column
  33. a
    • MST algorithm does not depend on the value of the weights, it depends only on the relative ordering of the edge weights.
    • Ranking remains unchanged as all the weights are >= 1
  34. b
    • I did it by hand, don't know if there is a shortcut
  35. b
    • Observe the graphs
  36. -
  37. d
    • observe that q is a dead state, so anything beginning with 000 should go to q -- A and B gets eliminated by this logic
    • after 10 if there is a 0 the state should move to 00 state, so D is correct
  38. a
    • look into any Data Structure book
  39. -
  40. -
  41. -
  42. -
  43. -
  44. d
    • Dijkstra's algorithm probes the best solution so far
    • Thanks to Shivam for pointing this out
  45. b
    • merge-sort takes O(n log n) comparisons
    • here to compare two strings you need O(n) time, so O(n^2 log n)
  46. c
    • represent a cycle by a permutation of 4 labeled vertices
    • cycles are identical if one is a rotation of another
    • same cycle of length 4 can have 4 different representations each starting with a unique letter
    • (6 P 4) / 4 = 90
  47. -
  48. -
  49. -
  50. c
    • line 2 has a static variable, which retains the old value when he function is called again
  51. d
    • "auto int" is same as normal "int"
    • "register int" is same as normal "int" as far as value retention is considered
  52. -
  53. -
  54. -
  55. -
  56. -
  57. a
  58. -
  59. a
    • maxima-minima problem
    • maximize the profit where, profit = 50q-5q^2
  60. b
  61. b
    • Given:
      • P(X) = 0.6
      • P(Y) = 0.4
      • P(R | X) = 0.96
      • P(R | Y) = 0.72
    • P(R) = P(X) * P(R | X) + P(Y) * P(R | Y) = 0.864
    • Applying Bayes Rule:
      • P(Y | R) = [ P(R | Y) * P(Y) ] / P(R) = 0.333
  62. c
    •  follows from fundamental definitions of mean and standard deviation
  63. -
  64. -
  65. b
    •  another maxima-minima problem and the function is already given, just maximize y

Please leave a comment if you were helped by my effort. Feel free to ask questions if you need further clarifications or have found some error in my solution.

7 comments:

  1. your dijkstra sol is wrong....ans is d sacet

    ReplyDelete
    Replies
    1. Thanks for letting me know. I have corrected the same.

      Delete
  2. A typo. Q.19. The answer, 2Kbits, is option D and not C

    ReplyDelete
    Replies
    1. Thanks for pointing out the typo. Corrected the same.

      Delete
  3. WHy nobody is saying the answer to dijksra question is b in set c? i have read from a made easy book that dijkstra works like kruskal...it picks up smallest weighted edges and finds shortest path.....so according to it answer shuld be b not a or d....please correct me if i m wrong...coz nobody has cleared my doubt.

    ReplyDelete
    Replies
    1. Dijkstra's algorithm explores the shortest path it has found so far. It does NOT take the smallest path always. Try to read up the algorithm from a trusted source like CLRS with the proof. The proof will clear up your doubts.

      Finally a small word of advice; please try to avoid "made easy" books for basic algorithms like Dijkstra and read standard textbooks instead.

      Delete
  4. your solution to ques. 11 i.e. c is incorrect as it is not necessary to have group by clause for running query with having clause either group by or aggregation is necessary.
    and secondly not all attributes are necessary to be in select clause that are in group by clause , any other attr. may be there provided it is in aggregation func.
    I have drawn these conclusions by running the queries ...

    ReplyDelete

I'd love to hear from you !