Read organised GATE CSE revision notes by unit and revisit important topics during exam preparation.
GATE CSE subject notes
Engineering Mathematics
Use matrices, probability, calculus and discrete structures as tools for analysing algorithms and systems.
Mathematics questions reward a precise translation from words to structure. In linear algebra, first identify whether the question concerns existence, uniqueness or the number of solutions; rank and determinant conditions then become easier to select. In probability, define the sample space and events before applying a formula. For graph theory and combinatorics, small cases often reveal whether order, repetition or connectivity matters.
- Linear algebra: rank, inverse, eigenvalues and systems of equations
- Probability: conditional probability, Bayes' rule and common distributions
- Discrete mathematics: logic, sets, relations, graphs and combinatorics
Question method: Write the governing condition first—for example, P(A|B) = P(A ∩ B)/P(B)—and substitute only after checking the denominator and assumptions. Use a tiny counterexample to test statements containing words such as always, only or independent.
Common pitfall: Applying a familiar formula without checking independence, invertibility, convergence or whether objects are distinguishable.
Quick example: If two events A and B are independent, P(A ∩ B) = P(A)P(B). Do not confuse independence with mutually exclusive events: two non-empty mutually exclusive events cannot be independent.
Digital Logic
Move confidently between Boolean expressions, logic circuits and sequential-system behaviour.
Digital logic becomes manageable when representation and behaviour are kept separate. A truth table describes behaviour, a Boolean expression represents it algebraically, and a circuit implements it. For sequential logic, the current state is part of the input to the next-state function, so timing and the active clock edge matter in addition to the logic expression.
- Boolean algebra, canonical forms and Karnaugh-map minimisation
- Combinational circuits: adders, multiplexers, decoders and comparators
- Sequential circuits: flip-flops, counters, registers and finite-state machines
Question method: For combinational circuits, label input and output widths before counting gates or select lines. For flip-flop and counter questions, create a short present-state/next-state table and trace only the number of clock edges requested.
Common pitfall: Treating don't-care entries as mandatory zeros, or changing a flip-flop output before the specified triggering edge.
Quick example: A 4-to-1 multiplexer needs two select lines because two bits represent four choices. In general, a 2^n-to-1 multiplexer uses n select lines.
Computer Organization and Architecture
Relate instruction execution to datapaths, memory hierarchy, pipelining and I/O.
Architecture questions often connect two views of the same machine: the programmer-visible instruction and the hardware path that executes it. Performance depends on instruction count, cycles per instruction and clock-cycle time. Memory questions add spatial and temporal locality, so always distinguish address bits used for the block offset, cache index and tag.
- Machine instructions, addressing modes and ALU/datapath design
- Pipelining, data hazards, control hazards and performance
- Cache mapping, virtual memory, secondary storage and I/O
Question method: Draw a bit-field diagram for every cache or address problem. In pipelines, list the stage occupied by each instruction cycle by cycle; mark data availability and branch resolution before deciding how many stalls occur.
Common pitfall: Using latency when the question asks for throughput, or forgetting that cache capacity normally refers to data storage rather than tag and control bits unless stated otherwise.
Quick example: With an ideal k-stage pipeline, the first instruction takes k cycles and each later instruction completes one cycle apart. Stalls and branch penalties reduce that ideal throughput.
Programming and Data Structures
Trace programs precisely and choose structures according to the operations they must support.
A data structure is best understood through its invariants and supported operations. A binary-search tree orders keys, a heap orders each parent relative to its children, and a hash table maps keys to candidate locations. In C questions, values, addresses and object lifetimes must be tracked separately, especially through pointer arithmetic and recursive calls.
- C programming, recursion, pointers and parameter passing
- Arrays, linked lists, stacks, queues, trees and heaps
- Hashing and asymptotic cost of common operations
Question method: Trace code with a table containing the current statement, variable values and changed memory locations. When comparing structures, write the required operations—search, insert, delete, minimum or traversal—and compare both average and worst-case costs.
Common pitfall: Assuming a binary tree is automatically a binary-search tree, or quoting average hash-table performance when the question asks for the worst case.
Quick example: A stack implements last-in, first-out order. Depth-first search can therefore use an explicit stack, while breadth-first search needs a queue to preserve discovery order.
Algorithms
Analyse correctness and running time before selecting a design technique.
Algorithm analysis separates correctness from efficiency. A loop invariant or induction argument explains why an algorithm returns the right result; a count or recurrence estimates its cost. Greedy algorithms commit to a locally best choice and therefore need an exchange or cut argument, whereas dynamic programming stores solutions to overlapping subproblems.
- Asymptotic notation and recurrence relations
- Searching, sorting, hashing and graph traversal
- Greedy methods, dynamic programming, divide-and-conquer and complexity classes
Question method: Identify the input-size variable and the operation being counted before simplifying. For graph algorithms, note whether the graph is directed, weighted or contains negative edges; these properties determine which algorithm is valid.
Common pitfall: Dropping a logarithmic factor too early, or selecting a shortest-path algorithm without checking for negative edge weights.
Quick example: Binary search satisfies T(n) = T(n/2) + Θ(1), so it takes Θ(log n) time. This requires random access to a sorted search space.
Theory of Computation and Compiler Design
Connect language classes with machines, then follow how source code becomes executable form.
The language hierarchy links restrictions on memory with expressive power: finite automata have finite control, pushdown automata add a stack, and Turing machines have unrestricted tape memory. Compiler questions follow a separate but related pipeline from characters to tokens, syntax trees, intermediate code and target code. Each stage consumes a particular representation and reports a different class of error.
- Regular languages, finite automata and regular expressions
- Context-free grammars, pushdown automata, decidability and reductions
- Lexical analysis, parsing, syntax-directed translation and runtime environments
Question method: For automata, test short accepted and rejected strings before constructing states. For grammars, separate ambiguity from left recursion. For parsing, compute FIRST and FOLLOW sets systematically rather than guessing table entries.
Common pitfall: Claiming that every non-regular language is context-free, or confusing a lexical error with a syntactically invalid token sequence.
Quick example: A DFA has exactly one transition for every state-symbol pair. An NFA may have several choices, but both recognise exactly the regular languages.
Operating Systems
Reason about concurrent execution, resource allocation, memory and persistent storage.
Operating systems coordinate independent activities while preserving isolation and progress. Scheduling determines when work runs, synchronization determines which interleavings are safe, and virtual memory determines how an address is translated and protected. Most numerical questions become simpler when the event sequence is written explicitly instead of handled mentally.
- Processes, threads, scheduling and inter-process communication
- Concurrency, semaphores, monitors and deadlocks
- Paging, virtual memory, file systems and disk scheduling
Question method: Build a Gantt chart for scheduling and calculate each process's completion, turnaround and waiting time from it. For paging, split the virtual address into page number and offset, then apply TLB and page-table access costs in the stated order.
Common pitfall: Mixing response time with waiting time, or assuming that mutual exclusion alone guarantees freedom from deadlock and starvation.
Quick example: A deadlock requires mutual exclusion, hold-and-wait, no pre-emption and circular wait together. Breaking any one of these necessary conditions prevents deadlock.
Databases
Model data cleanly and predict the correctness and cost of queries and transactions.
Database design moves from real-world constraints to relations, keys and dependencies. Normalization removes redundancy by decomposing relations while aiming to preserve information and useful dependencies. At runtime, transactions must appear correct despite interleaving, failures and concurrent reads, which is why serializability and recoverability are distinct checks.
- ER modelling, relational algebra, tuple calculus and SQL
- Functional dependencies, keys and normalization
- Indexing, transactions, serializability and recovery
Question method: Compute attribute closures before naming keys or normal forms. For SQL, create a tiny table including duplicates and NULL values. For schedules, draw the precedence graph with one node per transaction and one edge per conflicting order.
Common pitfall: Treating NULL as an ordinary value, forgetting SQL's bag semantics, or assuming every dependency-preserving decomposition is automatically lossless.
Quick example: For relation R(A,B,C) with A → B and B → C, A is a candidate key because A+ contains A, B and C. The dependency B → C can still create a transitive dependency.
Computer Networks
Track data across layers and calculate addressing, reliability and routing behaviour.
Networking questions become clearer when each responsibility is assigned to a layer. Link protocols move frames over one hop, IP forwards packets across networks, and transport protocols provide process-to-process communication. Delay combines transmission, propagation, processing and queuing components; only the first two are usually calculable from link rate, packet length and distance.
- Layering, Ethernet, switching and error detection
- IPv4 addressing, subnetting, routing and fragmentation
- TCP/UDP, congestion control, DNS, HTTP and application protocols
Question method: Write addresses in binary around the prefix boundary for subnet questions. For protocol traces, draw the communicating endpoints and number each message. For delay calculations, keep bits, bytes, seconds and metres consistent.
Common pitfall: Confusing transmission delay with propagation delay, or counting network and broadcast addresses as ordinary IPv4 hosts.
Quick example: A /26 IPv4 subnet leaves six host bits: 64 total addresses and normally 62 usable host addresses after reserving network and broadcast addresses.