GATE CY flashcards

34 cards. Read the term and the definition here. The deck at the top of this page is optional.

Successive percentage change

Two successive changes of a percent and b percent produce a net change of a + b + ab/100. A 20 percent increase followed by a 20 percent decrease gives a net 4 percent decrease, not zero.

Harmonic work formula

If worker A finishes a job in a days and worker B in b days, working together they take ab/(a+b) days. Extend by summing individual rates 1/a + 1/b and inverting the total.

Bayes theorem

P(A given B) equals P(B given A) times P(A) divided by P(B). The denominator expands as the sum over all mutually exclusive causes of P(B given cause) times P(cause).

Equivalence relation conditions

A relation is an equivalence relation when it is reflexive, symmetric, and transitive. Such a relation partitions the underlying set into disjoint equivalence classes whose union is the whole set.

Handshaking lemma

In any undirected graph the sum of all vertex degrees equals twice the number of edges. Consequently the number of vertices with odd degree must always be even.

Euler planar graph formula

For a connected planar graph, v minus e plus f equals 2, counting the outer face. A simple planar graph with v at least 3 also satisfies e less than or equal to 3v minus 6.

Rank-nullity theorem

For an m by n matrix A, the rank plus the nullity equals n, the number of columns. The matrix is invertible exactly when its rank equals its order.

Functional completeness of NAND

NAND alone can express NOT, AND, and OR, so every Boolean function is realizable using only NAND gates. NOR has the same property, which is why both are called universal gates.

Multiplexer as function generator

A multiplexer with n select lines and 2^n data inputs implements any Boolean function of n variables. Tie each data input to the constant required by the function's truth table.

Setup and hold time

Setup time is how long data must be stable before the active clock edge; hold time is how long it must remain stable after. Hold violations cannot be cured by lowering clock frequency.

Johnson counter states

A Johnson counter built from n flip-flops with inverted feedback has 2n distinct states before repeating. A simple ring counter with direct feedback has only n states.

Average memory access time

AMAT equals hit time plus miss rate times miss penalty. With two cache levels it becomes t1 plus m1 times the quantity t2 plus m2 times the main memory penalty.

Amdahl law speedup

If a fraction f of execution is enhanced by factor s, overall speedup is 1 divided by the quantity (1 minus f) plus f divided by s. Unenhanced portions cap the gain.

IEEE 754 single precision

Single precision uses 32 bits: one sign bit, eight exponent bits with bias 127, and 23 fraction bits. Double precision uses 64 bits with an 11-bit exponent biased by 1023.

Write-back versus write-through

Write-through updates memory on every store, keeping memory consistent at high bandwidth cost. Write-back updates only the cache and marks a dirty bit, writing memory at eviction time.

Array decay to pointer

In C an array name decays to a pointer to its first element in most expressions, so a[i] equals *(a+i). However sizeof on the array name yields the whole array's size.

Complete binary tree indexing

Stored in a zero-based array, node i has children at 2i+1 and 2i+2 and parent at floor((i-1)/2). This layout supports heaps without explicit pointers.

Binary search tree worst case

A binary search tree with n nodes has expected height logarithmic for random insertions, but inserting keys in sorted order produces a degenerate chain of height n, making search linear.

Hash table linear probing

With open addressing and load factor alpha, unsuccessful search probes rise sharply as alpha approaches one. Expected probes for linear probing grow roughly as 1/(1-alpha), so keep load low.

Master theorem cases

For T(n) = aT(n/b) + f(n), compare f(n) with n raised to log base b of a. Smaller f gives Theta(n^log_b a); equal gives an extra log factor; larger f gives Theta(f(n)).

Dijkstra versus Bellman-Ford

Dijkstra is fast with a heap but wrong for negative edge weights. Bellman-Ford relaxes all edges V-1 times in O(VE) time and detects negative cycles on an extra pass.

Greedy versus dynamic programming

Greedy works for fractional knapsack, Huffman coding, and interval scheduling by earliest finish. The 0/1 knapsack needs dynamic programming because a locally best item can block a better combination.

NP-complete definition

A problem is NP-complete if it belongs to NP and every NP problem reduces to it in polynomial time. SAT, 3-SAT, clique, vertex cover, and Hamiltonian cycle are classic examples.

Pumping lemma for regular languages

For a regular language there exists a pumping length p such that any string of length at least p splits into xyz with y nonempty, |xy| at most p, and xy^kz in the language for all k.

Closure of context-free languages

Context-free languages are closed under union, concatenation, and Kleene star, but not under intersection or complement. Deterministic CFLs are not closed under union either.

Rice theorem

Any non-trivial semantic property of recursively enumerable languages is undecidable. Non-trivial means some but not all such languages have the property.

LL(1) grammar requirements

An LL(1) grammar must be free of left recursion and left factoring. For each nonterminal, the FIRST sets of alternatives must be disjoint, and FIRST/FOLLOW conflicts are forbidden.

Three-address code

Intermediate code where each instruction has at most one operator and up to three operands, using compiler temporaries. Straight-line runs of such instructions form basic blocks for optimization.

Deadlock necessary conditions

Deadlock requires mutual exclusion, hold and wait, no preemption, and circular wait simultaneously. Preventing any single one of these four conditions is sufficient to rule out deadlock.

Belady anomaly

With FIFO page replacement, increasing the number of page frames can increase the number of page faults. LRU and optimal replacement are stack algorithms and never exhibit this anomaly.

BCNF versus 3NF

In BCNF every non-trivial functional dependency has a superkey on its left side. 3NF is weaker, allowing a dependency whose left side is not a superkey if its right side is prime.

Conflict serializability test

Build a precedence graph with an edge from transaction Ti to Tj whenever conflicting operations occur in that order. The schedule is conflict serializable exactly when this graph is acyclic.

TCP three-way handshake

A client sends SYN with an initial sequence number, the server replies SYN-ACK acknowledging it, and the client sends ACK. Both sides then have synchronized sequence numbers for reliable delivery.

Usable hosts in a subnet

An IPv4 block with prefix length n contains 2^(32-n) addresses. Subtracting the network and broadcast addresses leaves 2^(32-n) minus 2 usable host addresses.