In IEEE 754 Single-Precision (32-bit) floating-point representation, how are bits allocated and how is the value of a normalized number calculated?

1 Sign bit (S), 8 Exponent bits (E, bias = 127), and 23 Mantissa/Fraction bits (M). Value = (-1)^S * (1.M)_2 * 2^(E - 127).

What is the Master Theorem for solving divide-and-conquer recurrences T(n) = aT(n/b) + f(n) where a >= 1, b > 1?

Compare f(n) with n^(log_b(a)): Case 1: if f(n) = O(n^(log_b(a) - epsilon)), T(n) = Theta(n^(log_b(a))); Case 2: if f(n) = Theta(n^(log_b(a)) * log^k(n)), T(n) = Theta(n^(log_b(a)) * log^(k+1)(n)); Case 3: if f(n) = Omega(n^(log_b(a) + epsilon)) and regularity holds, T(n) = Theta(f(n)).

In Operating Systems, what are Coffman's four necessary and sufficient conditions for a Deadlock to occur?

1) Mutual Exclusion, 2) Hold and Wait, 3) No Preemption, and 4) Circular Wait. Banker's Algorithm prevents deadlock by ensuring the system remains in a Safe State.

What are the worst-case and average-case time complexities and space complexities of Merge Sort, Quick Sort, and Heap Sort?

Merge Sort: Worst/Avg Theta(n log n), Space O(n) (Stable); Quick Sort: Worst Theta(n^2), Avg Theta(n log n), Space O(log n) stack (Unstable); Heap Sort: Worst/Avg Theta(n log n), Space O(1) in-place (Unstable).

In Engineering Mathematics (Linear Algebra), how are the trace and determinant of a square matrix A related to its eigenvalues lambda_1, lambda_2, ..., lambda_n?

The sum of the eigenvalues equals the trace of A (sum of diagonal elements), and the product of the eigenvalues equals the determinant of A (det(A)).

In DBMS Transactions, how do Conflict Serializability and View Serializability relate, and how does 2-Phase Locking (2PL) guarantee serializability?

Every conflict-serializable schedule is view-serializable (tested via absence of cycles in the Precedence Graph), whereas a view-serializable schedule that is not conflict-serializable must contain blind writes. Basic 2PL guarantees Conflict Serializability; Strict 2PL (holding exclusive locks until commit) also guarantees Cascadeless and Recoverable schedules.

In Graph Theory, what is the Handshaking Lemma and Euler's formula for a connected planar graph?

Handshaking Lemma: Sum of degrees of all vertices = 2 * |E| (number of edges). Euler's Planar Formula: V - E + F = 2, and for simple connected planar graphs with V >= 3, E <= 3V - 6.

What are the error orders and step-size requirements for the Trapezoidal Rule and Simpson's 1/3 Rule in Numerical Integration?

Trapezoidal Rule (linear interpolation, any number of subintervals n): Error O(h^2). Simpson's 1/3 Rule (parabolic interpolation, requires n to be EVEN): Error O(h^4), exact for polynomials up to degree 3.

In OS Process Synchronization, what are the three requirements for a valid Critical Section solution, and how does a Binary Semaphore differ from a Mutex?

1) Mutual Exclusion (mandatory), 2) Progress (mandatory), 3) Bounded Waiting. A Mutex has an ownership concept (only the thread that locked it can unlock it), whereas a Binary Semaphore is a signaling mechanism without ownership.

What is the minimum frame size requirement in CSMA/CD (Ethernet IEEE 802.3)?

Transmission Time (T_tx = Frame_Size / Bandwidth) must be >= 2 * Propagation Time (2 * T_prop = 2 * Distance / Speed), so Minimum Frame Size L_min = 2 * Bandwidth * Distance / Speed (64 bytes or 512 bits for standard Ethernet).

In GATE Data Structures, what is the maximum and minimum number of nodes in a binary tree of height h (where a single root node has height 0) and in an AVL tree of height h?

Binary Tree: Min nodes = h + 1, Max nodes = 2^(h+1) - 1. AVL Tree (height-balanced, balance factor in {-1, 0, 1}): Min nodes N(h) = N(h-1) + N(h-2) + 1 with N(0)=1, N(1)=2 (so height is O(log n)).

In IPv4 Addressing and Subnetting, what is the difference between a Broadcast domain and a Collision domain across Hub, Switch, and Router?

A Hub (Layer 1) has 1 collision domain and 1 broadcast domain; a Switch (Layer 2) separates collision domains per port (N ports = N collision domains) but has 1 broadcast domain; a Router (Layer 3) separates both collision domains and broadcast domains.

When does a system of linear equations Ax = b have a unique solution, infinitely many solutions, or no solution according to the Rouche-Capelli rank condition?

Let n be the number of variables: 1) rank(A) != rank([A|b]) -> No solution (inconsistent); 2) rank(A) = rank([A|b]) = n -> Unique solution; 3) rank(A) = rank([A|b]) Infinitely many solutions with (n - rank(A)) free variables.

How do Dijkstra's, Bellman-Ford, and Floyd-Warshall shortest-path algorithms compare in time complexity and negative edge handling?

Dijkstra (binary heap): O((V + E) log V), fails on negative weight edges; Bellman-Ford: O(V * E), handles negative weights and detects negative cycles; Floyd-Warshall (all-pairs DP): O(V^3).

In GATE C Programming, what is the difference between `const char *p`, `char * const p`, and static local variables?

`const char *p` is a pointer to a constant character (pointer can change, pointed value cannot); `char * const p` is a constant pointer to a character (pointer address is fixed, pointed value can change). A `static` local variable is stored in the Data/BSS segment and retains its value across function calls.

In Computer Networks, how do you calculate the Utilization (Efficiency) of Stop-and-Wait, Go-Back-N (GBN), and Selective Repeat (SR) sliding window protocols?

Let a = T_propagation / T_transmission. Stop-and-Wait efficiency = 1 / (1 + 2a). For sliding window of size W, Efficiency = min(1, W / (1 + 2a)). Optimal window size for 100% utilization is W = 1 + 2a; Sequence number bits required: GBN needs W <= 2^k - 1, SR needs W <= 2^(k-1).

In DBMS Indexing, what is the structural difference between a B-Tree and a B+ Tree?

In a B-Tree, search keys and data pointers (record pointers) are stored in both internal and leaf nodes; in a B+ Tree, data pointers reside ONLY in leaf nodes, internal nodes store only routing keys (higher fan-out), and leaf nodes are linked sequentially for fast range queries.

In DBMS Normalization, what are the exact definitions of 1NF, 2NF, 3NF, and BCNF (Boyce-Codd Normal Form)?

1NF: Atomic attributes; 2NF: 1NF + no partial dependency of non-prime attributes on candidate keys; 3NF: 2NF + for every non-trivial FD X -> Y, either X is a superkey OR Y is a prime attribute; BCNF: for every non-trivial FD X -> Y, X MUST be a superkey.

In Theory of Computation (TOC), what is the Chomsky Hierarchy of formal grammars, languages, and their corresponding automata?

Type 3: Regular Languages Finite Automata (DFA/NFA); Type 2: Context-Free Languages (CFL) Pushdown Automata (PDA); Type 1: Context-Sensitive Languages (CSL) Linear Bounded Automata (LBA); Type 0: Recursively Enumerable Languages Turing Machine.

In Compiler Design, what is the hierarchy of LR parsers by parsing power and table size?

LR(0) < SLR(1) < LALR(1) < CLR(1) (Canonical LR). LALR(1) and SLR(1) have the same number of states as LR(0), whereas CLR(1) has the largest number of states. An LL(1) grammar can never be ambiguous or left-recursive.

In Vector Calculus, what are Gauss's Divergence Theorem and Stokes' Theorem?

Gauss's Divergence Theorem converts a closed surface integral to a volume integral: oint_S (F . n) dS = int_V (div F) dV. Stokes' Theorem converts a closed line integral to a surface integral: oint_C F . dr = int_S (curl F . n) dS.

In Computer Organization, what is the Effective Memory Access Time (EMAT) formula for a two-level cache/main memory system under simultaneous vs hierarchical access?

Simultaneous access: EMAT = h*T_cache + (1 - h)*T_memory. Hierarchical (serial) access: EMAT = T_cache + (1 - h)*T_memory, where h is the cache hit ratio.

What is the Newton-Raphson iterative formula for finding roots of f(x) = 0 and what is its order of convergence?

x_(n+1) = x_n - f(x_n) / f'(x_n). It has quadratic convergence (order 2) for simple roots provided f'(x) != 0.

In Probability, what are the mean and variance of Binomial(n, p), Poisson(lambda), Exponential(lambda), and Uniform(a, b) distributions?

Binomial: Mean = np, Var = np(1-p); Poisson: Mean = lambda, Var = lambda; Exponential: Mean = 1/lambda, Var = 1/lambda^2; Continuous Uniform(a,b): Mean = (a+b)/2, Var = (b-a)^2 / 12.

How do Mealy and Moore Finite State Machines (FSMs) differ in Digital Logic?

In a Moore machine, the output depends ONLY on the present state (requiring more states, synchronous output changes); in a Mealy machine, the output depends on BOTH the present state and the current input (fewer states, faster asynchronous response).

What is the Cayley-Hamilton Theorem and how is it used in GATE Linear Algebra?

Every square matrix satisfies its own characteristic equation det(A - lambda*I) = 0; it allows expressing higher powers A^n and the inverse A^-1 as a polynomial in A of degree at most n - 1.

In Propositional and First-Order Logic, how many boolean functions and self-dual functions exist for n boolean variables?

Total boolean functions of n variables = 2^(2^n). Total self-dual functions of n variables = 2^(2^(n-1)).

In a 5-stage instruction pipeline (IF, ID, EX, MEM, WB), what are the three types of pipeline hazards and how are Data Hazards mitigated?

1) Structural hazards (hardware resource conflict), 2) Data hazards (RAW, WAR, WAW), 3) Control/Branch hazards. RAW hazards are mitigated via Operand Forwarding (Bypassing) and pipeline stalls; WAR/WAW via Register Renaming.

In TCP Congestion Control, how does the Congestion Window (cwnd) change during Slow Start, Congestion Avoidance, Triple Duplicate ACK, and Timeout?

Slow Start: cwnd doubles every RTT (exponential, +1 MSS per ACK) until ssthresh; Congestion Avoidance: cwnd increases linearly (+1 MSS per RTT); Triple Duplicate ACK (Fast Recovery): ssthresh = cwnd/2, cwnd = ssthresh; Timeout: ssthresh = cwnd/2, cwnd resets to 1 MSS.

In TOC, which closure properties distinguish Context-Free Languages (CFLs) from Regular Languages?

Regular languages are closed under Union, Concatenation, Kleene Star, Intersection, and Complement. CFLs are closed under Union, Concatenation, and Kleene Star, but NOT closed under Intersection or Complement (though closed under intersection with a Regular language).

In OS Virtual Memory, what is Belady's Anomaly and which page replacement algorithms are immune to it?

Belady's Anomaly is the phenomenon where increasing the number of physical page frames results in an increase in page faults. FIFO suffers from Belady's Anomaly, whereas stack-based algorithms like LRU (Least Recently Used) and Optimal (OPT) never suffer from it.

In Digital Logic, what is the minimum number of 2-input NAND gates or 2-input NOR gates required to implement an XOR gate?

4 two-input NAND gates are required to implement A XOR B; similarly, 4 two-input NOR gates are required to implement A XOR B (5 for XNOR with NAND, 4 for XNOR with NOR).

GATE Engineering & Computer Science Core: Engineering Mathematics (Linear Algebra, Calculus, Probability), Digital Logic, OS, DBMS, Networks & Algorithms

Essential GATE Engineering Mathematics and Computer Science (CS/DA) concepts covering eigenvalues, probability distributions, digital logic, OS scheduling, DBMS normalization, computer networks, and algorithmic complexity.

Level: intermediate
Languages: en → en
Cards: 32
Markdown: GATE Engineering & Computer Science Core: Engineering Mathematics (Linear Algebra, Calculus, Probability), Digital Logic, OS, DBMS, Networks & Algorithms (.md)

Flashcards (32)

#	Front (Term / Question)	Back (Definition / Answer)
1	In IEEE 754 Single-Precision (32-bit) floating-point representation, how are bits allocated and how is the value of a normalized number calculated?	1 Sign bit (S), 8 Exponent bits (E, bias = 127), and 23 Mantissa/Fraction bits (M). Value = (-1)^S * (1.M)_2 * 2^(E - 127).
2	What is the Master Theorem for solving divide-and-conquer recurrences T(n) = aT(n/b) + f(n) where a >= 1, b > 1?	Compare f(n) with n^(log_b(a)): Case 1: if f(n) = O(n^(log_b(a) - epsilon)), T(n) = Theta(n^(log_b(a))); Case 2: if f(n) = Theta(n^(log_b(a)) * log^k(n)), T(n) = Theta(n^(log_b(a)) * log^(k+1)(n)); Case 3: if f(n) = Omega(n^(log_b(a) + epsilon)) and regularity holds, T(n) = Theta(f(n)).
3	In Operating Systems, what are Coffman's four necessary and sufficient conditions for a Deadlock to occur?	1) Mutual Exclusion, 2) Hold and Wait, 3) No Preemption, and 4) Circular Wait. Banker's Algorithm prevents deadlock by ensuring the system remains in a Safe State.
4	What are the worst-case and average-case time complexities and space complexities of Merge Sort, Quick Sort, and Heap Sort?	Merge Sort: Worst/Avg Theta(n log n), Space O(n) (Stable); Quick Sort: Worst Theta(n^2), Avg Theta(n log n), Space O(log n) stack (Unstable); Heap Sort: Worst/Avg Theta(n log n), Space O(1) in-place (Unstable).
5	In Engineering Mathematics (Linear Algebra), how are the trace and determinant of a square matrix A related to its eigenvalues lambda_1, lambda_2, ..., lambda_n?	The sum of the eigenvalues equals the trace of A (sum of diagonal elements), and the product of the eigenvalues equals the determinant of A (det(A)).
6	In DBMS Transactions, how do Conflict Serializability and View Serializability relate, and how does 2-Phase Locking (2PL) guarantee serializability?	Every conflict-serializable schedule is view-serializable (tested via absence of cycles in the Precedence Graph), whereas a view-serializable schedule that is not conflict-serializable must contain blind writes. Basic 2PL guarantees Conflict Serializability; Strict 2PL (holding exclusive locks until commit) also guarantees Cascadeless and Recoverable schedules.
7	In Graph Theory, what is the Handshaking Lemma and Euler's formula for a connected planar graph?	Handshaking Lemma: Sum of degrees of all vertices = 2 * \|E\| (number of edges). Euler's Planar Formula: V - E + F = 2, and for simple connected planar graphs with V >= 3, E <= 3V - 6.
8	What are the error orders and step-size requirements for the Trapezoidal Rule and Simpson's 1/3 Rule in Numerical Integration?	Trapezoidal Rule (linear interpolation, any number of subintervals n): Error O(h^2). Simpson's 1/3 Rule (parabolic interpolation, requires n to be EVEN): Error O(h^4), exact for polynomials up to degree 3.
9	In OS Process Synchronization, what are the three requirements for a valid Critical Section solution, and how does a Binary Semaphore differ from a Mutex?	1) Mutual Exclusion (mandatory), 2) Progress (mandatory), 3) Bounded Waiting. A Mutex has an ownership concept (only the thread that locked it can unlock it), whereas a Binary Semaphore is a signaling mechanism without ownership.
10	What is the minimum frame size requirement in CSMA/CD (Ethernet IEEE 802.3)?	Transmission Time (T_tx = Frame_Size / Bandwidth) must be >= 2 * Propagation Time (2 * T_prop = 2 * Distance / Speed), so Minimum Frame Size L_min = 2 * Bandwidth * Distance / Speed (64 bytes or 512 bits for standard Ethernet).
11	In GATE Data Structures, what is the maximum and minimum number of nodes in a binary tree of height h (where a single root node has height 0) and in an AVL tree of height h?	Binary Tree: Min nodes = h + 1, Max nodes = 2^(h+1) - 1. AVL Tree (height-balanced, balance factor in {-1, 0, 1}): Min nodes N(h) = N(h-1) + N(h-2) + 1 with N(0)=1, N(1)=2 (so height is O(log n)).
12	In IPv4 Addressing and Subnetting, what is the difference between a Broadcast domain and a Collision domain across Hub, Switch, and Router?	A Hub (Layer 1) has 1 collision domain and 1 broadcast domain; a Switch (Layer 2) separates collision domains per port (N ports = N collision domains) but has 1 broadcast domain; a Router (Layer 3) separates both collision domains and broadcast domains.
13	When does a system of linear equations Ax = b have a unique solution, infinitely many solutions, or no solution according to the Rouche-Capelli rank condition?	Let n be the number of variables: 1) rank(A) != rank([A\|b]) -> No solution (inconsistent); 2) rank(A) = rank([A\|b]) = n -> Unique solution; 3) rank(A) = rank([A\|b]) < n -> Infinitely many solutions with (n - rank(A)) free variables.
14	How do Dijkstra's, Bellman-Ford, and Floyd-Warshall shortest-path algorithms compare in time complexity and negative edge handling?	Dijkstra (binary heap): O((V + E) log V), fails on negative weight edges; Bellman-Ford: O(V * E), handles negative weights and detects negative cycles; Floyd-Warshall (all-pairs DP): O(V^3).
15	In GATE C Programming, what is the difference between `const char p`, `char const p`, and static local variables?	`const char p` is a pointer to a constant character (pointer can change, pointed value cannot); `char const p` is a constant pointer to a character (pointer address is fixed, pointed value can change). A `static` local variable is stored in the Data/BSS segment and retains its value across function calls.
16	In Computer Networks, how do you calculate the Utilization (Efficiency) of Stop-and-Wait, Go-Back-N (GBN), and Selective Repeat (SR) sliding window protocols?	Let a = T_propagation / T_transmission. Stop-and-Wait efficiency = 1 / (1 + 2a). For sliding window of size W, Efficiency = min(1, W / (1 + 2a)). Optimal window size for 100% utilization is W = 1 + 2a; Sequence number bits required: GBN needs W <= 2^k - 1, SR needs W <= 2^(k-1).
17	In DBMS Indexing, what is the structural difference between a B-Tree and a B+ Tree?	In a B-Tree, search keys and data pointers (record pointers) are stored in both internal and leaf nodes; in a B+ Tree, data pointers reside ONLY in leaf nodes, internal nodes store only routing keys (higher fan-out), and leaf nodes are linked sequentially for fast range queries.
18	In DBMS Normalization, what are the exact definitions of 1NF, 2NF, 3NF, and BCNF (Boyce-Codd Normal Form)?	1NF: Atomic attributes; 2NF: 1NF + no partial dependency of non-prime attributes on candidate keys; 3NF: 2NF + for every non-trivial FD X -> Y, either X is a superkey OR Y is a prime attribute; BCNF: for every non-trivial FD X -> Y, X MUST be a superkey.
19	In Theory of Computation (TOC), what is the Chomsky Hierarchy of formal grammars, languages, and their corresponding automata?	Type 3: Regular Languages <-> Finite Automata (DFA/NFA); Type 2: Context-Free Languages (CFL) <-> Pushdown Automata (PDA); Type 1: Context-Sensitive Languages (CSL) <-> Linear Bounded Automata (LBA); Type 0: Recursively Enumerable Languages <-> Turing Machine.
20	In Compiler Design, what is the hierarchy of LR parsers by parsing power and table size?	LR(0) < SLR(1) < LALR(1) < CLR(1) (Canonical LR). LALR(1) and SLR(1) have the same number of states as LR(0), whereas CLR(1) has the largest number of states. An LL(1) grammar can never be ambiguous or left-recursive.
21	In Vector Calculus, what are Gauss's Divergence Theorem and Stokes' Theorem?	Gauss's Divergence Theorem converts a closed surface integral to a volume integral: oint_S (F . n) dS = int_V (div F) dV. Stokes' Theorem converts a closed line integral to a surface integral: oint_C F . dr = int_S (curl F . n) dS.
22	In Computer Organization, what is the Effective Memory Access Time (EMAT) formula for a two-level cache/main memory system under simultaneous vs hierarchical access?	Simultaneous access: EMAT = hT_cache + (1 - h)T_memory. Hierarchical (serial) access: EMAT = T_cache + (1 - h)*T_memory, where h is the cache hit ratio.
23	What is the Newton-Raphson iterative formula for finding roots of f(x) = 0 and what is its order of convergence?	x_(n+1) = x_n - f(x_n) / f'(x_n). It has quadratic convergence (order 2) for simple roots provided f'(x) != 0.
24	In Probability, what are the mean and variance of Binomial(n, p), Poisson(lambda), Exponential(lambda), and Uniform(a, b) distributions?	Binomial: Mean = np, Var = np(1-p); Poisson: Mean = lambda, Var = lambda; Exponential: Mean = 1/lambda, Var = 1/lambda^2; Continuous Uniform(a,b): Mean = (a+b)/2, Var = (b-a)^2 / 12.
25	How do Mealy and Moore Finite State Machines (FSMs) differ in Digital Logic?	In a Moore machine, the output depends ONLY on the present state (requiring more states, synchronous output changes); in a Mealy machine, the output depends on BOTH the present state and the current input (fewer states, faster asynchronous response).
26	What is the Cayley-Hamilton Theorem and how is it used in GATE Linear Algebra?	Every square matrix satisfies its own characteristic equation det(A - lambda*I) = 0; it allows expressing higher powers A^n and the inverse A^-1 as a polynomial in A of degree at most n - 1.
27	In Propositional and First-Order Logic, how many boolean functions and self-dual functions exist for n boolean variables?	Total boolean functions of n variables = 2^(2^n). Total self-dual functions of n variables = 2^(2^(n-1)).
28	In a 5-stage instruction pipeline (IF, ID, EX, MEM, WB), what are the three types of pipeline hazards and how are Data Hazards mitigated?	1) Structural hazards (hardware resource conflict), 2) Data hazards (RAW, WAR, WAW), 3) Control/Branch hazards. RAW hazards are mitigated via Operand Forwarding (Bypassing) and pipeline stalls; WAR/WAW via Register Renaming.
29	In TCP Congestion Control, how does the Congestion Window (cwnd) change during Slow Start, Congestion Avoidance, Triple Duplicate ACK, and Timeout?	Slow Start: cwnd doubles every RTT (exponential, +1 MSS per ACK) until ssthresh; Congestion Avoidance: cwnd increases linearly (+1 MSS per RTT); Triple Duplicate ACK (Fast Recovery): ssthresh = cwnd/2, cwnd = ssthresh; Timeout: ssthresh = cwnd/2, cwnd resets to 1 MSS.
30	In TOC, which closure properties distinguish Context-Free Languages (CFLs) from Regular Languages?	Regular languages are closed under Union, Concatenation, Kleene Star, Intersection, and Complement. CFLs are closed under Union, Concatenation, and Kleene Star, but NOT closed under Intersection or Complement (though closed under intersection with a Regular language).
31	In OS Virtual Memory, what is Belady's Anomaly and which page replacement algorithms are immune to it?	Belady's Anomaly is the phenomenon where increasing the number of physical page frames results in an increase in page faults. FIFO suffers from Belady's Anomaly, whereas stack-based algorithms like LRU (Least Recently Used) and Optimal (OPT) never suffer from it.
32	In Digital Logic, what is the minimum number of 2-input NAND gates or 2-input NOR gates required to implement an XOR gate?	4 two-input NAND gates are required to implement A XOR B; similarly, 4 two-input NOR gates are required to implement A XOR B (5 for XNOR with NAND, 4 for XNOR with NOR).