Topics	Sub Topics	2014 (Set 1)	2014 (Set 2)	2014 (Set 3)	Analysis	2006	Analysis
DFA and NFA, Mealy and Moore Machines	DFA	1			Easy
	NFA
	e-NFA
	Interconversions
	Minimization
	Mealy Machines
	Moore Machines
Regular Expressions	Construction of RE
	Interconversions(RE to FA and FA to RE)	2		1	Easy
Regular Languages and Grammars	Regular Grmmars
	Regular Languages	1	1		Easy	2	Tricky Problem.
	Closure Properties		2		Tricky	2	Tricky Problems but Solvable.
	Decision Properties
	Pumping Lemma
PDA	Construction , Example PDAs
CFLs	Verifying whether language is CFL or not			2	Easy	1	Easy-Medium level problems. We can easily solve them.
	Clsoure properties
	Decision Properties
	Pumping Lemma
CFG	Construction
	Derivation of strings
	Languages					4	4 (Linked answer question has been asked. It is easy to meduim level problem).
Turing Machines	Construction		2
	Examples
Recursive and Recursive Enumerable Languages	RL and RELs	2			Easy
	Closure Properties					2	Easy
	Decision Properties					4	4 (Linked answer question has been asked. It is easy to meduim level problem).
Decidability and Undecidabilty			1	2	Easy to medium level based on decision properties in set 2 and Tricky in set 3	1	Tricky one
Complexity Clasess		2		2	Easy problem based on the definitions of P, NP in set 1 and tricky in set 3
Total		8	6	7		9

Topics	Sub Topics	2014 (Set 1)	2014 (Set 2)	2014 (Set 3)	Analysis	2006	Analysis
Introduction to Compilers	Over view of compilers		1		Easy
Lexical Analysis	Tokens, patterns, Lexemes
	Elimination of Left recursion
Parsing	Top down parsers		1		Easy	2	Easy problems to attempt.
	First and Follow functions
	Shift reduce parsers					2	Easy
	Bottom up Parsers(LR(0), SLR(1), CLR(1) and LALR(1)	2			Easy question based on shift reduce concept	1	Easy to Medium level questions. Chances of doing a silly mistake.
	Operator precdence parser
SDT	Syntax directed Translations					2	Easy
	L-Attributed and S-Attributed defintions
Runtime Environments				1	Easy to Medium problem
Symbol Tables			2
Intermediate Code Generation	Intermediate code			1	Easy
	Static Single Assignment
	AST, CFG, Basic Blocks, DAG			1
Local Optimization				4	One question has been from DAG easy to medium level	2	Easy
Data flow Analysis	Data flow Analysis	1			Easy question based on data flow analysis
	Constant propagation
	Live variable Analysis
	Common Subexpression elimination
Total		3	2	7		9

Topics	Sub Topics	2014 (Set 1)	2014 (Set 2)	2014 (Set 3)	Analysis	2006	Analysis
Boolean Algebra	Minimal Expressions and logic gates		2	2	Question to get the function of overflow conditon was asked. If we know all the cases of getting overflow, we can easily solve the given problem.	2	Question to get the function of overflow conditon was asked. If we know all the cases of getting overflow, we can easily solve the given problem.
	K-maps				A question regarding finding the implicants using k-maps was asked for 2 marks. The level of the question is medium.	2	A question regarding finding the implicants using k-maps was asked for 2 marks. The level of the question is medium.
	SOP and POS	3		1
Number System	Number Representation	1	1		A gray code conversion question was asked from this topic. The level of the question was easy.	2	A gray code conversion question was asked from this topic. The level of the question was easy.
	IEEE floating point representation		2
Combinational circuit	Adders				A question of 2 marks is aksed form this topic. The level of the question was easy.	2	A question of 2 marks is aksed form this topic. The level of the question was easy.
	ROM, PAL, PLA
	Multiplexers and Decoders			1	One question of 2 marks is aksed from this topic. It is an easy and scoring question.	2	One question of 2 marks is aksed from this topic. It is an easy and scoring question.
Sequential Circuits	Flip flops
	Counters		1		One easy and one tricky question has been asked from this topic.	3	One easy and one tricky question has been asked from this topic.
	Circuit output			2
Total		4	6	6		13

Topics	Sub Topics	2014 (Set 1)	2014 (Set 2)	2014 (Set 3)	Analysis	2006	Analysis
Graph Theory	Graph Properties	2	2	2	Havel Hakimi(2)-Set 1, Graph isomorphism(2)-Set 2, Based on planar graph(2)-Set 3	4	2 questions on Degree of graph(2x2)
	Graph Coloring
	Connectivity	2	1	2	Number of edges(2)-Set 1, Maximum number of edges(1)-Set 2, Number of edges(2)-Set 3	2	Number of connected components(2)
Logic	FOL	1		2	English to FOL(1)-Set 1, English to FOL(2)-Set 3	2	English to FOL(2)
	Propositional Logic	2	2	1	Whether expression is true if 2 out 3 variables are exactly true(2)-Set 1, Tautology based question(2)-Set 2, Equivalence and implication based question(1)-Set 3	4	Tautology(2), Find equivalence to given truth table of an unknown binary operator(2)
Set Theory & Algebra	Functions	2	1	2	Number of functions(2)-Set 1, Calculate function value(1)-Set 2, Given a function check the correctness of statements (2)-Set 3	5	Number of functions(1)-Easy, Function that permutes elements in set(2)-Difficult, Summation of function(2)-Medium
	Group			3	Order of subgroup(1)-Easy , Max number of elements in a group(2)-Medium	1	Check group properties(1)
	Lattice
	Relations					1	Check partial, total, equivalence relation properties(1)
	Sets		2	1	Symmetric difference of sets(2), Set cardinality(1)	2	Check Set properties(2)
Total		9	8	13		21

Topics	Sub Topics	2014 (Set 1)	2014 (Set 2)	2014 (Set 3)	Analysis	2006	Analysis
Linear Algebra	Determinants		1		Problems on calculus which uses determinents have been asked.
	Eigen Values and Eigen Vectors	1	2	1	Most Important topic here is Eigen Values and Eigen Vectors asked every year.
	System of Linear Equations	1			Problems on solution for system of linear equations, whether a system of linear equations have a solution.	2	Combination of determinant and number of solutions for the system of equations
Calculus	Limits				Problems of L'Hopitals rule
	Continuity	2			Problems on Continuity and discontinuity
	Differentiability	3			Problems on rolls theorem and mean value theorem, maxima and minima
	Integeration			3	Problems on definite integrals are mostly asked
Combinatorics	Permutations & Combinations	2			Concepts of permutations and combinations are used with concepts of different subjects counting the number of MST's, number of serializable schedule, etc.
	Generating Functions				Problems based on coeffecient a term in an infinite series have been asked.
	Recurrence Relations				In a few cases problems on recurrence relations are given in the form of words and recurrence relation has to be reframed.
Probability	Probability	3	1	2	Questions on probability includes concepts from combinatorics such as princple of inclusion and exclusion.	2	Coins problem with indpendent events
	Conditional Probability				Questions on conditional probability
	Probability Distribution Functions	1			Questions are asked based on uniform, normal and poisson distribution, mean, variance and expectation	1	Question asked on the concept of expectation
Total		13	4	6		5

Topics	Sub Topics	2014 (Set 1)	2014 (Set 2)	2014 (Set 3)	Analysis	2006	Analysis
Numbers	Factors					NIL
	Base System			2	It is a moderate level topic, with chance of minor silly mistake.
	Sequence & Series		1	1	AP, GP formulas are important to be remembered.
	Numerical Computation	1			Moderate level topic with some tricks involved.
Averages & Mixtures	Average		1		(optional)
Arithmetic & Word Based Problems	Clock Time
	Partnership		2		(optional)
	Direction Sense		2
	Ratio & Proportion
	Percentage
	Speed, Time & Distance	2		2	Easy level topic, concentrate on doing correct calculations with the help of the virtual calculator available.
Geometry	Circle
	Triangle
	Mensuration
	Misc.	2			Vast topic with chances of some moderate to hard problems, need to learn all the necessary formulaes.
Algebra	Functions
	Equations	1	2		(optional)
Data Interpretation	Contour Plots
	Line Graph		2	2	Problems are sometimes lengthy, need to be attentive enough so that you do not miss the necessary observations.
	Bar Graph
	Tabular	2		1	Its better to analyse the tables very minutely and just note down all the necessary information required in the rough sheet.
	Pie Chart
	Venn Diagrams
Analytical Aptitude	Logic
	Analogy
	Numerical Relations and Reasoning
Spatial Aptitude	Translation
	Rotation
	Scaling
	Mirroring
	Assembling and Grouping
	Paper folding, cutting, and patterns in 3D and 2D
Miscellaneous	Maxima & Minima
	Logical Reasoning
	Odd One
	Permutation & Combination
	Probablity
	Misc
English	Grammar			1	Its is dynamic, answer only those questions for which you are confident and you know the correct answer. Passage reading is scoring if direct questions are asked out of it, so reading the same carefully is very important.
	Grammatical Sentence
	Meaning	2	1
	Most Appropriate word	1	1
	Passage Reading	2	4	4
	Statement Sufficiency
	Statements Follow
	Tenses		1	1
	Verbal Reasoning	2
	Word Pairs
	Misc			1
Total		15	15	15

Topics	Sub Topics	2014 (Set 1)	2014 (Set 2)	2014 (Set 3)	Analysis	2006	Analysis
Sorting and Searching	Sorting Algorithms	1		1	This is a scoring topic, questions are usually easy and not much tricky.	2	Question based on quick sort and comprison of properties of sorting algorithms were asked, this is fairly easy and scoring topic.
	Searching			2	This is a scoring topic, questions are rarely asked but there are other areas where the concepts of this topic will be applied.	1	Question was asked on the minimum number of coparions for min and max in an array it is an easy topic if one coveres all the related algorithms.
Time complexity algorithms	Time complexity of given code	1			Questions form this topic vary from easy to morderate and may be tricky at times.	1	Small fragment of code based on which time compelxity quesiton was asked.
	Recurrence reation		1		This topic is easy and scoring mostly quesiton can be solve using master theorem, if one practtces Master Theorem/ Substitution method and recurrence tree method he must be able to solve all the problems.	2	Queston based on a recurrence realtion was asked, it was a medium level and fairly easy to solve.'
Linked Lists ,Stacks and Queues	Stacks and Queues		2		Basic understandin of stacks and queues and its implementation is nencessary to solve any quesiotn for this topic.
Trees, Hashing & Collision Resolution	Hashing	2		2	Quesitons for this topic vary from moderate to hard, quesiton based on probabilty was asked which made it tricky the key is to form the events properly.
	Trees and Tree traversal	1		1	Question based on array based implementaion and tree traversal has been asked, this is a fairly easy topic one needs to have a proper understanding of the code as well as sometimes quesiton based on the code is also asked.	1	Question was asked based on tree traversal it is an easy topic if one has proper understanding on basic tree traversal techniques.
	Heaps/Heap sort		1		Question based on the max heap was asked which is easy to solve.	5	Quesiton based on how to find the minimum element from the max heap and validitiy of heap and insertion on heap was asked this is a fairly easy topic which one can score easily
Graphs and Graph Traversals, Minimal Spanning Trees, Shortest Paths	Minimal spanning trees		2		Question based on Number of MST was asked which is easy, question from this topic are not much difficult, with knowledge of Kruskals. Prims and cut properlty most of the quesiton can be solved.	3	Question based on kruskals algoirthm(order of addition of edges) and a direct question on calcualting the weight of MST was asked.
	BFS and DFS and its applications	2	1	1	Questions were asked on shortest paths based on BFS and appliecaions of DFS such as SCC(strongly connected components), on this topic problems could be both easy and tricky.	3	Quesiton was asked baed on propertes of DFS and another quesiton as was asked on single source shortest path using BFS.
Greedy Approach and Dynamic Programming.	Greedy Approach		2		Question based on optimal merge pattern was asked which as easy, see at most one question on greedy algorithms mostly.
	Dynamic Programming		2		Quesiton was asked from Longes common subsquece, quesiton are at times easy and at times tricky from this topic.	2	A pseudo code was given and qeusiton was asked about its working, questions can be tricky from dynamic programming.
Total		7	11	7		20

Topics	Sub Topics	2014 (Set 1)	2014 (Set 2)	2014 (Set 3)	Analysis	2006	Analysis
ER and Relational Model	ER diagrams				It is an easy topic, if we are clear about all the relationships and boundary cases we can easily solve the questions from this topic.	2	The question was asked in combination with the sQL. It was a query plan quesiton. This topic(query plan) is no more the part of GATE syllabus.
	Relational Schema and key constraints	1	2	1	It is a medium level topic. The contraints of the relations sometimes confuse us and make us fall into the trap.
RA, TRC, and SQL	Relational Algebra			3	This is tricky topic. Not difficult if we are clear about all the RA operations.
	Relational Calculus				It is difficult to understand TRC and DRC query due to the use of quantifiers. Questions are rarely asked from this topic.
	SQL	2	4	2	Both easy and medium level questions are asked from SQL. We suggest students to have clear underdstanding of the clauses and stick to the GATE standards for the use of clauses in a valid query.	4	One question if of medium level while one is easy.
FD and Normalisation	FD Decomposition	3			It is fairly easy topic and the most scoring part from DBMS.	2	The question asked was very easy and a scoring question.
	Normalisation				It is fairly easy topic and the most scoring part from DBMS.
Transaction and concurrency control	Recoverability and Serializability	2	2		Both recoverability and serializabiliyt are important topics rom DBMS. They are easy to solve. We may expect atleast one question from this topic in every test.
	Lock based protocol				It is an easy topic, just needs practice.
	Timestamp ordering protocol				It is medium level topic. We are clear with all the TSP conditions of read and write we can solve the problem with minimum trouble. It sometimes confuse us with the answer so we have to be careful while solving problem from this topic.
	Log based recovery				Questions are rarely asked from this topic but they are majorily tricky. We need to be careful while solving the problems from this sections( must have information all the recovery systems in DBMS).	1	The question asked was of medium level.
Indexing	B & B+ trees				It is easy topic but questions asked are bit tricky. We need to be careful while solving the problems.
Total		8	6	6		9

Topics	Sub Topics	2014 (Set 1)	2014 (Set 2)	2014 (Set 3)	Analysis	2006	Analysis
Process Management	Process Scheduling & Scheduling algorithms	2	2	2	SRTF based question(2)-Set 1, Round Robin with IO(2)-Set 2, SRTF based question(2)-Set 3	5	Number of Context switches(1), % of CPU idle(2) , LRTF(2)
	Fork
	System Calls (Newly added)
	Interrupts
	Threads	1			User vs Kernel level threads(1)
Concurrency and Synchronization	Synchronization Mechanism Requirements (ME, Progress, Bounded Waiting)					4	2 questions on Barrier Synchronization (2x2)
	Software based solution (Lock variable, Strict Alternation, Peterson's Solution, etc)
	Hardware based solution (Disable Interrupts, TSL, Swap, etc)					2	Atomic Fetch and Set(2)
	OS based solution (Semaphores, Sleep & Wakeup, etc)		2		Producer Consumer semaphore based question(2)
	Concurrency Mechanism - Precedence Graph (Parbegin - Parend, Fork - Join ), Concurrent Execution
Deadlock	Deadlock Prevention
	Deadlock Avoidance (Banker's Algorithm)
	Deadlock Detection & Recovery (Resource Allocation Graph)
	Resource Allocation & Current System State	2		2	Resource allocation and system state(2)-Set 1, Minimum number of resources required(2)-Set 3	2	Resource allocation criteria to avoid deadlock (2)
Memory Management	Partitioning (Fixed & Variable)
	Paging (Single Level, Multi-level Paging)			2	EMAT paging with TLB(2)
	Demand Paging (Page fault)					4	Tlb tag(2), theoretical question on Virtual Memory(2)
	Segmentation
	Page Replacement	2	2	1	OPT policy (2)-Set 1, Comparing OPT with other replacement algorithm(2)-Set 2, LRU page faults(1)-Set 3
File Systems	Disks		1		Max file size(1)
	File Allocation Methods
	ADisk Scheduling	1			SSTF disk scheduling(1)
Total Marks Per Year		8	7	7		17

Topics	Sub Topics	2014 (Set 1)	2014 (Set 2)	2014 (Set 3)	Analysis	2006	Analysis
For Loop & Array	For loop	4			Two questions of 2 marks on for loop it is medium	2	2 Mark question on while loop and arrays medium level question
	Array
Static and struct keyword	Static Keyword		2		2 mark question on static keyword and conditional statemet if it is medium.
Function Calling	Function call		3		1 Mark question on recursion it is easy. Another 2 mark question on recursion is medium	2	2 mark pass by reference question is medium
String and Pointer	String & Pointer	1			1 mark question on pointer easy	2	2 mark question on swapping and includes pointer bit hard
Miscellaneous Topics	Dynamic allocation (malloc)
	Unary operators
	Static & dynamic Scoping
	Misc.		1	2	1 mark question on the variables mostly calcuation based medium-Set 2, 2 mark question based on eng maths as well as combination of pseudo code asked for transose of matrix it is hard-Set 3
Total		5	6	2		6

Topics	Sub Topics	2014 (Set 1)	2014 (Set 2)	2014 (Set 3)	Analysis	2006	Analysis
Physical layer
Data link layer	Flow control	2			Easy question on efficiency of sliding winow protocol	4	Two questions asked one is easy and onther is medium
	MAC protocols
	LAN technologies	2			Medium level question on token ring protocol based on numerical.
	Error detection			1	Simple one mark question on bit stuffing
	Framing
	LAN devices					4	Two questions asked on bridges it is linked questions one is easy another is medium
Network layer	IPV4 header		1	1	Easy question on TTL with diagram-Set 2, Simple one mark questionon IPV4 header asked about TTL, frgamnet offset etc-Set 3	1	Easy question on TTL
	Fragmentation			2	2 mark question on fragmentation DF, MF etc
	Routing	1	1		Medium level question on the distance vector and the link state routing-Set 1, Theory question on RIP and OSPF protocol-Set 2
	IP addressing			2	2 mark question on subnetting based on table medium question.	2	It is a easy question on subnetting
	Switching
	Protocols			2	2 mark questions on wrap around numerical question lil bit tough
	Traffic shaping
Transport layer	Flow control
	Congestion control	2			Easy question on congestion control AIMD
	TCP transition state
	TCP socket		1		Easy theory question on socket
	UDP
Application layer	HTTP/SMTP/POP3/ IMPA4	1	2		Simple theory based question on HTTP and DNS-Set 1, Question on HTTP based on security tough one but security is not part of syllabus now-Set 2
	DNS/DHCP		2		Two mark question again from HTTP medium level question, connection establishment question
Mixed questions	Layering			1	Simple general question on OSI layer theory question.
Total		8	7	9		11

Topics	Sub Topics	2014 (Set 1)	2014 (Set 2)	2014 (Set 3)	Analysis	2006	Analysis
Machine instructions and addressing modes	Memory Interfacing
	Machine Instructions( Including Instruction Format) [easy]	1			Easy	3	GATE 2006 1- mark question is easy and 2-Marks question is tricky or difficult level
	CPU Organization
	Addressing Modes
ALU, data‐path and control unit	Control Unit and design		1		Easy
	Hardwired Control unit		1		Easy
	Micro programmed control unit		1		Easy
Instruction pipelining	Pipelining [must for rankers]	2		3	Easy-Set 1, Pipeline execution times has been asked and it is an easy to medium level problem- Set 3
	Performance of a Computer (Speed Up)					2	GATE 2006- Easy to Medium level problem
	RISC and CISC
	Instruction Cycles		2		Medium
	Pipeline dependencies
Memory hierarchy: cache, main memory and secondary storagev [Very easy to understand]	Memory Hierarchy(AMAT)			2	Average memory access time Easy to Medium	6	2(Tricky) + 4(Linked answer question has been asked from direct mapping and set associative mapping . It is an easy to medium level problem and we can easily solve it)
	Cache Memory		2		1 Mark question for the TAG bits which is easy to solve
	Direct Mapping
	Associative Mapping
	Set-associative Mapping		3		Easy to Medium level problems from cache Mapping techniques
	Cache Replacement policies	2			Meduim-tricky problem
	Secondary Storage
I/O interface (Interrupt and DMA mode)	I/O Interface
	DMA
Total		6	7	5		11