:: GATE GUIDE BY AIR 98 ::

ANALYSIS OF PAPER 

First of all, go through all previous papers. Especially, the papers of the year when organizing institute is same as that of GATE’09.

GATE’08 was organized by IISc. The previous years when IISc was organizing institute were year 2002, 1996, and 1990. When I solved these papers, I found out that there are some concepts on which IISc was focusing more. E.g. In each of these papers there was question on:
B/B+ tree,
Newton-Raphson Method,
More stress on CO and Digital,
Mathematics is more inclined towards Calculus than Discrete Maths
On the contrary problems on Probability, Networks and Compilers were not much difficult…..

If u solve GATE’08 paper u ll find the same thing here also….

So we can say that GATE paper is much predictive. so first task to do is go through all the papers (I think the organizing institute this time may be Madras and prev years when madras was organizing institute were 1991, 1997, 2003…) and find out the similarities….stress on them.
I m not saying to skip all other topics…but practically its really difficult (not impossible) to focus on all the subjects….so, I just want to say, if u want to skip some topics don’t skip the topics stressed by the organizing institute. Also don’t underestimate the remaining topics …. here comes my first mistake…I under-estimate]Probability and solved very simple problem wrongly ….result was -2.5 marks .

But warning is if u skip some topics u must be perfect in all the remaining topics. And the definition of perfect, here, is there must be only one person to solve particular problem on that topic before u….the paper setter!!!…..no one else 

Now next point is,
Every GATE paper contains three kinds of questions:
1. problems on tricky concepts
if u know the concept, ur done…
2. Difficult problems
U ve to put ur brains to solve these problems…
3. Practically unsolvable problems
U may find totally unknown and new concepts which couldn’t be solved in 3hrs time this typically includes problems on CO and probability.

To crack the GATE u ve to solve correctly ALL the problems of first kind….for 2nd kind, the more the problem u solve, lesser the rank u ll get!!!

Now while solving the paper, I solved it in 3 passes….

1. Solve all the problems that u can solve undoubtfully…means answer only when ur200% sure about the ans ….for this pass I ve given 2hrs during the paper which is quite sufficient 
2. Check all the problems…Remember while checking have thorough checking….check whether u ve marked correct option…check question-to-ans correspondence is correct…many times it happens that we solve Q.30…leave Q31 blank and after solving Q32 we mark option in front of Q31….here comes my another mistake…I haven’t checked three of questions for which I thought no checking is necessary…but I lost 7.5 marks….this pass may take 15-20 min…
3. after careful checking only turn towards problems for which u are doubt full…try to rethink on these problems…u may solve 3-4 of them…

I ld like to explain u how much imp ur hit ratio….in GATE’08 I attempted 54 questions…out of which 14 are of 1 marks and 40 are of marks…out of 14, 11 are correct and 3 came to be wrong…and out of 40…28 came to be correct and 12 came to be wrong…so my score, I think is round about 60/150….

Now if I ld ve attempted only 11 one marked questions and 28 2 marked questions….for which I was 200% sure…then my score ld ve been 67/150….means surely I ld ve got rank <50

Continuing the discussion about marks…
I think, for easy paper(like GATE’07) 75/150 = IIT
For difficult paper(like GATE’08) …u can see even 60/150 is done!!!

So in general attempt 50-60 questions with hit ratio >90% and ur through!!!

Well,
Now I ll come to preparation part of the GATE

BOOKS and SUBJECT ANALYSIS

Discrete Mathematics 
MOST IMP subject as far as CS is concerned

First order logic:
prepare it from Trembley-Manohar and solve exercise from Discrete Mathematics and Application by Kenneth Rosen. Easy topic. Once concept is clear marks are urs….
Important rules of thumb are given in Kenneth Rosen

Probability and Combinatorics:
I skipped this part. But Kenneth Rosen again has variety of problems on this topic.

Set Theory:
Trembley-Manohar
Boolean algebra,Groups, Lattice, Relations:
Kenneth Rosen has good discussion on Relations and Lattice.
Book by K.D.Joshi on Discrete Maths has good derivations regarding enumerating the relations…go through it, it ll surely help to build up the ideas…
For Boolean Algebra and Group Theory again book by Trembley-Manoher is good, but for exercises I used book by Ross(I don’t remember the full name of author…sorry for that)
Trembley-Manoher includes good theorems in Group Theory…

Linear Algebra, Calculus and Numerical Methods:
For these subjects I used the course books by local authors which we used for semester exams…
There are some quickie methods to find out inverse of matrix, eigen values and eigen vectors, determinant…understand those from Profs in ur college

Recurrence Relations:
Kenneth Rosen includes some rules of thumb for Particular Solutions of Recurrence Relations…once u got them solving problems on RR is work of few secods…
Particularly for Recurrence Relations, try to find ans by eliminating wrong options…i.e. if u know f(1)=a and f(0)=b…try to put 1 and 0 in options and see where u get correct ans….believe me in most of cases u ll get quick and correct ans by this way….

Graph Theory:
MOST IMP topic for CS
Try to go through all possible books and material for Graph Theory.
Note down the general formulae/theorems given in books…read them frequently…
Kenneth Rosen includes good discussion in most of the concepts of GT.
Graph Theory by Douglas West is also gr8 book.

Theory of Computation 

Book by
John C. Martin
This is gr8 for Regular Languages, Finite Automata…theory and problems
Cohen
This includes variety of problems on every other concept of TOC…theory is also very perfect (as good as spoon feeding) …especially for pumping lemma

Peter Linz
Again good theory …easy to understand….problems on Turing Machine are tricky…

Michel Sipser
This book is good especially for Un-decidability, Recursive and RE languages, NP-completeness
For NP-completeness book on Algorithms by Sahani is also good

I suggest u to read these books in following order
1. Read concepts from Cohen….u also can refer Peter Linz…solve exercises
2. Solve exercise from John Martin
3. Read Michel Sipser for advanced concepts

statutory warning: TOC book by Ullman is injurious to brain …but do read this book once…this contains, exclusively, concepts of Homomorphism, HALF of LANGUAGE etc…

Digital Logic:
Morris Mano…morris mano…morris mano!!!!!!!!
There are ppts on the department website of IIT-D regardin this course…which contains good discussion on some concepts like Fault Detection and Hazards in Circuits…
Walkerly is also good book…
There is also a book Fundamentals of Digital Circuits by A. Anand Kumar which includes thorough discussion on Number System(don’t under-estimate this point…there are many tricky concepts in it!!!)

Computer Organization and Architecture:

Book by Morris Mano(not the same as Digital…there is separate book for CO)…it contains good theory and problems for Addressing Modes, DMA and IO…refer latest edition coz previous editions doesn’t include concepts of Register Window….so I could not attempt problem on it 
Book by J. P. Hays contains good discussion on Micro-programming and Hard-Wired Design, also it contains good formulae for Pipelining
J. P. Hays also contain thorough discussion on Floating Point number formats….
Good and exclusive formulae for Secondary Storage…

Book by Zaky
It has good theory for Pipelining
Also thorough discussion in Cache memories…. Don’t skip any word and any problem written about 

cache in this book 

Algorithms 

Read each and every word written in book by Cormen…solve every other excersies….this is enough…solution manual is available over the internet…search on esnips.com

Also there is one book, I found on flazx.com, named “Problems on Algorithms”…this book contains only problems …no theory…..but good book
Book by Sahani is also good

IMP subject for CS
Get perfection in:
Master Theorem and Asymptotic notations

Data Structure and Programming
For programming u must be great in concepts of Pointers and Recursion. For tricky problems related with programming visit department websites of various foreign universities and solve the assignments given there…

For data structure
Book by Alan Weiss is great and sufficient for theory….
For problems on Data Structure…nothing is sufficient….solve as many as u can…
To understand various operations on various Trees and Heaps there are many Java Applets available over the internet…they will demonstrate it…

Compiler Design
Ullman…nothing else!!!
For lexical analysis some problems are asked on C program like: a C program is given and we are asked to find out number of tokens generated…so to understand tokens in C…book by Denis Ritchie is good Read each and every word given on Parsers in Ullman…there are many tricks given to find out whether grammar is LL or LR or CLR or LALR
statutory warning: this book requires too much patience to understand
Many students skip this subject but Ullman is best for
Parsers, S-attributed and L-attributed SDT, Scopes of variables, Passing of Parameters, Code Optimization (defn only)
Prepare at least these points

Operating Systems 

Book by Galvin is very good for concepts
Modern Operating System by Andrew Tanenbaum is the best book for OS. It contains great number of problems. Also includes some of theory that is not included in Galvin’s book.
Operating Systems by Stallings also contains tricky problems…soln manual is also available on esnips.com
I also suggest Schaum’s Series (author: J. Archer Harris) book on operating systems for problems. It is a very good compilation of problems from Galvin, Tanenbaum and Stallings. Also soln are given.

While preparing prepare operating system along with CO. it will be helpful for Memory Management.

statutory warning: while solving problems on OS keep ur head cooool and….recheck them thrice…better not to attempt problems on OS in doubtful situation

Database 

For physical database organization (theory) and SQL, RA, TRC
Book by Raghuramkrishnan…soln manual is available

For transaction management and Normalization

Book by Korth … soln manual is available

For ER diagrams and problems on physical database organization
Book by Navathe….available on ebookee.com

Once u finish reading topics in Korth and Raghuramkrishnan and ur concepts are clear, then onwards I suggest u to read and stick up with Navathe coz it contains lot of techniques and algorithms not given any where else

Computer Networks 

For application layer protocols
“Computer Networking – A top down approach” by Kurose and Ross available on flazx.com
“TCP/IP” by Forouzan

For Frame Formats, TCP and IP Header formats
“TCP/IP” by Forouzan

Data Link Layer, Network Layer, Transport Layer
“Computer Networks” by Tanenbaum
Go through all the exercises given in the book…soln manual is available on esnips.com

Some Suggestions for Preparation/Study 

1. Strictly use Reference books, don’t rely on any class notes.
2. In first phase of ur study (in month of May-June) go through all GATE papers. Solve them by ur own. Once problem is solved try to find out similar problems from refernce books and solve them. This will fix up the concepts well.
3. Use department websites of various universities to get latest assignments.
4. plan ur schedule in such a way that u ll be able to finish up whole syllabus in month of Dec. from jan onwards try to solve papers.
5. keep ur feb first week for revision only…don’t read any new concepts ( I tried to do calculus in month of Feb…i couldn’t even solve simple problem on limits…total time-waste)

hope this was not too boring …and will be helpful to all of u….
if u have any doubts…feel free to ask me anytime…