Previous year questions

GATE PYQs, re-checked

Questions from your GeeksforGeeks PYQ book, one section at a time. Every answer has been re-derived by me (compiled and run, simulated, or reasoned and labelled); where I disagree with the book's key it is flagged.

Concepts with PYQs

• Cache memory mapping42
• CPU scheduling: criteria, FCFS, SJF and SRTF26
• Cache performance and multilevel caches23
• Analysing loops, time and space22
• Spanning trees and the cut property21
• Pipeline speedup and CPI calculations21
• Nested queries, views and NULL21
• Solving recurrences: substitution, tree and Master theorem20
• Binary heaps and heap operations19
• Sliding window: stop-and-wait, Go-Back-N, Selective Repeat19
• IPv4 header and fragmentation18
• 1NF to BCNF18
• Schedules, conflict and view serializability18
• Decidable and recognisable languages18
• Phases of a compiler17
• TCP: segments, handshake and teardown17
• Relational algebra17
• Page replacement algorithms17
• Context-free grammars and derivations17
• BFS and DFS16
• B+ trees16
• Semaphores16
• Layering: OSI and TCP/IP15
• Forwarding, stalls and branch prediction15
• Addressing modes15
• Disk structure and access time15
• Boolean algebra and identities15
• Closure properties of regular languages15
• CIDR and subnetting14
• Structural, data and control hazards14
• DFA minimisation14
• Recursion patterns13
• Joins, grouping and aggregates13
• Sign-magnitude, 1's and 2's complement13
• Number systems and conversion13
• Synchronous and asynchronous counters13
• Deadlock avoidance and the Banker's algorithm13
• Asymptotic notation12
• Binary search trees12
• Interrupts and vectoring12
• Counting binary trees12
• IPv4 addressing and classful addressing11
• Instruction formats and expanding opcodes11
• Pumping lemma for regular languages11
• Regex to automata and back11
• Chomsky hierarchy11
• Pumping lemma for CFLs11
• DFS edge types, topological sort and SCC10
• TCP congestion control10
• Binary tree traversals10
• Relational model and keys10
• Multiplexers and demultiplexers10
• Priority and round robin scheduling10
• TLB and effective access time10
• Paging and address translation10
• Multilevel, inverted and hashed page tables10
• NFA and epsilon-NFA10
• Kruskal and Prim9
• Recursion and the call stack9
• Functions and parameter passing9
• Arrays, strings and pointers together9
• Delay, throughput and bandwidth-delay product9
• Medium access: ALOHA, CSMA and CSMA/CD9
• Queue (abstract data type)9
• Chaining and open addressing9
• Functional dependencies and closure9
• Finding candidate keys9
• Tuple relational calculus9
• Joins, division and expression trees9
• Deadlock: conditions and resource allocation graphs9
• Virtual memory and demand paging9
• Deterministic versus nondeterministic PDA9
• Data types, operators and expressions8
• Scope, lifetime and storage classes8
• Pointers and pointer arithmetic8
• Top-down parsing and LL(1)8
• Ambiguity, left recursion and left factoring8
• Distance vector routing8
• HTTP8
• Memory interfacing and address decoding8
• Direct memory access8
• Ordered, primary, clustering and secondary indexes8
• Threads and multithreading models8
• Critical section and race conditions8
• File allocation methods and inodes8
• Disk scheduling8
• Regular expressions8
• Closure properties of CFLs8
• Linear and binary search7
• Quicksort7
• Dijkstra's algorithm7
• LCS, edit distance, knapsack and matrix chain7
• ICMP, ARP and DHCP (supporting)7
• RIP, OSPF and BGP overview7
• Socket API7
• Linked list operations7
• Stack (abstract data type)7
• Lossless join and dependency preservation7
• File organisation and blocking factor7
• Adders and subtractors7
• Latches and flip-flops7
• Control flow and loops6
• Lexical analysis6
• LR(0) and SLR(1) construction6
• Shift-reduce parsing and handles6
• CLR(1) and LALR(1)6
• Parser power hierarchy and conflicts6
• Circuit, packet and virtual-circuit switching6
• Ethernet, frames and minimum frame size6
• Switches, learning bridges and VLANs6
• UDP and ports6
• DNS6
• Instruction set architecture and formats6
• Instruction cycle6
• Cache replacement and write policies6
• Constructing a tree from its traversals6
• ER model6
• SQL: DDL and basic queries6
• Transactions and ACID6
• Two-phase locking and its variants6
• Recoverable, cascadeless and strict schedules6
• Logic gates and universal gates6
• Process states, fork and exec6
• Deterministic finite automata6
• DFA design patterns and counting states6
• Pushdown automata6
• Rice's theorem6
• Halting problem and reductions6
• Divide and conquer5
• Merge sort5
• Bubble, selection and insertion sort5
• Bellman-Ford5
• Huffman coding5
• DP on sequences: LIS and coin change5
• Arrays and indexing5
• Multidimensional arrays and address calculation5
• FIRST and FOLLOW sets5
• Operator precedence parsing5
• Basic blocks and control flow graphs5
• Liveness analysis5
• Code generation and register allocation (outside syllabus, used in the journey)5
• Intermediate code generation5
• ER to relational mapping5
• Karnaugh maps5
• Decoders, encoders and comparators5
• Context switching5
• Process model and PCB5
• I/O subsystem, buffering and spooling5
• Peterson, Dekker and software solutions5
• Subset construction5
• Decision problems for CFLs5
• Dynamic programming and memoization4
• Local optimisation4
• Runtime environments and activation records4
• Storage organisation: static, stack and heap4
• Syntax-directed definitions: synthesized and inherited attributes4
• S-attributed, L-attributed and evaluation orders4
• Translation schemes and semantic actions4
• Three-address code, quadruples and triples4
• Error detection: parity, checksum and CRC4
• Single-bus datapath and register transfer4
• I/O interface and programmed I/O4
• Singly linked lists4
• Multiplication: shift-add and Booth4
• Registers and shift registers4
• Producer-consumer, readers-writers, dining philosophers4
• Mealy and Moore machines4
• Heap sort3
• Divide and conquer applications3
• Greedy method and exchange argument3
• C memory layout: text, data, heap, stack3
• Link state routing3
• Instruction pipelining3
• Trees and binary trees3
• Hashing: functions and collisions3
• Load factor and expected probes3
• Integrity constraints and triggers3
• Safe expressions and domain calculus3
• Log-based recovery and checkpoints3
• Timestamp ordering3
• IEEE 754 floating point3
• SOP, POS, minterms and maxterms3
• FSM design: Mealy and Moore3
• System calls and kernel mode3
• Test-and-set, swap and atomic instructions3
• Deadlock detection and recovery3
• Memory management: partitioning and fragmentation3
• Alphabets, strings and languages3
• Myhill-Nerode theorem3
• Floyd-Warshall2
• Activity selection and fractional knapsack2
• Evaluation order, sequence points and undefined behaviour2
• Available expressions and common sub-expression elimination2
• Hamming code (error correction)2
• TCP flow control2
• Performance: CPI, MIPS and Amdahl's law2
• Procedure calls and stack frames in hardware2
• Microprogrammed control unit2
• Stack applications: expression evaluation and matching2
• AVL trees and rotations2
• Canonical cover and 3NF synthesis (page not built yet)2
• Hash-based file organisation (page not built yet)2
• B trees2
• Design of combinational circuits2
• Multilevel queues and real-time scheduling2
• Thrashing and the working set2
• Decision problems for regular languages (page not built yet)2
• TM variants and the Church-Turing thesis2
• Ambiguity in grammars2
• Stability, in-place and comparison of sorts1
• Graph representations1
• Structures, unions and memory alignment (page not built yet)1
• Function pointers (page not built yet)1
• Bottom-up parsing and LR1
• Translating expressions and control flow, backpatching1
• DAG representation of basic blocks1
• Network address translation1
• RTT estimation and retransmission timers (page not built yet)1
• RAM, ROM and DRAM refresh basics (page not built yet)1
• RISC versus CISC (page not built yet)1
• Hardwired control unit1
• Priority queues and building a heap1
• Floating-point arithmetic and precision1
• Fixed-point arithmetic and overflow1
• BCD, Gray and parity codes (page not built yet)1
• Tabular method (Quine-McCluskey)1
• Static and dynamic hazards in logic (page not built yet)1
• Functional completeness and duality (page not built yet)1
• ROM, PLA and PAL (page not built yet)1
• Excitation tables and flip-flop conversion1
• Process address space1
• Free-space management and file system performance (page not built yet)1
• File systems: concepts and directories1
• Simplification, CNF and GNF1

56 questions where my answer and the book's key differ or the question is unclear: Q21 (Greedy method); Q36 (Greedy method); Q4 (Dynamic programming); Q8 (Dynamic programming); Q15 (Control flow statement); Q4 (Function); Q5 (Function); Q42 (Function); Q18 (Array); Q14 (Lexical analysis); Q22 (Syntax analyzer); Q6 (Syntax directed translation); Q21 (Intermediate code generation); Q22 (Intermediate code generation); Q27 (Data link layer); Q28 (Data link layer); Q40 (Data link layer); Q41 (Data link layer); Q42 (Data link layer); Q64 (TCP); Q78 (TCP); Q81 (TCP); Q85 (TCP); Q20 (Application layer); Q15 (Pipelining); Q26 (Pipelining); Q6 (Machine instructions and addressing modes); Q23 (Machine instructions and addressing modes); Q42 (Cache memory); Q17 (Secondary memory and I/O organization); Q12 (Stack and queue); Q1 (Structured query language); Q21 (Structured query language); Q25 (Structured query language); Q31 (Structured query language); Q32 (Structured query language); Q18 (File organization and indexing); Q13 (Transaction and concurrency control); Q33 (Transaction and concurrency control); Q16 (Number system); Q2 (Logic gates); Q7 (Sequential circuit); Q17 (Sequential circuit); Q18 (Sequential circuit); Q19 (Sequential circuit); Q21 (Sequential circuit); Q22 (Sequential circuit); Q23 (Sequential circuit); Q16 (Deadlocks); Q33 (Memory management and virtual memory); Q15 (File system and IO scheduling); Q61 (Regular language and finite automata); Q76 (Regular language and finite automata); Q19 (Context free language and context free grammar); Q42 (Context free language and context free grammar); Q46 (Context free language and context free grammar).