Graduate Aptitude Test in Engineering (GATE) Syllabus | Computer Science
Mathematical Logic: Prepositional 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. 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.
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; BB)2))DDS>) JX>I>I)£>) JFJt-Jvocte), sjteiiozpJ j&sfrz? AypA? <2zkztiyj}> Z2&iztei&? <£&&? fW^^ 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.