# 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.