GATE CS Subject Notes
GATE Computer Science subject deep-dives: DBMS, CN, OS, TOC, DSA, COA concepts with the exam angle.
20 articles in this topic
B+ Trees and Database Indexing: why indexes are fast, with a worked insert
B+ trees and database indexing explained: dense vs sparse, primary clustering and secondary indexes, B-tree vs B+ tree, with a worked B+ tree insert example.
Process Synchronization and Semaphores: race conditions, Peterson's solution, wait and signal
Process synchronization explained: the race condition, critical-section problem, Peterson's solution, binary and counting semaphores, and a worked trace.
Memory Hierarchy and Virtual Memory: paging, the TLB, and address translation
Memory hierarchy and virtual memory explained: registers to disk, locality, paging, page tables, the TLB, a worked address translation, and access time.
SQL Queries and Joins in DBMS: sublanguages, joins, and GROUP BY worked out
SQL queries and joins in DBMS: DDL DML DCL TCL sublanguages, SELECT and WHERE, inner and outer joins, GROUP BY with HAVING, plus a worked join example.
Transactions and concurrency control in DBMS: ACID, schedules, serializability
Transactions in DBMS explained: ACID properties, schedules, conflict serializability with a worked precedence graph, two-phase locking, and the exam angle.
Normalization in DBMS: 1NF to BCNF, with the exam angle
Normalization in DBMS explained: functional dependencies, the exact 1NF, 2NF, 3NF and BCNF rules, a worked decomposition of one relation, and 3NF vs BCNF.
Pipelining in Computer Architecture: the 5-stage pipeline, speedup, and hazards
Pipelining in computer architecture: the 5-stage pipeline, speedup and throughput formulas, CPI, structural, data and control hazards, and forwarding.
Dynamic Programming Explained: optimal substructure and a worked knapsack
Dynamic programming explained: optimal substructure, overlapping subproblems, memoization vs tabulation, and a fully worked 0/1 knapsack DP table example.
Sorting Algorithms Compared: complexity, stability, and the n log n lower bound
Sorting algorithms compared: bubble, insertion, selection, merge, quick and heap sort with best, average and worst time, stability, and the n log n bound.
Graph Algorithms: BFS, DFS, and shortest paths worked out
Graph algorithms explained: adjacency matrix vs list, BFS and DFS traversal order, edge classification, topological sort, and Dijkstra shortest paths.
Turing Machines and Decidability: recursive vs RE, and the halting problem
Turing machines and decidability explained: TM definition and configurations, recursive vs recursively enumerable languages, the halting problem, reductions.
Context-Free Grammars and Pushdown Automata: CFGs, PDAs, and a worked example
Context-free grammars and pushdown automata explained: derivations, ambiguity, CNF and GNF, PDA acceptance modes, the pumping lemma, and a worked example.