Computer Science and Information Technology - GATE 2021 Syllabus

Boolean Algebra; Combinational and Sequential Circuits; Minimization; Number representation and computer arithmetic (fixed and floating point);

Machine instructions and addressing modes; ALU, Data-path and Control Unit; Instruction pipelining; Memory Hierarchy: Cache, Main Memory and Secondary Storage; IO interface (Interrupt and DMA mode);

Programming in C; Recursion; Arrays; Stacks; Queues; Linked Lists; Trees, Binary search trees; Binary heaps; Graphs;

Searching; Sorting; Hashing; Asymptotic Worst Case Time and Space Complexity; Greedy; Dynamic Programming; Divide-and-conquer; Graph Search, Minimum Spanning Trees, Shortest Paths;

Regular Expressions and Finite Automata; Context Free Grammars and Push-down Automata; Regular and Contex-Free Languages, Pumping Lemma; Turing machines and Undecidability;

Lexical analysis; Parsing; Syntax-Directed Translation; Runtime environments; Intermediate Code Generation;

Processes, Threads; Inter-Process Communication, Concurrency and Synchronization; Deadlock; CPU Scheduling; Memory management and Virtual memory; File systems;

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;

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 Signature and Certificate; Firewalls;

Propositional Logic; First Order Logic; Sets; Relations; Functions; Partial Orders and Lattices; Groups; Graphs: Connectivity, Matching, Coloring; Combinatorics: Counting, Recurrence Relations, Generating Functions;

Matrices; Determinants; Systems of linear equations; Eigen values and Eigen vectors; LU Decomposition;

Limits; Continuity; Differentiability; Maxima and Minima; Mean Value Theorem; Integration;

Random Variables; Uniform Distributions; Normal Distributions; Exponential Distributions; Poisson Distributions; Binomial Distributions; Mean, Median, Mode and Standard Deviation; Conditional Probability and Bayes Theorem;