# GATE Computer Science and Information Technology Syllabus

Engineering Entrance Exam » GATE »

**GATE Computer Science & Information Technology Syllabus ( CS )**

**Section 1 : Engineering Mathematics Syllabus**

Discrete Mathematics : Propositional and first order logic. Sets, relations, functions, partial orders and lattices. Groups. Graphs: connectivity, matching, coloring. Combinatorics : counting, recurrence relations, generating functions.

Linear Algebra : Matrices, determinants, system of linear equations, eigenvalues and eigenvectors, LU decomposition.

Calculus : Limits, continuity and differentiability. Maxima and minima. Mean value theorem. Integration.

Probability : Random variables. Uniform, normal, exponential, poisson and binomial distributions. Mean, median, mode and standard deviation. Conditional probability and Bayes theorem.

Computer Science and Information Technology

**Section 2 : Digital Logic**

Boolean algebra. Combinational and sequential circuits. Minimization. Number representations and computer arithmetic ( fixed and floating point ).

**Section 3 : Computer Organization and Architecture **

Machine instructions and addressing modes. ALU, data ‐ path and control unit. Instruction pipelining. Memory hierarchy : cache, main memory and secondary storage; I/O interface ( interrupt and DMA mode ).

**Section 4 : Programming and Data Structures **

Programming in C. Recursion. Arrays, stacks, queues, linked lists, trees, binary search trees, binary heaps, graphs.

**Section 5 : Algorithms **

Searching, sorting, hashing. Asymptotic worst case time and space complexity. Algorithm design techniques : greedy, dynamic programming and divide ‐ and ‐ conquer. Graph search, minimum spanning trees, shortest paths.

**Section 6 : Theory of Computation **

Regular expressions and finite automata. Context – free grammars and push – down automata. Regular and contex – free languages, pumping lemma. Turing machines and undecidability.

**Section 7 : Compiler Design **

Lexical analysis, parsing, syntax – directed translation. Runtime environments. Intermediate code generation.

**Section 8 : Operating System **

Processes, threads, inter ‐ process communication, concurrency and synchronization. Deadlock. CPU scheduling. Memory management and virtual memory. File systems.

**Section 9 : Databases **

ER ‐ model. Relational model : relational algebra, tuple calculus, SQL. Integrity constraints, normal forms. File organization, indexing ( e.g., B and B+ trees ). Transactions and concurrency control.

**Section 10 : Computer Networks**

Concept of layering. LAN technologies ( Ethernet ). Flow and Error control techniques, switching. IPv4 / IPv6, routers and routing algorithms ( distance vector, link state ). TCP / UDP and Sockets, congestion control. Application layer protocols ( DNS, SMTP, POP, FTP, HTTP ). Basics of Wi – Fi. Network security: authentication, basics of public key and private key cryptography, digital signatures and certificates, firewalls.