The Ultimate GATE CS Cheatsheet

# Fundamental Equivalences
Commutative:   P ∧ Q ≡ Q ∧ P          P ∨ Q ≡ Q ∨ P
Associative:   P ∧ (Q ∧ R) ≡ (P ∧ Q) ∧ R
Distributive:  P ∧ (Q ∨ R) ≡ (P ∧ Q) ∨ (P ∧ R)
De Morgan's:   ¬(P ∧ Q) ≡ ¬P ∨ ¬Q    ¬(P ∨ Q) ≡ ¬P ∧ ¬Q
Implication:   P → Q ≡ ¬P ∨ Q
Contrapositive: P → Q ≡ ¬Q → ¬P
Biconditional: P ↔ Q ≡ (P → Q) ∧ (Q → P)

# Tautology & Contradiction
P ∨ ¬P  ≡ T  (Tautology / Law of Excluded Middle)
P ∧ ¬P  ≡ F  (Contradiction)

# Resolution Principle
(P ∨ Q) ∧ (¬P ∨ R) ⊢ (Q ∨ R)

# Quantifiers
∀x P(x) — "For all x, P(x) is true"
∃x P(x) — "There exists x such that P(x) is true"

# Negation Rules
¬∀x P(x) ≡ ∃x ¬P(x)
¬∃x P(x) ≡ ∀x ¬P(x)

# Nested Quantifiers
∀x ∀y P(x,y) ≡ ∀y ∀x P(x,y)
∀x ∃y P(x,y) ≢ ∃y ∀x P(x,y)  ← Order matters!

# Important
∃x ∀y P(x,y) → ∀y ∃x P(x,y)   (Valid implication)

# Set Operations
|A ∪ B| = |A| + |B| − |A ∩ B|              (Inclusion-Exclusion)
|A ∪ B ∪ C| = |A| + |B| + |C| − |A∩B| − |A∩C| − |B∩C| + |A∩B∩C|

# Pigeonhole Principle
If n items into m containers (n > m), at least one container has ⌈n/m⌉ items.

# Permutations & Combinations
P(n,r) = n! / (n−r)!          Arrangements (order matters)
C(n,r) = n! / [r!(n−r)!]     Selections (order doesn't matter)
nPr = nCr × r!

# Binomial Theorem
(x + y)^n = Σ C(n,k) × x^k × y^(n−k),  k = 0 to n

# Key Properties
Euler Circuit  — every vertex has even degree
Euler Path     — exactly 0 or 2 vertices with odd degree
Hamiltonian    — visits every vertex exactly once (NP-complete)

# Handshaking Lemma
Σ deg(v) = 2 × |E|   (Sum of all degrees = 2 × edges)

# Planarity
Euler's formula for planar graphs: V − E + F = 2
Kuratowski's: A graph is planar iff no K₅ or K₃,₃ subdivision
For planar: E ≤ 3V − 6  (V ≥ 3)
For planar bipartite: E ≤ 2V − 4

# Graph Coloring
χ(G) ≤ Δ(G) + 1   (χ = chromatic number, Δ = max degree)
Bipartite → 2-colorable  iff  no odd-length cycle
Planar graph → 4-colorable (Four Color Theorem)

# Trees
Tree: connected graph with V − 1 edges
Spanning tree: V − 1 edges, no cycles
Minimum Spanning Tree: Kruskal / Prim
Binary tree with n nodes: height ≥ ⌊log₂n⌋

# Master Theorem: T(n) = aT(n/b) + Θ(n^k × log^p n)
Compare f(n) = n^k × log^p(n) with n^(log_b a)

Case 1: f(n) << n^(log_b a)  →  T(n) = Θ(n^(log_b a))
Case 2: f(n) ≈ n^(log_b a)   →  T(n) = Θ(n^(log_b a) × log^(p+1) n)
Case 3: f(n) >> n^(log_b a)  →  T(n) = Θ(f(n))
  (Case 3 needs: a·f(n/b) ≤ c·f(n) for some c < 1)

# Common Recurrences
T(n) = 2T(n/2) + O(n)     → O(n log n)     [Merge sort]
T(n) = T(n/2) + O(1)      → O(log n)       [Binary search]
T(n) = 2T(n/2) + O(1)     → O(n)           [Tree traversal]
T(n) = 2T(n/2) + O(n²)    → O(n²)
T(n) = T(n-1) + O(n)      → O(n²)          [Selection sort]

# Hash Functions
Division:   h(k) = k mod m    (m should be prime)
Multiplication: h(k) = ⌊m × (k × A mod 1)⌋    (A ≈ 0.618)

# Collision Resolution
Open Addressing (Probing):
  Linear:     h(k,i) = (h′(k) + i) mod m       → Clustering!
  Quadratic:  h(k,i) = (h′(k) + c₁i + c₂i²) mod m
  Double:     h(k,i) = (h₁(k) + i × h₂(k)) mod m

Separate Chaining: each slot → linked list
  Load factor α = n/m  (avg chain length)
  Search: O(1 + α) avg case

# Load Factor Thresholds (Open Addressing)
  α < 0.5 recommended for linear probing
  α < 0.7 for quadratic probing
  α < 0.9 for double hashing

# Binary Search Tree (BST)
  Search / Insert / Delete: O(h)  where h = height
  Best case h = log n,  Worst case h = n (skewed)

# AVL Tree (Self-balancing BST)
  Balance Factor: BF = height(left) − height(right)
  Valid range: BF ∈ {−1, 0, 1}
  Rotations: LL, RR, LR, RL
  Height: ⌊1.44 × log₂ n⌋  (tighter bound)

# Red-Black Tree
  Properties:
    1. Every node is RED or BLACK
    2. Root is BLACK, Leaves (NIL) are BLACK
    3. RED node → children are BLACK
    4. Same # of BLACK nodes on all paths (BLACK-HEIGHT)
  Height: ≤ 2 × log₂(n+1)

# B-Tree of order m
  Max keys: m−1, Min keys: ⌈m/2⌉−1
  Max children: m, Min children: ⌈m/2⌉
  Height: O(log_m n)
  Search: O(log n)  [disk access = height]

# Heap
  Max-Heap: parent ≥ children (root = maximum)
  Min-Heap: parent ≤ children (root = minimum)
  Build heap: O(n)  [NOT O(n log n)]
  Extract-Max/Insert: O(log n)

# Common DP Problems & Recurrence

Fibonacci:     dp[i] = dp[i−1] + dp[i−2]
0/1 Knapsack:  dp[i][w] = max(dp[i−1][w], val[i] + dp[i−1][w−wt[i]])
Unbounded KS:  dp[i][w] = max(dp[i−1][w], val[i] + dp[i][w−wt[i]])
LCS:           dp[i][j] = dp[i−1][j−1]+1  if s1[i]=s2[j]
                 = max(dp[i−1][j], dp[i][j−1])  otherwise
LIS:           dp[i] = 1 + max(dp[j]) for all j < i and arr[j] < arr[i]
Edit Distance: dp[i][j] = dp[i−1][j−1]           if s1[i]=s2[j]
                 = 1 + min(dp[i−1][j], dp[i][j−1], dp[i−1][j−1])
Matrix Chain:  dp[i][j] = min(dp[i][k] + dp[k+1][j] + dims[i-1]*dims[k]*dims[j])
Coin Change:   dp[i] = min(dp[i], 1 + dp[i−coin])  for each coin
Subset Sum:    dp[i][j] = dp[i−1][j] or dp[i−1][j−arr[i]]

# DP Optimization Techniques
  1. Knuth Optimization — O(n²) → O(n log n) for C[i][j] monotone
  2. Divide & Conquer — optimal point is monotone
  3. Convex Hull Trick — linear function optimization

# Process Metrics
Turnaround Time (TAT) = Completion Time − Arrival Time
Waiting Time (WT) = TAT − Burst Time
Response Time (RT) = First CPU Time − Arrival Time

# Round Robin
  Context switches = total bursts / quantum q
  If q → ∞, RR becomes FCFS
  If q → 1, RR approximates SJF (for unit bursts)

# Gantt Chart Example (SJF):
  P1(BT=6), P2(BT=2), P3(BT=1) — all arrive at 0
  Order: P3 → P2 → P1
  Avg WT = (0 + 1 + 3) / 3 = 1.33

# CPU Utilization
  CPU Util = 1 − (IO burst time / CPU burst time)

# Classical Problems

Producer-Consumer (bounded buffer):
  mutex = 1, empty = n, full = 0
  Producer: wait(empty); wait(mutex); produce; signal(mutex); signal(full)
  Consumer: wait(full); wait(mutex); consume; signal(mutex); signal(empty)

Readers-Writers (readers preference):
  mutex = 1, wrt = 1, readcount = 0
  Reader:  wait(mutex); readcount++; if(readcount==1) wait(wrt); signal(mutex); read;
           wait(mutex); readcount--; if(readcount==0) signal(wrt); signal(mutex)
  Writer:  wait(wrt); write; signal(wrt)

Dining Philosophers:
  Solution: pick lower-numbered fork first
  OR: allow at most n-1 philosophers to eat simultaneously

# Semaphores
  Binary semaphore (mutex): value ∈ {0, 1}
  Counting semaphore: value ∈ {0, 1, 2, ...n}
  wait(S) / P(S): while S≤0: wait; S--;
  signal(S) / V(S): S++;

# Critical Section Requirements
  Mutual Exclusion, Progress, Bounded Waiting

# Paging
  Physical Address = Frame_number × Frame_size + Offset
  Page table size = Number_of_pages × Entry_size
  Number_of_pages = Virtual_address_space / Page_size
  Number_of_frames = Physical_memory / Frame_size

  Multi-level paging:
  2-level: 10+10+12 bits → 1024 outer PT entries, 1024 inner, 4KB page
  TLB hit ratio h:
    EAT = h × (TLB + memory) + (1−h) × (TLB + 2 × memory)

# Segmentation
  Address = Segment_number × Max_segment_size + Offset
  External fragmentation possible (internal fragmentation in paging)

# Belady's Anomaly
  More frames → more page faults!
  Occurs with FIFO (does NOT occur with LRU, Optimal)

# Page Replacement
  FIFO: First In First Out
  LRU: Least Recently Used — optimal approximation of optimal
  Optimal (MIN): Replace page not used for longest future time
  Clock / Second Chance: Circular, reference bit

# Thrashing
  When a process spends more time paging than executing
  Solution: increase degree of multiprogramming
  Working Set Model: maintain pages accessed in last Δ references

# Necessary Conditions (ALL must hold)
  1. Mutual Exclusion    2. Hold & Wait
  3. No Preemption       4. Circular Wait

# Detection (Single Instance — using Wait-For Graph)
  If cycle exists in WFG → Deadlock!

# Detection (Multi-Instance — using Available/Allocation matrices)
  For each process:
    Finish[i] = false initially
    If Allocation[i] ≤ Work → Work += Allocation[i]; Finish[i] = true
  Repeat until no change. If any Finish[i]=false → Deadlock.

# Banker's Algorithm (Avoidance)
  Safe state: exists sequence where all processes can complete
  Need[i] = Max[i] − Allocation[i]
  Request[i] ≤ Need[i] AND Request[i] ≤ Available
  Then tentatively allocate and check for safe state

# Prevention Strategies
  Eliminate one condition:
    - Circular wait: order resource numbers
    - Hold & Wait: request all at once OR release before new request

# Fundamental Operations
σ_{condition}(R)        Selection — filter rows
π_{attr1,attr2}(R)      Projection — select columns
R ∪ S                   Union (same schema)
R ∩ S                   Intersection
R − S                   Set Difference
ρ_{new}(R)              Rename
R × S                   Cartesian Product

# Derived Operations
R ⋈_{cond} S            Natural Join ( equi-join on common attrs )
R ⟕ S                   Left Outer Join (all tuples from R)
R ⟗ S                   Full Outer Join

# Division
R ÷ S — tuples in R matching ALL tuples in S
  For "find students who took ALL courses"

# Aggregate Functions
𝒢_{group_attr} _{agg_func}(R)
  SUM, AVG, COUNT, MIN, MAX
  COUNT(*) counts all rows, COUNT(attr) counts non-null

-- Key SQL Operations
SELECT DISTINCT col1, agg(col2) AS alias
FROM table1 t1
  JOIN table2 t2 ON t1.id = t2.id
  LEFT JOIN table3 t3 ON t2.id = t3.id
WHERE condition
GROUP BY col1
HAVING agg(col2) > value
ORDER BY col1 ASC
LIMIT n;

-- ER to Relational Mapping
-- Strong Entity → Table (key attributes become primary key)
-- Weak Entity → Table (partial key + owner PK = composite PK)
-- 1:1 Relationship → Merge into either table (add FK)
-- 1:N Relationship → Add FK to N-side table
-- M:N Relationship → New table with composite PK from both sides

-- Total Participation → NOT NULL constraint on FK
-- Cardinality constraints are mapped as CHECK constraints

# ACID Properties
  Atomicity, Consistency, Isolation, Durability

# Transaction States
  Active → Partially Committed → Committed
  Active → Failed → Aborted

# Serializability
  Conflict Serializable: If precedence graph is acyclic
  View Serializable:    If initial read, updated read, final write same

# Isolation Levels
  Read Uncommitted → Dirty reads possible
  Read Committed   → No dirty reads
  Repeatable Read  → No non-repeatable reads
  Serializable     → Full isolation (locks everything)

# Concurrency Control Protocols
  2PL (Two-Phase Locking):
    Growing phase (acquire locks) → Shrinking phase (release locks)
    Strict 2PL: hold all locks until commit/abort
    Rigorous 2PL: release all locks after commit only

  Timestamp Ordering (T/O):
    Read: TS(TS) ≥ W-timestamp(Q) → OK, else abort
    Write: TS(TS) ≥ R-timestamp(Q) AND TS(TS) ≥ W-timestamp(Q)

  Optimistic: Validate → Read → Write
  Deadlock-free but may restart transactions

# B+ Tree (most tested)
  Internal nodes: only keys (for routing)
  Leaf nodes: keys + data pointers
  Leaf nodes linked (range queries efficient)
  Order m:
    Internal node: ⌈m/2⌉ to m children, ⌈m/2⌉−1 to m−1 keys
    Leaf node: ⌈m/2⌉ to m key-pointer pairs

  Search: O(log n)
  Insert: Split at overflow
  Delete: Redistribution or Merge

# B Tree vs B+ Tree
  B Tree:  data in all nodes, no linked leaves
  B+ Tree: data only in leaves, leaves linked, better for range queries

# Indexing
  Dense Index: entry for every search key
  Sparse Index: entry for some search keys (block-level)

  Primary Index: ordered data file, sparse index on ordered key
  Clustering Index: ordered non-key field, dense index
  Secondary Index: non-ordered, dense index (pointer to data)

# Hash Index
  Static: fixed buckets, overflow chains
  Dynamic: extendible hashing, linear hashing

# IP Address Classes
  Class A:  0.0.0.0   – 127.255.255.255  |  /8   |  2^24 hosts
  Class B:  128.0.0.0 – 191.255.255.255  |  /16  |  2^16 hosts
  Class C:  192.0.0.0 – 223.255.255.255  |  /24  |  2^8  hosts
  Class D:  224–239 (Multicast)
  Class E:  240–255 (Reserved)

# CIDR Notation
  Subnet Mask bits / n → n bits for network, 32−n bits for host
  Usable hosts = 2^(32−n) − 2 (subtract network & broadcast)

# Subnetting Example
  192.168.1.0/24 → need 4 subnets
  Borrow 2 bits: /26
  Subnets: .0/26, .64/26, .128/26, .192/26 (64 hosts each, 62 usable)

# Special Addresses
  127.0.0.1        → Loopback
  0.0.0.0          → This network
  255.255.255.255  → Broadcast
  10.0.0.0/8       → Private (Class A)
  172.16.0.0/12    → Private (Class B)
  192.168.0.0/16   → Private (Class C)

# TCP 3-Way Handshake
  Client → Server: SYN (seq=x)
  Server → Client: SYN+ACK (seq=y, ack=x+1)
  Client → Server: ACK (seq=x+1, ack=y+1)

# TCP Window Size
  Throughput = Window Size / RTT
  Bandwidth-Delay Product = Bandwidth × RTT
  For full utilization: Window ≥ BDP

# TCP Congestion Control
  Slow Start:    cwnd doubles each RTT (exponential)
  Threshold:     ssthresh = cwnd/2 at first loss
  Congestion Avoidance: cwnd += 1/cwnd per ACK (linear, AIMD)
  Fast Retransmit: 3 duplicate ACKs → retransmit immediately
  Fast Recovery: cwnd = ssthresh (skip slow start)

# RTT Estimation
  RTT_ewma = α × RTT_sample + (1−α) × RTT_ewma   (α typically 0.875)
  DevRTT = β × |RTT_sample − RTT_ewma| + (1−β) × DevRTT
  RTO = RTT_ewma + 4 × DevRTT

# DNS Resolution
  1. Browser cache → 2. OS cache → 3. Local DNS resolver
  4. Root DNS → 5. TLD DNS → 6. Authoritative DNS
  Types of records:
    A:     IP address (IPv4)
    AAAA:  IP address (IPv6)
    CNAME: Canonical name (alias)
    MX:    Mail exchange
    NS:    Name server
    PTR:   Pointer (reverse DNS)

# Regular Expression Operators
  Union:       R1 + R2   (alternation)
  Concatenation: R1R2
  Kleene Star: R*      (zero or more)
  Kleene Plus: R+      (one or more) = RR*
  ε-closure:   state + all states reachable via ε

# Regex to NFA (Thompson's Construction)
  Base cases: single symbol → 2-state NFA
  Union/Concat/Star: combine using ε-transitions

# DFA Minimization (Hopcroft's Algorithm)
  1. Remove unreachable states
  2. Partition into final/non-final (initial partition)
  3. Refine: states in same partition must go to same partition
  4. Repeat until no further refinement

# Pumping Lemma for Regular Languages
  For regular L, ∃ pumping length p:
    For string s ∈ L with |s| ≥ p:
      s = xyz where |xy| ≤ p, |y| > 0
      For all i ≥ 0: xy^iz ∈ L
  USE: to PROVE language is NOT regular
  (choose s, show contradiction for some i)

# CFG Terminology
  G = (V, T, P, S) — Variables, Terminals, Productions, Start symbol
  Leftmost derivation: always expand leftmost variable first
  Ambiguous grammar: more than one parse tree for same string

# CFL Closure Properties
  CLOSED under: Union, Concatenation, Kleene Star, Reversal, homomorphism
  NOT closed under: Intersection, Complement, Difference

  BUT: DCFL is closed under Complement
  CFL ∩ Regular is CFL

# Pumping Lemma for CFL
  For CFL L, ∃ pumping length p:
    For s ∈ L with |s| ≥ p:
      s = uvxyz where |vxy| ≤ p, |vy| > 0
      For all i ≥ 0: uv^ixy^iz ∈ L

# CNF (Chomsky Normal Form)
  Productions: A → BC  or  A → a  or  S → ε
  Conversion: Eliminate ε, unit, useless productions; binarize

# PDA = NFA + Stack
  Accept by: Final State or Empty Stack (equivalent power)
  Deterministic PDA (DPDA) recognizes DCFL (proper subset of CFL)

# Turing Machine
  TM = (Q, Σ, Γ, δ, q₀, q_accept, q_reject)
  δ: Q × Γ → Q × Γ × {L, R}

# Language Classes
  Recursive (R): TM halts on ALL inputs (decidable)
  Recursively Enumerable (RE): TM halts on YES inputs (semi-decidable)

  R ⊂ RE ⊂ All Languages

# Key Properties
  RE complement is co-RE
  R is closed under complement (decidable languages)
  If L and L' are both RE → L is Recursive

# Universal TM = UTM (can simulate any TM)
  Halting Problem = "Does TM M halt on input w?" → UNDECIDABLE

# Reduction: If A ≤m B and B is decidable → A is decidable
            If A ≤m B and A is undecidable → B is undecidable

# Common Undecidable Problems
  1. Halting Problem
  2. Post Correspondence Problem (PCP)
  3. Equivalence of two CFGs
  4. Is CFG ambiguous?
  5. Is L(CFG) = Σ*?
  6. Is L(TM) = Regular?
  7. Does TM accept empty string?

# Top-Down Parsing (LL Parsing)
  LL(1) Grammar: scan Left-to-right, Leftmost derivation, 1 lookahead
  FIRST(α): all terminals that can begin strings derived from α
  FOLLOW(A): all terminals that can appear immediately after A

  LL(1) Condition: For every production A → α | β:
    FIRST(α) ∩ FIRST(β) = ∅
    If ε ∈ FIRST(α), then FIRST(β) ∩ FOLLOW(A) = ∅

  Predictive Parsing Table: M[A, a] = production to use
  Left Recursion Elimination:
    A → Aα | β  converts to  A → βA', A' → αA' | ε
  Left Factoring:
    A → αβ₁ | αβ₂  converts to  A → αA', A' → β₁ | β₂

# Bottom-Up Parsing (LR Parsing)
  LR(0): items, no lookahead
  SLR(1): LR(0) items + FOLLOW for reduce
  LALR(1): merged LR(1) states (used in YACC/Bison)
  CLR(1) / LR(1): full lookahead, most powerful

  Power: LR(0) ⊂ SLR(1) ⊂ LALR(1) ⊂ CLR(1)
  LR parsing can handle more grammars than LL parsing

# Three-Address Code Forms
  x = y op z        (binary operation)
  x = op y           (unary operation)
  x = y              (copy)
  goto L             (unconditional jump)
  if x relop y goto L (conditional jump)
  param x / call p,n / return x  (function)

# Basic Block
  Maximal sequence with no branches in / branches out only at end

# DAG (Directed Acyclic Graph) for Basic Block
  Common sub-expression elimination
  Dead code elimination
  Nodes: operators, operands; Edges: data flow

# Optimization Techniques
  1. Constant Folding: evaluate constants at compile time
  2. Common Subexpression Elimination
  3. Dead Code Elimination
  4. Code Motion (Loop Invariant)
  5. Strength Reduction: replace * by <<
  6. Induction Variable Elimination

# Register Allocation
  Graph coloring: interference graph of live ranges
  k registers → k-colorable?
  NP-complete → use heuristic (Chaitin's algorithm)
  Spill: if not colorable, store in memory

# Symbol Table Entry
  name, type, scope, offset, arguments, return type

# Scope Resolution
  Nested scopes → use scope stack
  Most closely nested rule applies

# Activation Record (Stack Frame)
  Parameters | Return Address | Dynamic Link | Saved Registers | Local Variables | Temporaries

# Parameter Passing
  Call by Value:      copy of actual parameter
  Call by Reference:  address of actual parameter
  Call by Value-Result: copy-in + copy-out
  Call by Name:       textual substitution (lazy evaluation)
  Call by Need:       lazy evaluation with memoization

# Storage Allocation
  Static:    compile-time allocation (globals)
  Stack:     runtime stack (activation records)
  Heap:      dynamic allocation (malloc, new)

# Conversions
  Binary → Decimal:  Σ bit × 2^position
  Decimal → Binary:  Repeated division by 2
  Octal → Binary:    Each digit → 3 bits
  Hex → Binary:      Each digit → 4 bits

  Binary → Octal:    Group 3 bits from right
  Binary → Hex:      Group 4 bits from right

# Number Representations (n bits)
  Range Unsigned:           0 to 2^n − 1
  Range Signed Magnitude:  −(2^(n-1)−1) to +(2^(n-1)−1)
  Range 1's Complement:    −(2^(n-1)−1) to +(2^(n-1)−1)
  Range 2's Complement:    −2^(n-1) to +(2^(n-1)−1)

  2's complement of x: (2^n − x) or invert all bits + 1
  1's complement of x: (2^n − 1 − x) or invert all bits

# Subtraction (2's complement)
  A − B = A + (2's complement of B)
  If carry out → positive result (discard carry)
  If no carry → negative result (take 2's complement of result)

# Laws
  Identity:   A + 0 = A          A · 1 = A
  Null:       A + 1 = 1          A · 0 = 0
  Complement: A + A' = 1         A · A' = 0
  Idempotent: A + A = A          A · A = A
  De Morgan:  (A+B)' = A'B'      (AB)' = A'+B'
  Absorption: A + AB = A         A(A+B) = A
  Consensus:  AB + A'C + BC = AB + A'C

# Canonical Forms
  Sum of Products (SOP):  OR of AND terms (minterms)
  Product of Sums (POS):  AND of OR terms (maxterms)
  m_i = M_i'  (minterm i is complement of maxterm i)

  Number of minterms = 2^n (for n variables)
  k-map minterms: adjacent cells differ by 1 bit

# K-Map Sizes
  2 var → 4 cells     3 var → 8 cells
  4 var → 16 cells    5 var → two 16-cell maps

  Essential prime implicant: covers at least one minterm not covered by others

# Combinational Circuits
  Multiplexer (MUX):   2^n:1 MUX needs n select lines
  Demultiplexer:       1:2^n DEMUX
  Encoder:             2^n inputs → n outputs
  Decoder:             n inputs → 2^n outputs
  Comparator:          Compare two n-bit numbers
  Adder:               Ripple carry (O(n)), Carry lookahead (O(log n))

  Carry lookahead:     C_i = G_i + P_i × C_(i-1)
  Generate: G_i = A_i · B_i
  Propagate: P_i = A_i ⊕ B_i

# Sequential Circuits
  Flip-Flops:
    SR:   S=R=1 is invalid state
    JK:   J=K=1 toggles (no invalid state)
    D:    Q = D (used in registers)
    T:    Q toggles when T=1

  Counters:
    Ripple Counter:     output of one FF drives clock of next
    Synchronous:        all FFs share common clock
    Mod-N:              counts 0 to N-1
    Johnson (Twisted Ring): 2N states for N FFs
    Ring Counter:       N states for N FFs

  Shift Registers:
    SISO: n clock cycles for n-bit shift
    SIPO: serial in, parallel out
    PISO: parallel in, serial out
    PIPO: n clocks for full load

# State Machine
  Moore: output depends only on state
  Mealy:  output depends on state AND input
  Moore needs more states but simpler output logic

# Number System
  Sum of first n naturals:  n(n+1)/2
  Sum of first n squares:   n(n+1)(2n+1)/6
  Sum of first n cubes:     [n(n+1)/2]²

# HCF & LCM
  HCF × LCM = a × b (for two numbers)
  LCM(a,b,c) = a×b×c / [HCF(a,b)×HCF(b,c)×HCF(c,a)] × HCF(a,b,c)

# Percentages
  x% of y = y% of x
  If price increases by R%: new = P × (100+R)/100
  Successive changes: a% then b% → net = a + b + ab/100

# Profit & Loss
  Profit% = (Profit/CP) × 100
  Selling after discount: SP = MP × (100−d)/100

# Time & Work
  Work = Rate × Time
  If A can do in a days, B in b days: Together = ab/(a+b) days
  M persons in D days working H hrs/day: M₁D₁H₁/W₁ = M₂D₂H₂/W₂

# Time, Speed, Distance
  Speed = Distance/Time
  Average speed = 2xy/(x+y) for equal distances
  Relative speed (same dir) = |x−y|, (opposite dir) = x+y

# Simple & Compound Interest
  SI = P×R×T/100
  CI = P(1+R/100)^T − P

# Common Patterns
  Blood Relations: Use tree diagram or notation (A + B = married, A − B = sibling)
  Directions: N/E/S/W; NE/NW/SE/SW; Left/Right turns
    Facing North → Left = West, Right = East
    Facing East  → Left = North, Right = South
  Coding-Decoding: letter shifting, reverse, position-based
  Series: Arithmetic (d), Geometric (r), Square, Cube, Fibonacci
  Seating Arrangement: Linear, Circular, Rectangular with conditions
  Syllogism: Use Venn diagrams, basic squares
  Data Interpretation: Read tables/graphs carefully, check units

# Clock Problems
  Angle between hands = |30H − 5.5M|
  Hands overlap: 11 times in 12 hours (every 65 5/11 min)
  Hands are opposite: 11 times in 12 hours
  Hands are at right angle: 22 times in 12 hours

# Calendar Problems
  Odd days: Normal year = 1, Leap year = 2
  Century years divisible by 400 = leap year
  Day = (Date code + Month code + Year code) mod 7