GATE Computer Science & IT

How this paper is marked

The scored paper in the app is marked as MCQ. A correct answer is worth 1. A wrong answer costs -0.3333.

Computer Architecture

Instruction sets, pipelining, cache and the memory hierarchy

• ISA and CPU TimeThe hardware contract: what an instruction is, how it names operands, and the three levers of CPU time.
• Instruction PipeliningOverlap fetch, decode, execute, memory and write-back; hazards that stall that overlap; speedup versus a non-pipelined machine.
• Cache and the Memory HierarchyWhy caches work, where a block may live, and how to average the cost of a hit and a miss.
• Input, Output and DMAHow the CPU talks to devices: polling, interrupts, DMA, and the same LOAD aimed at a device register.

Databases

Relational model, SQL, normalization, transactions and indexing

• Entities, Relationships and TablesFrom a campus-shop ER sketch to the three tables a relational database actually stores.
• Relations, Keys and Basic SQLWhat a relation is, how keys name a row, relational algebra, and SELECT/WHERE on one campus-shop table.
• SQL Joins, Groups and NULLJoin the campus-shop tables, group sales, and handle missing values in SQL.
• Functional Dependencies and First Normal FormFDs, attribute closure, candidate keys and atomic cells — the rules that make the campus-shop tables split later.
• Second, Third and Boyce–Codd FormSplit the campus-shop leftovers: partial FDs, transitive wardens, and BCNF determinants.
• Transactions, Accidents and RecoveryACID on one sale, dirty/lost/phantom accidents, conflict serializability and write-ahead logging.
• Isolation Levels and LockingWhich accidents a kiosk session may still see, from READ UNCOMMITTED to SERIALIZABLE, and how 2PL implements the stronger ones.
• Indexing and B+ TreesClustered versus secondary indexes and B+ trees that find a campus-shop sale without a full scan.

Computer Networks

TCP/IP, addressing, routing and application protocols

• Layers and How a Connection OpensOSI versus TCP/IP layering, TCP versus UDP, the three-way open and four-way close, and the header bytes that name ports.
• TCP Flow and Congestion ControlReceiver window versus congestion window, sliding-window throughput, slow start and AIMD after loss.
• IP Addressing, CIDR and NATIPv4 addressing, subnetting with CIDR, fragmentation, and support protocols like ARP, DHCP and NAT.
• How a Packet Finds a PathRoutes as next hops, distance-vector Bellman-Ford, count-to-infinity, and link-state Dijkstra.
• DNS, HTTP and MailDNS resolution and records, HTTP/HTTPS, well-known ports, and the SMTP send versus POP3/IMAP pull split.

Operating Systems

Processes, system calls, threads, synchronization, deadlocks, CPU scheduling, memory, page replacement, filesystems and disk scheduling

• Processes and the PCBWhat a process is, the five states, the PCB, context switches, multiprogramming and how two processes exchange data.
• System calls and the process APIUser versus kernel mode, the trap that is a system call, and fork / wait / exit.
• ThreadsThreads share a process's address space; user-level versus kernel-level scheduling.
• SynchronizationRaces, the critical-section properties, Peterson's two-process lock, semaphores and monitors.
• DeadlocksCoffman conditions, wait-for / resource-allocation graphs, Banker's algorithm and the minimum-units bound.
• CPU schedulingTurnaround, waiting and response, then FCFS, SJF, SRTF, Round Robin and priority on one three-job walk.
• Memory managementPaging, address translation, the TLB, demand paging and segmentation.
• Page replacementVictim choice under FIFO, LRU and Optimal, and Belady's anomaly.
• File systemsWhat a file is, contiguous / linked / indexed allocation, inodes and directories.
• Disk schedulingDisk access time and FCFS, SSTF, SCAN-family head movement.

System Design

Scalability, load balancing, caching, database scaling and CAP

• Growing past one boxHow CampusClip grows from one host to many — scale up versus out, a load balancer, CAP under a partition, and availability nines.
• Load vs capacityArrivals versus what a CampusClip host can finish — excess, utilisation, and QPS × payload.
• Latency vs throughputTime for one CampusClip open versus finishes per second, and Little's Law for in-flight work.
• CachingA fast copy of a CampusClip mapping — hits, write paths, staleness, and where the copy sits after scale-out.
• QueuesWork the CampusClip caller is not waiting on — bursts, producer/broker/consumer, back-pressure, and when not to queue.
• CampusClip walkThe two CampusClip paths — paste and redirect — with the store, key placement, and a sketch that uses only numbers the course already stated.

Data Structures & Algorithms

Arrays, Linked Lists, Trees, Graphs, Dynamic Programming & Time Complexity Analysis

• Arrays and StringsContiguous array storage, string manipulation, prefix sums and in place techniques.
• Hashing and Hash MapsHash tables, collision handling and using maps and sets for constant time lookups.
• Two Pointers and Sliding WindowTwo pointer traversal and sliding window techniques for subarray and substring problems.
• Linked ListsSingly and doubly linked lists, pointer manipulation, reversal and cycle detection.
• Stacks and QueuesLIFO stacks and FIFO queues with applications like expression parsing and monotonic stacks.
• Recursion and BacktrackingRecursive problem solving and backtracking to explore permutations, subsets and combinations.
• Graph Colouring by Backtrackingm-colouring as a search: assign each vertex a colour in 1..m, abandon a partial colouring the moment a neighbour clash appears. Distinct from the chromatic-number decision…
• Searching and SortingComparison sorts like merge and quick sort plus linear and non comparison sorts.
• Strassen Matrix MultiplicationDivide-and-conquer matrix multiply: why eight half-size products still cost $n^3$, Strassen's seven products, the $\Theta(n^{\log_2 7})$ recurrence, and when the extra additions…
• Convex HullThe smallest convex polygon containing a point set: Graham scan (polar sort plus left-turn stack), the CCW test, and the divide-and-conquer merge by common tangents.
• Binary SearchBinary search on sorted data and on answer spaces for optimization problems.
• Trees and GraphsBinary trees, binary search trees, traversals and graph representations with BFS and DFS.
• AVL TreesHeight-balanced binary search trees: balance factor, rotations, insert, delete and when an AVL beats a plain BST.
• B-TreesMulti-way search trees of order m: node occupancy, search, insert-with-split, delete-with-borrow-or-merge, and why disk indexes use them.
• Heaps and Priority QueuesBinary heaps and priority queues for efficient access to minimum or maximum elements.
• Dynamic ProgrammingSolving problems with overlapping subproblems using memoization and tabulation.
• Optimal Binary Search TreesChoose BST shape to minimise expected search cost: the $O(n^3)$ DP $e[i,j] = w[i,j] + \min_r\,(e[i,r-1]+e[r+1,j])$, filled by increasing span on a three-key instance.
• DP for the Travelling SalesmanHeld–Karp optimisation TSP: state (S, j) is the cheapest path from city 1 through exactly the cities in S ending at j, in $O(n^2 2^n)$ — the shortest tour, not the NPC decision…
• Greedy AlgorithmsMaking locally optimal choices to reach a global optimum for suitable problems.
• Job Sequencing with DeadlinesOne machine, unit-time jobs, each with a deadline and a profit: sort by profit and place each job in the latest free slot that still meets its deadline.
• Advanced Graph AlgorithmsShortest path, minimum spanning tree and topological sort algorithms on weighted graphs.
• Branch and BoundState-space search with live nodes, bounding functions, 0/1 knapsack and the travelling-salesman decision to prune.
• Time and Space ComplexityAsymptotic analysis with Big O notation for time and space, including recurrence solving.
• P, NP and NP-CompletenessDecision versus optimisation, the classes P, NP, NP-hard and NP-complete, polynomial reductions, and Cook's theorem.
• NP-Complete Graph ProblemsClique, chromatic-number and TSP as decision problems, the complement reduction between clique and independent set, and what NP-completeness licenses.
• NP-Hard SchedulingIdentical-processor makespan (2 machines ≡ PARTITION) and job-shop (named machines, per-job routes). Problem statements, one reduction you can finish by hand, and LPT as a…
• Bit ManipulationBitwise operations and tricks for masks, counting bits and set operations.

Previous year papers

• GATE Computer Science Previous Year Question PapersOfficial papers with provenance, free to read.