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 2006 CS Solution Keys

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

## Comments 14

Ankur sir, can you please explain ans to qno12 because i am confused with the fact that why cant we implement it with a heap and how do we get the vertices that will give the minimum hop count to reach destination from source??

Author

Compare it with BFS algorithm. It will become similar to that if graph is unweighted.

Here #vertices we will take care of to reach from source to destination as the graph is unweighted. So, how will we get the vertices that will be the shortest path as there can be some vertices during level order traversing that doesn’t fall within the shortest path. eg the entry into the queue ca be ABCDEF when the actual path can be ABDF?? how to get this actual path from ABCDEF??

If possible, can you send me a snap with the solution to my mail??

Author

Entering ABCDEF does not mean that there is a path from A to F. First of all you will insert the source node in the queue. Then you will remove the source node and insert all the adjacent nodes to it. The source node will become the parent of those nodes inserted in the queue. Then You will remove one of the nodes in queue and insert its adjacent nodes and make that node the parent of inserted nodes. Please read the BFS again. You are talking about something else. Try to make the picture in your mind. It seems you are applying DFS algorithm.

Suppose A is adjacent to B and C, D is adjacent to B & also E is adjacent to B. F is adjacent to both D & E. Now tell me to find the shortest path from A to D how to proceed and what to do using BFS(queue)??

Author

It will be like this

A

/

B C

/

D E

/

F

First of all you will insert A in queue. Then you will remove A and insert B and C in queue. A will become parent of B and C. No you will remove B from queue and insert D and E in the queue. Now B will become parent of D and E. So you can traverse the shortest path from A to D by traversing the parent nodes from D to A which will give you DBA. I hope it clears your doubt. If it does not clear, then I again suggest you to go through the book and try to make diagram and practice to apply the algorithm.

A

/ \

B–C

/\

D E

\ /

F

Sorry i forgot to mention B is also adjacent to C. Now there are three paths to F( one is ABDF, other is ACBEF & another is ACBDF). Among them shortest is ABDF, now how we can manage to get that path when C will get inserted before DF and will get removed also before them. Then how do we will be getting this shortest path??

Author

You will never get the sub path “CB”. Read the BFS algorithm carefully again before making any more comments. I hope you are reading some standard book.

Answer to question 7 is D

Could you please explain me the Q.No 29,

why the option C incorrect ???

I am not able to get question 13. how solution is getting 2^n, can you explain.

answer of 39 question should be C,

I need your help to solve 59 question how do you get answer such type of question regarding evaluation of expression. I have not seen such type of problems in my uimaan book but getting confused when i see solution in differenr link because all link have different wrong logics and different answer question.

Hi ,

Could you explain the answer for question no 23 and 38.