I85PREP
⌘ K
GATE CS study materials
GATE CS study resources

GATE CS: GATE Computer Science and Information Technology (CS): Scoring the Core

GATE CS · Work through your exam, one topic at a time.

All guide sections

GATE Computer Science and Information Technology (CS): Scoring the Core

GATE CS is one three-hour computer-based paper of 65 questions and 100 marks. General Aptitude supplies 15 marks; the Computer Science and Information Technology portion supplies 85, and roughly 25 questions are worth 1 mark while 30 are worth 2. The syllabus runs across Engineering Mathematics, Digital Logic, Computer Organization and Architecture, Programming and Data Structures, Algorithms, Theory of Computation, Compiler Design, Operating Systems, Databases, and Computer Networks. Most marks are won by exact computation and precise definitions, not by broad recall.

Rules that decide marks

  • Marking: a wrong MCQ costs 1/3 mark (1-mark question) or 2/3 mark (2-mark question). Numerical Answer Type (NAT) and Multiple Select Questions carry no negative marking, so a NAT should never be left blank.
  • Recurrences: apply the Master Theorem only after checking its regularity condition; otherwise expand a recursion tree.
  • Theory of Computation: DFA and NFA are equivalent in power; emptiness and equivalence are decidable for regular languages, while ambiguity of a context-free grammar is undecidable.
  • Databases: find candidate keys from the closure of attribute sets, then test a decomposition for losslessness (chase/joint test) and dependency preservation separately.
  • Networks: subnet arithmetic in CIDR plus TCP congestion-window growth are recurring 2-mark items.

Worked example

Solve T(n) = 2T(n/2) + n log n, with T(1) = 1. Here a = 2, b = 2, so n^(log_b a) = n. The driving function f(n) = n log n is larger than n by a factor of log n, which is not a constant, so the basic second case of the Master Theorem (which gives Θ(n log n) only when f(n) = Θ(n)) does not apply directly. Using the extended second case with k = 1 gives Θ(n log^(k+1) n) = Θ(n log² n). Check with a recursion tree: level i holds 2^i nodes each costing (n/2^i) log(n/2^i), so the level total is n(log n − i); summing i from 0 to log n gives n · Θ(log² n).

Traps

  • Dropping the log factor and answering Θ(n log n) instead of Θ(n log² n).
  • Confusing O, Ω and Θ; a question asking for the tightest bound is not asking which statement is merely true.
  • Attributing Belady's anomaly to LRU or OPT - it belongs to FIFO page replacement.
  • Ticking plausible but unprovable options in an MSQ; a partially correct selection scores zero.
  • Ignoring units and floor/ceiling behaviour in counting questions (distinct binary trees, onto functions, register counts).