This particular post is for all the GATE Computer Science Aspirants[GCSA]. I am currently pursuing my M.Tech in EE[Communications] at IIT Bombay. You might be wondering CS —> EE??? How?? Go through my post GATE IIT Admissions, you’ll know it.
Many people ask me when is the best time to write a GATE CS exam. I naively tell them, once you are prepared ;-). I think six months is a good time period for this exam. I wrote this exam after more than 2 and half years of my job experience. Aspirants who are in their 3rd/4th year of engineering curriculum might think they are at a better position to crack GATE. But, I would totally deny that. The only difference between working professional and engg. student is the amount of time they can allot to studies. The latter are in more advantageous position in this regard. This post can be taken as a set of guidelines for the GCSA. I indeed got some tips from the following documents:
- ” Raj’s Collection” given in the doc “Books-GATE.doc”.
- The “Analysis_CS.jpg” gives a good picture of how the marks are distributed.
- Analysis_CS_2003_08 [The best resource before you start preparing]
The above resources marked 1 and 2 are a good starting point for people who are not sure which books to read. The 3rd and 4th resource are analysis of GATE CS papers over the relevant years. The last two resources lets one also decide which subjects to skip in case one is short of time.The 4th resource, gives subject-wise and topic wise breakup of the distribution of marks over the years. Also, one need not cover the entire topics mentioned in the syllabus. Aspirants can as well leave out some of the subjects in which they are not interested or not proficient. Some of the subjects which are very essential for scoring high are: Discrete Maths, ToC, Digital Logic, Programming and Data Structures, Algorithms.
Solving the previous year papers almost covers the entire scoring area. So, it is always nice to solve GATE papers subject-wise.
I would particularly insist the GCSA to cover the Engg. Mathematics. The reason being, the questions asked in this area are pretty straightforward and hence, quite easy. Most of the aspirants generally ignore this area and that is what becomes the deciding factor for good and great scores. Also try to know quicker ways of solving problems and that would give you more time to solve problems from other area.
I personally feel that the choice of books differs from one person to another and therefore, the list of books suggested can be omitted altogether in case one finds another book being superior/more suitable for their needs. My suggestions[Personal choice] for the references would be:
Engg Maths: Materials from Vani/ACE/Elite is very handy
Discrete Maths: Discrete mathematics & its applications, Kenneth H. Rosen
Graph Theory: Graph Theory, Narsingh Deo
ToC: Introduction to Automata Theory, Languages, and Computation, John E. Hopcroft, Jeffery D. Ullman
Compilers: Introduction to Compiler Design by Aho(first 7 chapters do not miss LALR parser)
Digital Logic: By Givon or Morris Mano. Both are equivalently good.
Computer Organization: By Hamacher
Programming & Data Structures: Book by Mark Allen Weiss is good + Relevant stuffs from http://cslibrary.stanford.edu/ is more than enough. Use wiki for any topic. Wiki is a very reliable source for this area.
Algorithms: Book by Cormen. + Use wiki for any algorithm. Wiki is a very reliable source for this area.
Operating Systems: Book by Galvin, Gagne, silberschatz is good except for Process synchronization. Use internet or Tanenbaum’s book for this particular topic.
Databases: Best book I feel is Navathe. Use Raghu Ramakrishna for Transactions & Concurrency control.
Computer Networks:Computer-Networks by Larry-L-Peterson, Bruce-S-Davie as well as book A top-down approach by Kurose & Ross are equivalently good.
Software Engg: I do not know any good resource as I skipped this subject. But I feel, Pankaj Jalote seems to serve the purpose.
Web/Html: Internet is the best resource for this. w3schools site for html is good.
One important suggestion: Kindly do not use books like Handa, GK etc. they are simply a waste of time. Gathering the concepts and knowing the tricks are the best ammunition for cracking GATE.
I’ll be updating this post with important topics in each subject in short time. For the time being .. I’ll just put the GATE 2010 CS Syllabus and will update it with scoring areas as an inline comment.
CS-Computer Science and Engineering
Mathematical Logic: Propositional Logic; First Order Logic.
Probability: Conditional Probability; Mean, Median, Mode and Standard Deviation; Random Variables; Distributions; uniform, normal, exponential, Poisson, Binomial.
Set Theory & Algebra: Sets; Relations; Functions; Groups; Partial Orders; Lattice; Boolean Algebra.
Combinatorics: Permutations; Combinations; Counting; Summation; generating functions; recurrence relations; asymptotics.
Graph Theory: Connectivity; spanning trees; Cut vertices & edges; covering; matching; independent sets; Colouring; Planarity; Isomorphism.
Linear Algebra: Algebra of matrices, determinants, systems of linear equations, Eigen values and Eigen vectors.
Numerical Methods: LU decomposition for systems of linear equations; numerical solutions of non-linear algebraic equations by Secant, Bisection and Newton-Raphson Methods; Numerical integration by trapezoidal and Simpson’s rules.
Calculus: Limit, Continuity & differentiability, Mean value Theorems, Theorems of integral calculus, evaluation of definite & improper integrals, Partial derivatives, Total derivatives, maxima & minima.
COMPUTER SCIENCE AND ENGINEERING
Theory of Computation: Regular languages and finite automata, Context free languages and Push-down automata, Recursively enumerable sets and Turing machines, Undecidability; NPcompleteness.
Digital Logic: Logic functions, Minimization, Design and synthesis of combinational and sequential circuits; Number representation and computer arithmetic (fixed and floating point).
Computer Organization and Architecture: Machine instructions and addressing modes, ALU and data-path, CPU control design, Memory interface, I/O interface (Interrupt and DMA mode), Instruction pipelining, Cache and main memory, Secondary storage.
Programming and Data Structures: Programming in C; Functions, Recursion, Parameter passing, Scope, Binding; Abstract data types, Arrays, Stacks, Queues, Linked Lists, Trees, Binary search trees, Binary heaps.
Algorithms: Analysis, Asymptotic notation, Notions of space and time complexity, Worst and average case analysis; Design: Greedy approach, Dynamic programming, Divide-and-conquer; Tree and graph traversals, Connected components, Spanning trees, Shortest paths; Hashing, Sorting, Searching.
Compiler Design: Lexical analysis, Parsing, Syntax directed translation, Runtime environments, Intermediate and target code generation, Basics of code optimization.
Operating System: Processes, Threads, Inter-process communication, Concurrency, Synchronization, Deadlock, CPU scheduling, Memory management and virtual memory, File systems, I/O systems, Protection and security.
Databases: ER-model, Relational model (relational algebra, tuple calculus), Database design (integrity constraints, normal forms), Query languages (SQL), File structures (sequential files, indexing, B and B+ trees), Transactions and concurrency control.
Computer Networks: ISO/OSI stack, LAN technologies (Ethernet, Token ring), Flow and error control techniques, Routing algorithms, Congestion control, TCP/UDP and sockets, IP(v4), Application layer protocols (icmp, dns, smtp, pop, ftp, http); Basic concepts of hubs, switches, gateways, and routers.