The GATE FAQ (CSE)

1. Can I rely on this author, how is this person, and why did the write the FAQ?
2. Hey the details in this FAQ are wrong, I followed this FAQ and now, I am in Antarctica!!!
3. I need to contact the author, how do I do it?
4. What is the official gate website?
5. Can you give me the links to the IIT and IISc websites?
6. Are there any important dates w.r.t GATE?
7. Everybody talks about the "conducting institute", what does this mean?
8. Where can I get the GATE brochure?
9. What books do I refer for GATE CSE?
10. Apart from the books do I need to refer the articles published in the Internet?
11. Is there any official document that I can refer to, w.r.t GATE?
12. Do I require to buy the GATE material from Brilliants, Elite, etc, If I do, then which is the best?
13. I need the syllabus for GATE Computer Science 2004
14. I don't have any idea about the relation between marks, percentile, and rank
15. Could someone tell the list of gate-specific books
16. List of books for Computer Hardware
17. List of books for Discrete Mathematics
18. List of books for Theory of Computation (Formal Languages and Automata Theory)
19. List of books for Theory of Computation (Analysis of Algorithms and Computational Complexity)
20. List of books for Data Structures and Programming and Algorithms
21. List of books for Compiler Design
22. List of books for Database Systems
23. List of books for Computer Networks
24. List of books for Operating Systems
25. Which is the best IIT? What do I choose first?
26. Any information about BITS pilani
27. I need to know who contributed to this document

J Venkata Subramani (Venkat)

<thegatefaq@yahoo.com>

Last updated: 21 August 2003 (15:30 hrs)

This FAQ is orginally located at http://oocities.com/thegatefaq/thegatefaq.html

1.

Can I rely on this author, how is this person, and why did the write the FAQ?

The author is totally unreliable(and his English is bad too...), he is also trying to get through GATE like you people, and he wrote this FAQ cause he was really disappointed by the way those yahoo groups work.... every new aspirant asks the same set of questions all over again (nobody can patiently answer those questions on a repeated basis), this FAQ is one step to reduce those questions.

2.

Hey the details in this FAQ are wrong, I followed this FAQ and now, I am in Antarctica!!!

Cool, I didn't know my FAQ could do that..., well this FAQ was written to give people some insight about GATE, these are not specification to be followed exactly..., grow up dude!!!, I'll call this my disclaimer.

3.

I need to contact the author, how do I do it?

Simple, send him a mail at thegatefaq@yahoo.com, he usually sleeps all time, but when he wakes up he might read your mail.

Author: Hey party ppl any mistakes, any additions, any suggestions, any comments, any (*&@(*&#*#!^), or any other kind of information to be passed on, please feel free to send in your mail, please include any of the following words in the mail subject - QUESTION:, ANSWER:, PRAISE:, COMMENT:, SUGGESTION:, MISTAKE:, INFO:, INFORMATION:, MISC: - followed by the actual subject. If you are sending gate related information to me make sure that you include your name and place in it, I would like to add it in the contributors section...

Examples: Subject: "SUGGESTION: Stop writing this FAQ!!!", Subject: "PRAISE: Your English sucks..."

4.

What is the official gate website?

Actually there is no official website for GATE, each year one of the IITs or IISc conducts the GATE so they host the details on their website, other institutes usually mirror the contents. But general gate information or the previous year's gate brochure is available at all times in most IITs or IISc websites. (See below for the URLs)

5.

Can you give me the links to the IIT and IISc websites?

Please search for the gate links from the main pages listed below...

Table 1. IITs and IISc Website

IISc, Bangalorehttp://www.iisc.ernet.in
IIT, Bombayhttp://www.iitb.ac.in
IIT, Delhihttp://www.iitd.ac.in
IIT, Guwahatihttp://www.iitg.ernet.in
IIT, Kanpurhttp://www.iitk.ac.in
IIT, Kharagpurhttp://www.iitkgp.ernet.in
IIT, Madrashttp://www.iitm.ac.in
IIT, Roorkeehttp://www.iitr.ac.in
6.

Are there any important dates w.r.t GATE?

Yes, there are many, it is recommended to visit the the conducting institute's website and get the details

Most times the dates follow the some standard rules..., like GATE is conducted every second Sunday of February.

I shall specify the important dates as listed on the GATE 2003 brochure, this should give you some idea

Table 2. GATE 2004 Information - (http://www.iitkgp.ernet.in/acadsnew/gate/home.php) as on Aug 14 2003

Receipt of request at GATE Office for Information Brochure and Application Form by postOct 25,2003(Saturday)
Sale at Bank Counters / On-line submissionOct 30, 2003 ( Thursday)
Sale at IIT/IISc./GATE Office CountersNov 03, 2003 ( Monday)
Last date for receiving completed Application Form at GATE OfficesNov. 3, 2003(Monday)
Dispatch of Admit Cards by the respective InstitutesJan 13 , 2004 (Tuesday)
Date of GATE 2004 ExaminationFeb 08, 2004 (Sunday)
Announcement of resultsMar 15, 2004 (Monday)

THE EXAMINATION DATE WILL NOT BE CHANGED UNDER ANY CIRCUMSTANCES DATE: FEBRUARY 08, 2004 (SUNDAY) TIME: 9.30 A.M. to 12.30 P.M.

7.

Everybody talks about the "conducting institute", what does this mean?

Every year one of the the IITs or IISc conduct GATE, this institute takes care about all GATE related functions from setting up the paper to renting examination halls, this institute is called the "conducting institute" for that year.

Table 3. Conducting Institutes

2003IIT, Madras
2002IISc, Bangalore
2001Anyone knows who conducted...
2000IIT, Kharagpur
1999IIT, Bombay
8.

Where can I get the GATE brochure?

This information is published in most popular newspapers

9.

What books do I refer for GATE CSE?

Wrong question, nobody will give you an answer, we can only recommend a list of books, well the choosing part is left to you.

10.

Apart from the books do I need to refer the articles published in the Internet?

No harm to extend your knowledge, but do keep an eye on time. Most successful GATE'ians tell textbooks were more than sufficient, if used properly.

11.

Is there any official document that I can refer to, w.r.t GATE?

Nothing as such, but I would advise you ppl to read the last year's GATE brochure in detail. You will get a lot of information in that.

12.

Do I require to buy the GATE material from Brilliants, Elite, etc, If I do, then which is the best?

Well this is a very sensitive issue, it is generally a recommended option to get these materials, because it helps cover any new additions or information required for GATE. We people made up a group and shared the materials. Hope those tuition fellas don't read this part of the document.

13.

I need the syllabus for GATE Computer Science 2004

GATE CSE 2004 syllabus is not yet released, usually there are no changes in content, so I it a good idea to stick on to the previous year's GATE Syllabus.

GATE 2003 - CS - COMPUTER SCIENCE AND ENGINEERING

  • BASIC MATHEMATICS

    • Mathematical Logic

      • Propositional Logic, First-order Logic

    • Probability

      • Random variables and expectation, Conditional probability, Independent random variables, Distributions (Uniform, Normal, Exponential, Poisson, Binomial)

    • Discrete Mathematics

      • Sets, Relations, Functions, Groups, Lattice, Boolean algebra, Induction, Recurrence relations

    • Combinatorics

      • Permutations, Combinations, Counting, Summation

    • Elementary graph theory

      • Basic properties, Connectivity, Covering and matching, Planarity

    • Elementary concepts of Linear and Matrix Algebra

    • Numerical methods

      • Classical algorithms for interpolation and root finding

  • THEORY OF COMPUTATION

    • Formal Languages and Automata Theory

      • Regular languages and finite automata, Context free languages and Push-down automata, Recursively enumerable sets and Turing machines, Un-decidability

    • Analysis of Algorithms and Computational Complexity

      • Asymptotic analysis (best, worst, average case) of time and space, Upper and lower bounds on the complexity of specific problems, NP-completeness

  • COMPUTER HARDWARE

    • Digital Logic

      • Logic functions, Minimization, Design and synthesis of Combinational and Sequential circuits

    • Number representation and Computer Arithmetic (fixed and floating point)

    • Computer Organization

      • Machine instructions and addressing modes, ALU and Data-path, hardwired and micro-programmed control, Memory interface, I/O interface (Interrupt and DMA mode), Serial communication interface, Instruction pipelining, Cache, main and secondary storage

  • SOFTWARE SYSTEMS

    • Data structures

      • Notion of abstract data types, Stack, Queue, List, Set, String, Tree, Binary search tree, Heap, Graph

    • Programming Methodology

      • C programming, Program control (iteration, recursion, Functions), Scope, Binding, Parameter passing, Elementary concepts of Object oriented, Functional and Logic Programming

    • Algorithms for problem solving

      • Tree and graph traversals, Connected components, Spanning trees, Shortest paths

    • Hashing, Sorting, Searching

    • Design techniques (Greedy, Dynamic Programming, Divide-and-conquer)

    • Compiler Design

      • Lexical analysis, Parsing, Syntax directed translation, Runtime environment, Code generation, Linking (static and dynamic)

    • Operating Systems

      • Classical concepts (concurrency, synchronization, deadlock), Processes, threads and Inter-process communication, CPU scheduling, Memory management, File systems, I/O systems, Protection and security

    • Databases

      • Relational model (ER-model, relational algebra, tuple calculus), Database design (integrity constraints, normal forms), Query languages (SQL), File structures (sequential files, indexing, B+ trees), Transactions and concurrency control

    • Computer Networks

      • ISO/OSI stack, sliding window protocol, LAN Technologies (Ethernet, Token ring), TCP/UDP, IP, Basic concepts of switches, gateways, and routers

14.

I don't have any idea about the relation between marks, percentile, and rank

See the table of GATE-2003 statics

Table 4. GATE-2003 Results (Extract form results)

DepartmentRank (R)Out of (N)Percentile (P)Absolute Score
CS13779799.99867/867
CS23779799.99851/867
CS33779799.99789/867
CS43779799.99786/867
CS53779799.99782/867
CS103779799.97724/867
CS263779799.93678/867
CS503779799.87660/867
CS1003779799.73637/867
CS5063779798.60582/867
CS10183779797.12557/867
CS15233779795.73545/867
CS20083779794.55537/867
CS30513779791.68522/867
CS39603779789.25514/867

Percentile (P) = (No. of Students below you) / (No. of Students)

P = ( N - R ) / N

e.g. 100th rank, P = ( 37797 - 100 ) / ( 37797 ) = 99.73

15.

Could someone tell the list of gate-specific books

Thanks to sunny narola for contributing this valuable piece of information...

sunny: "I suggest u take one book at a time and get to the next after you are through with the previous."

  • Gate Complete Reference - J. V. N. Ramesh

  • Multiple Choice Questions CSE - Williams

  • Question Bank Bible CSE - S. Jaiswal

  • Question Bank CSE - S. K. Basandara

  • Computer Science (Guide for GATE) - G. K. Publishers

  • Computer Science Engineering GATE (Objective) - A. Handa

  • CSE (GATE) - Bhanu Pratap

  • CSE Papers - G. K. Publishers

  • CSE (Confirming To The Syllabus Of Gate) - G. K. Publishers

  • ELITE Academy Study Material + Question Bank

16.

List of books for Computer Hardware

Computer Hardware includes Digital Logic, Number representation and Computer Arithmetic, and Computer Organization. It is hard to classify the books for each one of the above mentioned three subjects, instead I will try to list the books which are most commonly used

  • M. M. Mano. Computer System Architecture , 3rd Edition, Prentice Hall of India, 1993.

  • J. P. Hayes, Computer Architecture and Organization, McGraw Hill, 1979.

  • V. C. Hamacher, Z.G. Vranesic and S.G. Zaky, computer Organization, 4th Ed., McGraw-Hill, 1996.

  • David A. Patterson and John L. Henessey, Computer Architecture a Quantitative Approach, Morgan Kauffmann, 1990/1996.

  • A. S. Tanenbaum. Structured Computer Organization , 3rd Edition, Prentice Hall of India, 1990.

  • Digital Computer Design by V. Rajaraman and T. Radhakrishnan

17.

List of books for Discrete Mathematics

Sets, Relations, Functions, Groups, Lattice, Boolean algebra, Induction, Recurrence relations

  • C. L. Liu, Elements of Discrete Mathematics, McGraw-Hill International Editions, 1985.

  • Discrete Mathematics by Tremblay & Manohar

18.

List of books for Theory of Computation (Formal Languages and Automata Theory)

Regular languages and finite Automata, Context free languages and Push-down Automata, Recursively enumerable sets and Turing machines, Un-decidability

  • John C. Martin

  • A. V. Aho, J. E. Hopcroft and J. D. Ullman, Introduction to Automata, Languages and Computation, Addison Wesley, 1980.

  • H.R. Lewis and C.H.Papadimitrou, Elements of the Theory of Computation, Prentice Hall Inc., 1981.

  • Peter Linz, Finite Automata and Formal Languages

  • Theory of Computations - K L P Mishra & Chandrashekar

19.

List of books for Theory of Computation (Analysis of Algorithms and Computational Complexity)

Asymptotic analysis (best, worst, average case) of time and space, Upper and lower bounds on the complexity of specific problems, NP-completeness.

  • This concept is mostly embedded in the algorithm books.

20.

List of books for Data Structures and Programming and Algorithms

Data structures: Notion of abstract data types, Stack, Queue, List, Set, String, Tree, Binary search tree, Heap, Graph

Programming Methodology: C programming, Program control (iteration, recursion, Functions), Scope, Binding, Parameter passing, Elementary concepts of Object oriented, Functional and Logic Programming

Algorithms for problem solving: Tree and graph traversals, Connected components, Spanning trees, Shortest paths Hashing, Sorting, Searching

Design techniques (Greedy, Dynamic Programming, Divide-and-conquer)

Data structure by Horowitz, Sahani. Rigorous preparation for this is a must as good amount of questions will be asked on this. If you get some time (and if book is available) read algorithms by Rivest, Coreman. This is really good (and tough) book. Some other basic book will also do. Try to read from different books. You will find something new in each of them

  • Tremblay and Sorenson. An Introduction to Data Structures with Applications , 2nd Edition, McGraw Hills, 1985.

  • E.Horowitz, S.Sahni, Fundamentals of Computer Algorithms, Galgotia Publishers, 1984.

  • T. H. Cormen, C.E. Leiserson and R.L. Rivest, Introduction to Algorithms, Tata-Mcgraw Hill Publishers, New Delhi, 1998.

  • Cormen, Leiserson, and Rivest. Algorithms , MIT Press, 1990.

  • A. V. Aho, J. E. Hopcroft, and J. D. Ullman, Data Structures and Algorithms, Addison-Wesley, USA, 1984.

  • A. V. Aho, J. E. Hopcroft, and J. D. Ullman, The Design and Analysis of Computer Algorithms , Addison Wesley, 1974.

  • E. Horowitz, S. Sahni, Fundamentals of Data Structures, Galgotia Publishers 1983.

  • Horowitz and Sahni, Fundamentals of Data Structures in C/C++, Computer Science Press, 1997.

  • D. E. Knuth, The Art of Computer Programming, Vols. 1 and 3, Addison Wesley, 1968, 1975.

21.

List of books for Compiler Design

Lexical analysis, Parsing, Syntax directed translation, Runtime environment, Code generation, Linking (static and dynamic)

  • A.V.Aho, Ravi sethi and J.D.Ullman, Compilers, Tools and Techniques, Addison - Wesley, 1986.

  • D.M.Dhamdhere, Compiler Construction - Principles and Practice, Macmillan, India, 1997.

22.

List of books for Database Systems

Relational model (ER-model, relational algebra, tuple calculus), Database design (integrity constraints, normal forms), Query languages (SQL), File structures (sequential files, indexing, B+ trees), Transactions and concurrency control

  • R. Elmasri and Shamakant B. Navathe, Fundamentals of Database Systems, 3rd Edition, The Benjamin/Cummings Publishing company Inc., 1999.

  • H. F. Korth and A. Silberschatz. Database Concepts , 2nd Edition, Mcgraw Hill, 1991.

  • Abraham Silberschatz, Henry F. Korth and S. Sudarshan, Database System Concepts 3rd Ed, McGraw Hill, 1997.

  • C.J. Date, Database Systems, Sixth Edition, Addison Wesley, 1997.

23.

List of books for Computer Networks

ISO/OSI stack, sliding window protocol, LAN Technologies (Ethernet, Token ring), TCP/UDP, IP, Basic concepts of switches, gateways, and routers.

  • Andrew S. Tannenbaum, Computer Networks, Prentice Hall, Third Edition, 1997.

  • William Stallings, Hand Book of Data Communication, Volumes I, II and III, JW, 1990.

  • D. Bertsekas and R. Gallagher, Data Networks, Prentice Hall, Second Edition, 1987.

  • Douglas Comer, Inter-networking with TCP/IP

24.

List of books for Operating Systems

Classical concepts (concurrency, synchronization, deadlock), Processes, threads and Inter-process communication, CPU scheduling, Memory management, File systems, I/O systems, Protection and security.

Silberschatz & Galvin, coupled with OS concepts by Dhamdere should be more than enough

I suggest OS by Galvin. Don't read Unix as it is not needed. But if you read, it may be helpful in future (e.g. in interviews)

  • A. Silberschatz, J.L. Peterson and P.B. Galvin, Operating System Concepts, 3rd Edition, Addison-Wesley, 1991.

  • Andrew S. Tanenbaum, Modern Operating Systems, Prentice Hall, 1992.

  • D.M.Dhamdhere, Systems Programming and Operating Systems, 1997.

25.

Which is the best IIT? What do I choose first?

I would recommend you to talk to at least 3 people to get a more accurate answer, a first year MTech student, a second year MTech student, and lastly a person who just finished his MTech. (Please let me know, I will add the information here...)

Table 5. Extract form website of V. Shreeniwas (Student at IIT Kanpur)

Sl. No.Subject of MTechDepartmentInstitutionPossible ranks (*)
1Comp. & AutomationComp. & AutomationIISc, Bangalore50
2Internet ScienceComp. & AutomationIISc, Bangalore75
3CSECSEIIT Kanpur200
4CSECSEIIT Bombay200
5CSECSEIIT Delhi225-250
6CSE, various specializationsCSEIIT Kharagpur300
7CSECSEIIT Madras300
8CSEElectronicsIIT Roorkee400
9CSECSEIIT Guwahati500
10Comp. TechEEIIT Delhi600
11ITKReSITIIT Bombay1500 – 1800
12Comp. Appl.MathsIIT Delhi750
13Various Specializations---IIITs1500-2000
14CSECSEDCE/NSIT1500

(*) - Possible ranks till where it may go down. The ranks provided here are pure guess work and have been kept on the higher side, that is the actual admissions are expected to close at a higher rank than stated here. But its reasonable to apply if you have this kind of rank.

Some tips regarding GATE Applying

  • The MTech IT course is run by Kanwal Rekhi School of IT (KReSIT) at IITB. The course is as good as the CS MTech with slightly more impetus on CS applications. However, their selection process is different. They call everybody till a low rank and have some tests/interview for them. That's precisely the rank is low, not because the course is bad or anything. A similar posture was adopted by IITK 2 years ago. So, some things are unpredictable. That's precisely why I said that the cut offs there in was just a humble estimations from my side. You accept it at your own risk.

  • The MTech IT at IITR is pretty bad. It is not even run at Roorkee. They run at the ERDC campus at NOIDA. Now, the MTech course is a total experience starting from the hostel life through to placements. A major part of it is lost in this course. So, Do that at your own peril.

  • IIITs are placed higher than RECs because they are good. They are having good faculty. They are developing well into research and getting good response from the Industry. The RECs are lacking the impetus to perform well in research. I have classmates here from two RECs - Calicut & Jaipur, and they verify the fact. So, I will maintain my rating for IIITs.

  • BARC etc are not taking you for education. They are taking you for placement as Scientist. Though, joining them has its own benefits:

    • You can do your PhD later under the QIP program.

    • You can join MTech side by side and join BARC and get your MTech converted into sponsored one. I have a classmate who does so. You get a higher fellowship during your MTech.

    • Of course, you sign a bond and that's a problem.

    • The Govt. sector is research is good, but I have heard that BARC is beset with problems.

  • Your GATE score is your percentile. Period. If they ask you for rank, you may provide that. But GATE score, nationwide, is regarded as your percentile.

26.

Any information about BITS pilani

(Please double check this content..., Someone had posted this on one of the groups long back)

BITS Pilani take both semester admissions and they are not of much difference.

There is no compulsion that you should be BITS graduate to appear in second sem/first sem.

Any one having bachelor's can apply, there is a written test conducted for that in which Questions from your graduation discipline are asked.

M.E (CS): You have to be Bachelor's in computer science

M.E (SS Software Systems): People who don't have Bachelor's in computer science can go for this.

There are difference of course structure but for job wise I don't find very much of a difference.

For more about information, see BITS brochure.

Website: http://www.bits-pilani.ac.in

27.

I need to know who contributed to this document

The list is small but, I'm sure it will grow...

Table 6. Contributors

Venkat from Bangalore (Author)
Maga from Bangalore (Author's friend)
Pavan from Bangalore (contrib: conducting institutes)
Sunny (contrib: list of gate-specific books)