GATE Syllabus for Computer Science and IT

Course Syllabus

• Propositional and first order logic
  • Sets
  • Relations
  • Functions
  • Partial orders
  • Lattices
• Groups
• Graphs −
  • Connectivity
  • Matching
  • Coloring
• Combinatorics −
  • Counting
  • Recurrence relations
  • Generating functions
• Unit 2: Linear Algebra
• Matrices
• Determinants
• System of linear equations
• Eigenvalues and eigenvectors
• LU decomposition
• Unit 3: Calculus
• Limits, continuity and differentiability
• Maxima and minima
• Mean value theorem
• Integration
• Unit 4: Probability
• Random variables
• Uniform, normal, exponential, poisson and binomial distributions
• Mean, median, mode and standard deviation
• Conditional probability
• Bayes theorem
• Section B: Digital Logic
• Boolean algebra
• Combinational and sequential circuits
• Minimization. Number
• representations and computer arithmetic (fixed and floating point)
• Section C: 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 D: Programming and Data Structures
• Programming in C
• Recursion
• Arrays, stacks, queues, linked lists, trees, binary search trees, binary heaps, graphs
• Section E: Algorithms
• Searching, sorting, hashing
• Asymptotic worst case time and space complexity
• Algorithm design techniques −
  • Greedy
  • Dynamic programming
  • Divide-and-conquer
• Graph search, minimum spanning trees, shortest paths
• Section F: 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 G: Compiler Design
• Lexical analysis, parsing, syntax-directed translation
• Runtime environments
• Intermediate code generation
• Section H: Operating System
• Processes, threads, inter-process communication, concurrency and synchronization
• Deadlock
• CPU scheduling
• Memory management and virtual memory
• File systems
• Section I: 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 J: 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