GATE Syllabus for Computer Science and Information Technology
Engineering Mathematics
Graph Theory: independent sets, planarity, colouring, isomorphism, connectivity, cut vertices and edges, spanning trees, covering.
Set theory and Algebra: Functions, Boolean algebra, sets, partial orders, lattice, relations, groups.
Mathematical Logic: First order logic, propositional logic.
Combinatorics: Generating functions, asymptotics, permutations, counting summation, combinations and recurrence relations.
Calculus: Partial derivatives, theorems of integral calculus, maxima and minima, limit, evaluation of definite and improper integrals, total derivatives, Mean value theorems.
Probability: Distributions, mode and standard deviation, poisson, median, binomial, exponential, random variables, normal, uniform.
Numerical Methods: Bisection and NewtonRaphson methods, LU decomposition for systems of linear equations, numerical integration by trapezoidal and Simpson’s rules, numerical solutions of nonlinear algebraic equations by Secant.
Linear Algebra: Systems of linear equations, eigen values and eigen vectors, algebra of matrices.
Computer Science and Information Technology
Information Systems and software Engineering: Process specification, process life cycle, input/output design, planning and managing the project, coding, design, testing, maintenance, data flow diagrams, information gathering, implementation, requirement and feasibility analysis.
Operating system: Synchronization, CPU scheduling, deadlock, memory management and virtual memory, I/O system, file system, protection and security, interprocess communication, threads, processes, communication concurrency.
Theory of computation: Recursively enumerable sets and turning machines, regular languages and finite automata, undecidability, context free languages and pushdown automata.
Programming and Data Structures: Arrays, queues, Stacks, trees, linked lists, binary heaps, binary search trees, parameter passing, programming in C, recursion, functions, binding, scope.
Digital Logic: Design and synthesis of combinational and sequential circuits, logic functions, number representation and computer arithmetic (fixed and floating point), minimization.
Web technologies: Basic concepts of clientserver computing, XML, HTML.
Databases: Query languages (SQL), transactions and concurrency control, file structures ( indexing, sequential files, B and B+ trees), relational model (relational algebra, tuple calculus), ERmodel, database design (integrity constraints, normal forms).
Algorithms: Tree and graph traversals, spanning trees, connected components, shortest paths, sorting, hasting, searching, upper and lower bounds, asymptotic analysis (best, average cases, worst) of time and space, basic concepts of complexity classesP, NP, NPhard, NPcomplete, asymptotic notation, analysis, notion of space and time complexity, design, greedy approach, worst and average case analysis, dynamic programming, divide and conquer.
Compiler Design: Intermediate and target code generation, syntax directed translation, basics of code optimization, lexical analysis, parsing.
Computer Organization and Architecture: Memory interface, cache main memory, addressing modes and machine instructions, I/O interface (interrupt and control DMA mode), secondary storage, ALU and datapath, instruction pipelining, CPU control design,
Computer Networks: Basic concepts of hubs, gateways and routers, switches, network securitybasic concepts of public key and private key cryptography, ISO/OSI stack, digital signature, LAN technologies (Ethernet, Token ring), firewalls, flow and error control techniques, application layer protocols (dns, icmp, smtp, ftp, pop, http), congestion control, routing algorithm, TCP/UDP and sockets, IP(v4).
