GATE Computer Science and IT Syllabus


Advertisements

Subject Code: CS

Course Structure

Sections/Units Topics
Section A Engineering Mathematics
Unit 1 Discrete Mathematics
Unit 2 Linear Algebra
Unit 3 Calculus
Unit 4 Probability
Section B Digital Logic
Section C Computer Organization and Architecture
Section D Programming and Data Structures
Section E Algorithms
Section F Theory of Computation
Section G Compiler Design
Section H Operating System
Section I Databases
Section J Computer Networks

Course Syllabus

Section A: Engineering Mathematics

Unit 1: Discrete Mathematics

  • 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

To download pdf Click here.

Advertisements