GATE Data Structures and Algorithms formula sheet

w = size of one element in bytes; L = lower bound of the index (L = 0 for a C array, giving Base + i*w); Base = address of the first element A[L].

cols = number of columns. C stores 2-D arrays row-major, and these notes assume row-major unless a question says column-major. For column-major, whole columns are stored one after another: Base + (j*rows + i)*w, where rows = number of rows.

Root at level 0. An upper bound for any binary tree, reached exactly when level $i$ is completely filled.

Reached exactly by a perfect binary tree of height $h$ (every level completely filled).

$f$ grows no faster than $g$, up to a constant factor.

$f$ grows at least as fast as $g$, up to a constant factor.

The successful-search average assumes the key is present and equally likely to be at each of the $n$ positions. Both the worst case and the average case are $O(n)$.

Convention: each probe of a[mid] counts as one (three-way) comparison. The worst case $\lfloor {\log }_{2}n\rfloor +1$ holds for both successful and unsuccessful search. If a question counts the == test and the < test as separate comparisons, recount under its rule. Valid only for a sorted array with random access.

Applies only when any fraction of an item may be taken. Solved by sorting items on $v_i/w_i$ in descending order and filling greedily until capacity is used up; only the last item taken can be partial. Time $O(n\log n)$.

$p_i$ is the probability of symbol $i$. If frequencies are given, divide each by the total frequency. $l_i$ is its codeword length (the depth of its leaf). Huffman's construction minimises $L$ over all prefix-free codes for the given distribution. When weights tie, different trees are possible, but they all have the same minimum $L$.

Use the matrix when the graph is dense (E close to V^2) or constant-time edge checks are needed; use the list when the graph is sparse (E much smaller than V^2). An undirected graph's adjacency lists hold 2E entries in total (each edge appears in both endpoints' lists); a directed graph's hold E.

The degree sum counts every undirected edge once from each end. Consequence: every undirected graph has an even number of odd-degree vertices. In a directed graph, the sum of in-degrees = the sum of out-degrees = E.

Holds for integers with b nonzero; a // b is the floor of the true quotient, so a nonzero remainder takes the sign of b.

Holds for integers a, b and any nonzero step k, positive or negative; for example len(range(3, 20, 4)) = ceil(17/4) = 5 and len(range(5, 0, -2)) = ceil(2.5) = 3.