GATE Algorithms previous year questions

With randomly ordered input, the first element is equally likely to be any rank. If it is the (k+1)-th smallest, the partitions have sizes k and n - k - 1, each with probability 1/n for k = 0..n-1. Averaging gives T(n) = (1/n) Σ [T(k) + T(n - k - 1)] + O(n), which solves to O(n log n). (A) is the worst case, (B) and (C) are particular fixed splits. Answer: (D).

Concept: Expected-case recurrence averages over all pivot ranks. The trap is choosing the balanced-split recurrence, which describes one ideal case, not the expectation.

Each step makes one (three-way) comparison and recurses on at most the larger half. Worst-case sizes: 1000 → 500 → 250 → 125 → 62 → 31 → 15 → 7 → 3 → 1, then the range becomes empty. That is 10 comparisons, i.e. ⌊log₂ 1000⌋ + 1 = 9 + 1 = 10. Answer: 10.

Concept: Unsuccessful binary search takes ⌊log₂ n⌋ + 1 probes in the worst case. The trap is answering ⌈log₂ 1000⌉ = 10 for the wrong reason or 9 by forgetting the last probe.

BFS and DFS both visit exactly the vertices reachable from the start. If u is reachable from v in G, there is a path v → ... → u; reversing every edge gives a path u → ... → v in Gᴿ, so v is reachable from u in Gᴿ (D true). (A)/(B) fail for G with the single edge v → u: in Gᴿ nothing is reachable from v, but u is reachable in G. (C) fails because traversal orders are unrelated. Answer: (D).

Concept: Reachability reverses under edge reversal. The trap is assuming reversed graphs have the same reachable sets from the same source.

Insertion sort: insert 2 (1 comparison), 3 (1), 5 (1), 4 (compare with 5 and shift, then compare with 3 and stop: 2). N2 = 5, with one swap/shift (C true), so (A) false. Bubble sort: the plain version makes 4 + 3 + 2 + 1 = 10 comparisons; even with an early-exit flag it makes 4 + 3 = 7. Either way N1 > N2 (B true). Both compare already-ordered pairs such as (1, 2) (D true). Answer: (B), (C), (D).

Concept: Counting comparisons on a nearly sorted array. The trap is counting only 4 comparisons for insertion sort, missing the final comparison that stops the insertion of 4.

fun is one bubble-sort pass that swaps adjacent out-of-order pairs and returns the number of swaps; the list is modified in place. The loop runs 5 passes, enough to sort a 5-element list, so count equals the total number of adjacent swaps, which equals the number of inversions. Inversions in [5, 3, 4, 1, 2]: 5 with 3, 4, 1, 2 (4); 3 with 1, 2 (2); 4 with 1, 2 (2); total 8. Pass by pass: 4, 2, 2, 0, 0. Answer: 8.

Concept: Bubble sort swaps equal the inversion count. The trap is counting comparisons instead of swaps, or thinking the list is copied between calls.

T₂: a = 5, b = 4, n^(log₄ 5) ≈ n^1.16, which dominates log n polynomially, so T₂(n) = Θ(n^(log₄ 5)) by Master theorem case 1. T₁: a = 4, b = 2, n^(log₂ 4) = n². The driving term n^1.16 is polynomially smaller than n², so case 1 again: T₁(n) = Θ(n²). Answer: (A) T₁(n) = Θ(n²).

Concept: Nested Master theorem: solve the inner recurrence first, then use it as f(n). Options (C)/(D) are the trap of reporting T₂ instead of T₁, since log₄ 5 < 2.

1 -> 8. 13 -> 20 mod 11 = 9. 22 -> 29 mod 11 = 7. 15 -> 22 mod 11 = 0. 11 -> 18 mod 11 = 7, occupied; probe 8, 9 occupied; 10 free. 24 -> 31 mod 11 = 9, occupied; 10, 0 occupied; 1 free. Occupied: 0, 1, 7, 8, 9, 10. Of the options only position 2 is empty. Answer: (C) 2.

Concept: Linear probing wraps around from the last slot to slot 0, which is how 24 ends up at 1. Forgetting the wrap leaves 1 wrongly empty.

S1: every path of length at most k is also of length at most k + 1, so the minimum over the larger set cannot be larger: true. S2: weights are integers and may be negative. Let s-u have weight 5 and u-v weight -3 with no other edges. The shortest s to v path is s-u-v using (u, v), with weight 2. For k = 2, d₂(u) = 5 > d₂(v) = 2. Also for k = 1, d₁(v) = ∞ while d₁(u) = 5, but the k = 2 case already breaks S2. So S2 is false. Answer: (A) Only S1 is true.

Concept: Hop-bounded distances (as in Bellman-Ford rounds) are monotone non-increasing in k. 'Predecessor is closer' fails once negative edges are allowed, which 'integer weights' quietly permits.

(A) Cycle property: with distinct weights the heaviest edge on any cycle is in no MST. True. (B) False: vertices a, b, c, d with ab = 5, bc = 6, ca = 7, ad = 1, db = 2. In cycle a-b-c, ab is the lightest, but ab is the heaviest on cycle a-b-d, so it is in no MST. (C) False: if v has degree 1, its only edge is both the heaviest and lightest at v and must be in every MST. (D) Cut property on the cut ({v}, V - {v}): the lightest crossing edge is in every MST. True. Answer: (A), (D).

Concept: Cycle property excludes the heaviest edge of a cycle; cut property includes the lightest edge across a cut. The lightest edge of a cycle has no such guarantee.

By the parenthesis theorem, two DFS intervals are either nested or disjoint, so the overlapping pattern (D) can never occur in any graph. (A): v nested in u, a tree or forward edge, fine in a DAG. (C): v finished before u was discovered, a cross edge, fine. (B): u nested inside v means u is a descendant of v, so (u, v) is a back edge, which implies a cycle, impossible in a DAG. Answer: (B), (D).

Concept: Parenthesis theorem plus edge classification: a directed graph is acyclic iff DFS finds no back edge. That is also why reverse finishing order is a topological sort.

2^(log₂ n) = n. log(n!) = Θ(n log n) by Stirling. Any polynomial beats a logarithm, so log n < n^(1/3) < n. Hence log n, n^(1/3), 2^(log n), log(n!). Answer: (A).

Concept: Simplify before comparing: 2^(log₂ n) is just n, and log(n!) is Θ(n log n). The trap is treating 2^(log n) as exponential and putting it last.

(A) unrolls to T(n) = n: Θ(n). (B) by the master theorem, a = 2, b = 2, n^(log_b a) = n dominates f(n) = 1, so Θ(n). (C) f(n) = n equals n^(log_b a), so Θ(n log n). (D) sums 1 + 2 + ... + n = Θ(n²). Answer: (A) and (B).

Concept: Solving recurrences by unrolling and the master theorem. The trap is (B): two half-size calls with constant work still total Θ(n), not Θ(log n).

k mod 9: 5→5, 28→1, 19→1, 15→6, 26→8, 33→6, 12→3, 17→8, 10→1. Slot 1 holds 28, 19, 10 (3 keys); slots 6 and 8 hold 2 each; others at most 1. Longest chain = 3. Answer: 3.

Concept: Separate chaining: just compute each bucket and count. The usual slip is an arithmetic error in a mod computation.

Level 1: [10]+[7] not void; [8]+[19] void; [41]+[35] not void; [25]+[31] void. Level 2: [7,10]+[8,19] not void (8 < 10); [35,41]+[25,31] not void. Level 3: [7,8,10,19]+[25,31,35,41] void (19 < 25). A merge is void exactly when max(L) < min(R). Total = 3. Answer: 3.

Concept: Trace top-down merge sort level by level; a merge is void when the largest element of L is below the smallest of R. The trap is checking the original unsorted halves instead of the sorted subarrays.

Topologically sort the DAG in Θ(m + n), then relax the outgoing edges of each vertex in topological order. Every edge is relaxed once, and when a vertex is processed its distance is final. Total Θ(m + n), and every edge may need to be examined, so this is optimal. It also handles negative weights. Answer: (A).

Concept: DAG shortest paths need no priority queue. The trap is reaching for Dijkstra (B) or Bellman-Ford (C) without exploiting acyclicity.

Let dᵢ = A[i+1] - A[i] for i = 1..n-1. The condition says dᵢ > dⱼ whenever i > j, i.e. the difference sequence is strictly increasing. By transitivity it suffices to check dᵢ₊₁ > dᵢ for consecutive i: one pass, Θ(n). A lower bound of Ω(n) holds because any unread element could break the condition. Answer: (A) Θ(n).

Concept: A condition over all pairs often reduces to adjacent pairs via transitivity. The trap is checking all pairs in Θ(n²) or thinking binary search applies.

T[i][j] depends on T[i-1][j] (row above) and T[i][j-1] (left). Boundary entries are already 1. B1 fills row by row, left to right, so both dependencies are final when used: correct. B2 fills anti-diagonals i + j = s in increasing s; both dependencies lie on diagonal s - 1 (or on the boundary), already computed: correct. B2 is just slower (Θ(n³)). Answer: (A).

Concept: A DP evaluation order is valid if every entry's dependencies are computed before it. Both row-major and anti-diagonal orders satisfy this. The trap is judging B2 wrong because of its wasted iterations.

h(1) = 3 -> slot 3. h(4) = 12 mod 10 = 2 -> slot 2. h(5) = 15 mod 10 = 5 -> slot 5. h(6) = 18 mod 10 = 8 -> slot 8. h(14) = 42 mod 10 = 2: slot 2 full, 3 full, 4 free -> slot 4. h(15) = 45 mod 10 = 5: slot 5 full, 6 free -> slot 6. Answer: (D) 4 and 6.

Concept: Linear probing moves to the next free slot on a collision. The trap is reporting the home slot (2 and 5) instead of where the key actually lands after probing.

Binary search needs sorted data (otherwise discarding half the range is unjustified) and O(1) access to the middle element. An unsorted array or list fails the first requirement. A sorted linked list fails the second: reaching the middle takes O(n) steps, so the total is O(n). Only a sorted array gives O(log n). Answer: (C).

Concept: Binary search requires both order and random access. The trap is the sorted linked list: it has order but no random access, so it degrades to linear time.

Insertion sort makes one adjacent swap per inversion. The pair (15, 13) is always one inversion, so x must create exactly one more. x = 10: 11 > 10 before it - 1 inversion; 10 < 15, 13. Total 2. Yes. x = 12: nothing before it is larger, and 12 < 15, 13. Total 1. No. x = 14: 14 > 13 after it - 1 inversion. Total 2. Yes. x = 16: 16 > 15 and 16 > 13 - 2 inversions. Total 3. No. Answer: (A) 10, (C) 14.

Concept: Swaps in insertion sort equal the number of inversions. The trap is counting only inversions involving x and forgetting the fixed (15, 13) pair.

Each given shortest path has length 3, so no edge may create a shorter route between its endpoints. (b, d): a - b - d would have length 2 < 3. Not an edge. (b, h): a - b - h would have length 2 < 3. Not an edge. (e, g): e - g - h would have length 2 < 3. Not an edge. (b, g): it creates a - b - g - h (length 3, not shorter), and gives no shorter a-d or e-h path, so it may exist. Answer: (A), (C), (D).

Concept: An edge between two vertices of a shortest path that skips ahead would shorten it, so such edges cannot exist. The trap is ruling out (b, g), which only creates a path of equal length.

Each vertex i has out-edges to i + 2 and i + 1, visited in that order. DFS from 0 always takes the +2 edge first: 0, 2, 4, ..., 100 are discovered in that order. 100 has no out-edges. Backtracking: 98's next neighbour 99 is new, discovered (its neighbour 100 is done). Then 96 discovers 97, and so on down to 0 discovering 1. Discovery order: 0, 2, ..., 100, then 99, 97, ..., 1. After 50: the evens 52, ..., 100 (25 vertices) and all 50 odd vertices. Total = 25 + 50 = 75.

Concept: Adjacency order decides the DFS path: the larger neighbour first means a dive along even vertices, and odd vertices are found only during backtracking. The trap is assuming 51 is found right after 50.

T is a subgraph of G, so the unique u-v path in T is also a path in G. The shortest u-v distance in G is at most the length of that path: d1 ≤ d2. Equality need not hold: in a triangle with weights 2, 2, 3, the MST drops the 3-edge, and its endpoints are 3 apart in G but 4 apart in T. Equality can also hold (u, v adjacent by an MST edge), so (D) fails. Answer: (B).

Concept: An MST minimises total weight, not pairwise distances; it is not a shortest-path tree. Removing edges can only lengthen shortest paths.

Divide by 2ⁿ: let U(n) = T(n)/2ⁿ. Then U(n) = U(n - 1) + n with U(0) = 1. So U(n) = 1 + (1 + 2 + ... + n) = 1 + n(n + 1)/2 = Θ(n²). Hence T(n) = 2ⁿ U(n) = Θ(n²2ⁿ). Answer: (A).

Concept: Normalising by the homogeneous solution 2ⁿ turns it into a sum. The trap is Θ(n2ⁿ), ignoring that the n·2ⁿ term accumulates over n levels.

fun() is bubble sort; each swap removes exactly one inversion. A descending array of n distinct values has every pair inverted: n(n - 1)/2 inversions. For n = 30: 30 x 29 / 2 = 435 swaps. Answer: 435.

Concept: Bubble sort swaps = number of inversions. Reverse-sorted input is the worst case, giving the maximum C(n, 2).

A BFS tree from root r has height equal to the eccentricity e(r), the largest d(r, v). Take u, v with d(u, v) = 30. By the triangle inequality 30 ≤ d(u, r) + d(r, v) ≤ 2e(r), so e(r) ≥ 15. Height 15 occurs from a central vertex (e.g. middle of a path) and 30 from an endpoint, so neither "exactly" option holds for every G, and "at least 30" fails for a central root. Answer: (C).

Concept: BFS tree height = eccentricity of the root, which lies between radius and diameter, and radius ≥ diameter / 2. Trap: assuming BFS height always equals the diameter.

Edge BC is in every MST iff it is strictly lighter than the heaviest edge on every other B-C path (cycle property). Other B-C paths and their maximum edge: B-A-C max(7, 3) = 7; B-D-C max(1, 8) = 8; B-D-A-C max(1, 6, 3) = 6; B-A-D-C max(7, 6, 8) = 8. The smallest of these is 6, so we need x < 6. At x = 6, the MST {BD, AC, AD} avoids BC. Largest integer: x = 5. Answer: 5.

Concept: An edge is in every MST iff every alternative path between its endpoints contains an edge strictly heavier than it. Trap: answering 6, where a tie lets another MST exclude BC.

63 mod 11 = 8 → slot 8. 50 mod 11 = 6 → slot 6. 25 mod 11 = 3 → slot 3. 79 mod 11 = 2 → slot 2. 67 mod 11 = 1 → slot 1. 24: h1 = 2 (occupied), h2 = 1 + (24 mod 7) = 1 + 3 = 4. i = 1: (2 + 4) mod 11 = 6 (occupied). i = 2: (2 + 8) mod 11 = 10, free. Key 24 goes to slot 10. Answer: 10.

Concept: Double hashing steps by h2(k) on each collision. Traps: using linear probing (slot 4) or forgetting h2 adds 1 to k mod 7.

Pick any two elements and compare them once. The smaller one cannot be the largest element of the list, since the other is bigger. Zero comparisons cannot work because no element is known to be non-maximal. Answer: (A) 1.

Concept: Read the question: any non-largest element is enough, not the largest itself. The trap is answering N - 1, the cost of finding the maximum.

(A) False: in a triangle s-a-b, DFS may go s-a-b, giving b depth 2 though its distance is 1. (B) True: in an undirected DFS there are no cross edges; every non-tree edge joins an ancestor and a descendant. (C) True: for any edge (u, v), BFS levels satisfy |d(u) - d(v)| ≤ 1, otherwise the farther vertex would have been discovered earlier. (D) True: repeatedly starting either traversal from an unvisited vertex labels components. Answer: (B), (C), (D).

Concept: Key edge properties: undirected DFS has only tree and back edges; BFS non-tree edges join the same or adjacent levels. Only BFS gives shortest paths in unweighted graphs.

Every spanning tree has exactly n - 1 edges, so each tree's weight rises by (n - 1)α and the ranking of trees is unchanged: every MST stays an MST. A path with k edges rises by kα, so paths with more edges are penalized more. Example: s-t direct weight 3, s-a-t with weights 1 and 1. Before, s-a-t (2) is shortest; after adding 2, direct = 5 and s-a-t = 6. SPs need not remain SPs. Answer: (C).

Concept: MSTs depend only on the relative order of edge weights; shortest paths depend on sums over paths of varying length. Multiplying all weights by a positive constant would preserve both.

Find the peak by binary search: compare A[mid] with A[mid+1]; if increasing, the peak is to the right, else at or to the left. This takes O(log n). Then binary search the increasing part and the decreasing part separately, O(log n) each. Total O(log n). A lower bound of Ω(log n) holds because a sorted array is a special bitonic array. Answer: (D) Θ(log n).

Concept: Decompose into peak-finding plus two ordinary binary searches. The trap is (C), assuming nested binary searches.

Two BFS passes on a tree return its diameter: the first BFS ends at an endpoint of a longest path, the second measures that path. Longest paths here: N-M-K-H-E-F-G and N-M-K-H-E-C-A, each with 6 edges. Check: from E the farthest vertices are N (4 edges) and A, G, D (2 edges), so no path is longer than 4 + 2 = 6. Answer: 6.

Concept: Double BFS computes the diameter of a tree exactly (not of general graphs). Count edges along the longest path, not vertices.

To insert a key with open addressing we probe until an empty slot is found, which is exactly the probe sequence of an unsuccessful search for that key. Hence the expected number of probes for insertion is at most 1/(1 - α). Answer: (B) 1/(1 - α).

Concept: Insertion in open addressing equals an unsuccessful search. The trap is the expression (1/α) ln(1/(1 - α)), which bounds a successful search, not an insertion.

Binary search compares the target with the middle element (1 comparison) and then continues in one half; excluding the middle, the larger half has ⌊n/2⌋ elements. So the worst case satisfies F(n) = F(⌊n/2⌋) + 1, giving F(n) = ⌊log₂ n⌋ + 1. (B) would search both halves, (C) has no cost per step, (D) describes linear search. Answer: (A).

Concept: Recurrence for binary search. The trap is (B), the shape of a divide-and-conquer that recurses into both halves, like merge sort.

BFS: expand 1 (adds 2, 3); expand 2 (adds 4; 3 already listed); expand 3 (adds 5); expand 4 (adds 6); expand 5 (adds 7); then 6 is reached. Expansion order 1, 2, 3, 4, 5. DFS with ascending order: expand 1 (2, 3), take the smallest, 2 (adds 4), then the smallest unexpanded 3 (adds 5), then 4 (adds 6), then 5, then 6. Because every new child is n+1 or n+2 and the smallest unexpanded number is always the next integer, both strategies expand states in the order 1, 2, 3, 4, 5 before the goal 6. They expand the same number of states. Answer: (C).

Concept: Here ascending-order tie-breaking makes BFS and DFS follow the identical sequence. The trap is assuming DFS dives deep along n+2 and so expands fewer states.

Bubble sort: pass 1 gives [3, 2, 1, 4, 5], pass 2 gives [2, 1, 3, 4, 5]: not sorted. Insertion sort: pass 1 inserts 3 giving [3, 4, 2, 1, 5], pass 2 inserts 2 giving [2, 3, 4, 1, 5]: not sorted. Selection sort: pass 1 swaps the minimum 1 into position 1 giving [1, 3, 2, 4, 5], pass 2 swaps the minimum of the rest, 2, into position 2 giving [1, 2, 3, 4, 5]: sorted. Answer: (B) (iii) only.

Concept: Tracing what one pass of each elementary sort achieves. The trap is assuming bubble sort finishes quickly because 5 is already in place; it moves the small values left only one step per pass.

A valid order must put each edge's tail before its head: P and R before Q; Q before S and V; S before U; V before T. (A) Q comes before R: invalid (also T before V). (B) P, R, Q, then V, S, U, T: every constraint holds: valid. (C) Q before R: invalid. (D) P, R, Q, S, V, T, U: S before U, V before T: valid. Answer: (B), (D).

Concept: Topological order respects every edge direction. The trap is overlooking that Q has two predecessors, so both P and R must precede it.

In the worst case (the array is sorted, or the violation is at the end) the single pass makes about N − 1 comparisons, each O(1). So worst-case time is Θ(N), which means it is both O(N) and Ω(N). Answer: (A).

Concept: Θ(N) implies both O(N) and Ω(N). The trap is associating Ω only with best-case analysis; here the bound is on the worst case.

Divide by n: T(n)/n = T(√n)/√n + 1. Let S(n) = T(n)/n, so S(n) = S(√n) + 1. Taking square roots repeatedly reaches a constant after log log n steps, so S(n) = Θ(log log n) and T(n) = Θ(n log log n). Answer: (A).

Concept: Normalise by n (or substitute n = 2^(2^k)) to turn the square-root recurrence into a simple count. The trap is treating it like T(n) = 2T(n/2) + n and answering n log n.

Forward edges: an edge u → w to a non-child descendant puts w at least two levels below u, but BFS from v would discover w at depth(u) + 1 via that edge, so T could not be a BFS tree. Hence no forward edges: (C) true. Back edges can exist (v → u and u → v). Cross edges can exist: with v → a, v → b, b → a, DFS visits a then b, and b → a is a cross edge, while BFS gives the same tree. So (A), (B), (D) fail. Answer: (C).

Concept: A BFS tree has no edge that skips a level downward. The trap is assuming the tree must contain every edge or that cross edges are impossible.

DFS on an undirected graph gives a spanning forest with one tree per connected component. A forest with V vertices and c trees has V − c edges. So 100 − c = 40 and c = 60. Answer: 60.

Concept: Edges in a spanning forest = vertices − components. The trap is thinking DFS yields a single tree.

The elements kept unchanged must already form a non-decreasing subsequence, and any such subsequence can be kept (integers can fill the gaps since values may repeat). So distance = n − length of the longest non-decreasing subsequence. Here 2, 3, 4, 6 (positions 1, 3, 5, 7) has length 4, and no length-5 non-decreasing subsequence exists. Distance = 7 − 4 = 3 (e.g. 2, 3, 3, 3, 4, 4, 6). Answer: 3.

Concept: Reduces to the longest non-decreasing subsequence. The trap is counting inversions or out-of-place elements instead.

first is the previous element and second the other value in the current two-value window. If X[i] equals second (not first), the window still has two values, so len2++; but the run of equal values ending at X[i] restarts, so len1 = 1 (P = 1). If X[i] is a new third value, the longest two-value subarray ending at X[i] is the run of the previous value (length len1) plus X[i]: len2 = len1 + 1 (Q). Answer: (B) (P) 1, (Q) len1+1.

Concept: Maintaining run-length invariants. When a new value appears, only the trailing run of the previous value can stay in the window - not the whole old window (len2+1 is the trap).

Take any cycle C and two edges e, f on it. Extend the path C − f to a spanning tree T (it contains e, not f). T − e + f is also a spanning tree, and both have even weight, so w(f) − w(e) is even: e and f have the same parity. Hence every cycle is all-even or all-odd: (D) true. Counterexamples: a triangle with weights 1, 1, 1 (every spanning tree weighs 2) breaks (A) and (C); a path (a tree) with weights 1, 1, 2 has its only spanning tree of weight 4, breaking (B). Answer: (D).

Concept: Spanning-tree exchange: swapping one cycle edge for another keeps a spanning tree, so cycle edges must share parity. Edges not on a common cycle (bridges) can differ.

Take all weight-1 edges (no cycle): a-b, a-f, c-d, d-e. Components: {a,b,f}, {c,d,e}, {g}. Two more edges are needed. The cheapest connections are weight 2, all through g: g to {a,b,f} via a-g, b-g or f-g (3 choices) and g to {c,d,e} via c-g, d-g or e-g (3 choices). The direct links between {a,b,f} and {c,d,e} (b-c, f-e) weigh 3, so they never appear. MST weight 4 + 4 = 8 and the count is 3 × 3 = 9. Answer: 9.

Concept: Counting MSTs with ties: contract the forced lighter edges, then multiply the number of equal-weight choices for each required connection.

Any fixed hash function (division or multiplication method) is known to the adversary, who can then choose keys that all hash to the same slot, giving Θ(k) chains. Universal hashing picks the hash function at random from a universal family at run time, so for any fixed set of keys the expected number of collisions for a pair is at most 1/m, regardless of how the keys were chosen. Answer: (C) Universal hashing method.

Concept: Randomisation defeats a malicious input generator. The trap is believing a carefully chosen constant or a prime modulus helps; any deterministic function can be attacked.

n ≤ n² for all n ≥ 1, so f ∈ O(g). Moreover f(n)/g(n) = 1/n → 0, so f ∈ o(g) (strictly slower growth). Since the ratio tends to 0, there is no constant c > 0 with n ≥ c·n² for all large n, so f ∉ Ω(g) and therefore f ∉ Θ(g). Answer: (A) and (C).

Concept: Little-o means the ratio tends to 0, which implies big-O but rules out Ω and Θ. The trap is marking only O and forgetting that o also holds.

f1(n) = n + floor(n/2) + floor(n/4) + ... (while the value exceeds 1), which lies between n and 2n, so f1(n) = Θ(n). f2(n) = 100n = Θ(n). Hence f1 ∈ Θ(f2) and f1 ∈ O(n). Since the ratio f1/f2 stays between 1/100 and 1/50 (roughly), it neither tends to 0 nor to infinity, so o and ω are false. Answer: (A) and (D).

Concept: A geometric series n + n/2 + n/4 + ... sums to under 2n, so the halving loop is linear, not n log n. Constant factors like 100 do not affect Θ.

G has 8 vertices. ∅ is a proper subset of every other subset, so ∅ is adjacent to all 7 other vertices. BFS from ∅ visits ∅ first and then discovers all 7 neighbours at level 1; they may be enqueued in any order, and once they are all discovered nothing else remains. So every ordering of the 7 non-empty subsets is a valid BFS order: 7! = 5040. Answer: 5040.

Concept: BFS order freedom comes from the order in which neighbours are enqueued. Because the start vertex is adjacent to everything, the count is simply 7!.

Polynomial f(n) = a·nᵏ + lower terms: f(n²) ~ a·n²ᵏ and f(n)² ~ a²·n²ᵏ, same order, so (A) holds. Exponential f(n) = 2ⁿ: f(n²) = 2^(n²) while f(n)² = 2^(2n), so f(n²) is not O(f(n)²) - (C) fails, and this also kills (B). For f(n) = log n: f(n²) = 2 log n while f(n)² = log²n, so f(n²) is not Ω(f(n)²) - (D) fails. Answer: (A).

Concept: Test each claim with a polynomial, an exponential and a slow function like log n. The trap is (D): squaring the input grows polynomials and exponentials faster, but not logarithms.

Each key, whether hashed by h₁ or h₂, lands in any particular slot with probability 1/m because both functions are simple uniform. By linearity of expectation, the expected number of keys in a slot is n × (1/m) = n/m. Splitting keys between two uniform functions changes nothing. Answer: (B) n/m.

Concept: Load factor α = n/m under simple uniform hashing. The trap is thinking two functions halve or double the load.

Think of Kruskal. (A) The two lightest edges can never form a cycle, so both are picked: true. (B) The third edge is rejected only if edges 1, 2, 3 form a triangle. Then the fourth edge would be rejected only if it closed a cycle with edges 1 and 2, i.e. joined the same pair as edge 3, impossible in a simple graph. So at least one of them is picked: true. (C) Cut property: with distinct weights, the lightest edge crossing any cut is in every MST: true. (D) Distinct weights give a unique MST: false. Answer: (A), (B), (C).

Concept: Kruskal's order and the cut property. The trap is (D): multiple MSTs need tied weights.

(I) In an undirected DFS, when an edge (u, v) is examined from u and v is unvisited, v becomes a descendant of u; if v is already visited it must be an ancestor or descendant, since u's subtree is finished before DFS backs out. So every non-tree edge is a back edge and there are no cross edges: true. (II) In BFS, edge endpoints differ in depth by at most 1, but can be at the same depth: in a triangle x-y-z rooted at x, y and z are both at depth 1 and the edge y-z has |i - j| = 0. False. Answer: (A) I only.

Concept: Undirected DFS has only tree and back edges; BFS non-tree edges join the same or adjacent levels. The trap is reading BFS's "at most 1" as "exactly 1".

Dimensions p = 2, 25, 3, 16, 1, 1000. Pairs: m12 = 150, m23 = 1200, m34 = 48, m45 = 16000. m13 = min(150 + 96, 1200 + 800) = 246. m24 = min(48 + 75, 1200 + 400) = 123, via F₂(F₃F₄). m35 = min(16000 + 48000, 48 + 3000) = 3048. m14 = min(123 + 50, 150 + 48 + 6, 246 + 32) = 173, via F₁(F₂(F₃F₄)). m15: split after F₄ gives 173 + 2·1·1000 = 2173; after F₂ gives 150 + 3048 + 6000 = 9198; others are larger. Optimum ((F₁(F₂(F₃F₄)))F₅) = 2173. The only directly multiplied adjacent pair is F₃F₄. Answer: (C).

Concept: Matrix chain multiplication DP. The 16×1 and 1×1000 shapes make it cheap to collapse everything to a 2×1 matrix first, then multiply by F₅ once. The trap is greedily multiplying the cheapest-looking pairs, such as F₁F₂.

Edges T-B (1) and T-C (3) are the two cheapest and form no cycle, so every MST contains them. Vertex A joins through T-A or A-B, both weight 4, giving 2 choices (B-C, also 4, would close the cycle T-B-C and is never needed). Vertex R joins only through T-R (x) or C-R (5). If x = 5 both are equally cheap, giving 2 choices; any other x gives 1. Maximum number of MSTs = 2 × 2 = 4 with x = 5. Answer: 4.

Concept: Multiple MSTs arise from ties among the cheapest edges crossing a cut. Choosing x equal to the competing edge (5) creates a tie for R. The trap is counting B-C as a third option for A; it never crosses the cut that separates A.

Ratios: item 4 = 12, item 1 = 6, item 3 = 5, item 2 = 4. Greedy takes item 4 (2 kg, 24); item 1 (10 kg) would make 12 kg, so it is skipped; item 3 (4 kg) fits, total 6 kg, 44; item 2 (7 kg) would make 13 kg, skipped. V_greedy = 44. Optimal: item 1 alone gives 60; no other item fits with it (10 + 2 = 12). Other subsets: 2 + 4 = 52, 2 + 3 = 48, 3 + 4 = 44. V_opt = 60. Difference = 60 - 44 = 16. Answer: 16.

Concept: Greedy by value/weight is optimal only for fractional knapsack; 0/1 knapsack needs DP or exhaustive search. The trap is letting greedy stop at the first item that does not fit; it continues down the list.

a is the only source, so it comes first; f is the only sink, so it comes last. In between, b must precede c and d must precede e, with no constraint between the two chains. The number of interleavings of two chains of length 2 is C(4, 2) = 6. Answer: 6.

Concept: Counting topological orders as interleavings of independent chains. The trap is listing orders by hand and missing some, or treating b, c, d, e as freely permutable (24).

Insertion sort: a reverse-sorted input forces i shifts for the i-th element, Θ(n²). Merge sort always splits in half and merges in linear time, Θ(n log n) in every case. Quick sort: with consistently bad pivots (e.g. sorted input with first-element pivot) partitions are of size n-1 and 0, Θ(n²). Answer: (D).

Concept: Worst-case complexities of the standard sorts. The trap is quoting quick sort's average Θ(n log n) as its worst case.

P: Every spanning tree has exactly V - 1 edges, so adding c to each edge adds (V - 1)c to every tree; the relative order of edge weights (which Kruskal uses) is unchanged. The MST stays the same. P is true. Q: Paths have different numbers of edges, so a path with k edges increases by kc. Example: A-B weight 3 directly vs A-C-B with weights 1 + 1 = 2. Adding 2 to each edge gives 5 vs 6, so the shortest path changes. Q is false. Answer: (A) P only.

Concept: MSTs depend only on the order of weights; shortest paths depend on sums over paths of different lengths. The trap is assuming both are invariant.

Edges: {1,2} = 2, {1,3} = 8, {1,4} = 5, {2,3} = 5, {2,4} = 8, {3,4} = x. The edge {3,4} is most useful for the pair (3, 4). Without it, the shortest 3-4 route is 3-2-1-4 = 5 + 2 + 5 = 12 (3-1-4 and 3-2-4 cost 13). So the direct edge lies on a shortest path whenever x ≤ 12 (at x = 12 it ties, and 'at least one shortest path' still includes it). For other pairs the edge would need a much smaller x (e.g. for (1,3), 5 + x ≤ 7 needs x ≤ 2). Largest integer x = 12. Answer: 12.

Concept: An edge lies on some shortest path iff its weight does not exceed the best alternative between its endpoints. The trap is using strict inequality and answering 11.

Kruskal always takes edges 1 and 2 (two edges cannot form a cycle). To make the MST heavy, edge 3 should close a cycle: place edges 1, 2, 3 as a triangle on three vertices, so edge 3 is rejected. The fourth vertex is joined by edges 4, 5, 6, and Kruskal takes 4. MST weight = 1 + 2 + 4 = 7. If edges 1 and 2 do not form a path with 3 completing a triangle, edge 3 is accepted and the weight is only 1 + 2 + 3 = 6. Maximum = 7. Answer: 7.

Concept: Adversarial edge placement against Kruskal's algorithm. The trap is answering 6 + 5 + 4 or ignoring that edges 1 and 2 are always chosen.

II is the cycle property: if e is the unique heaviest edge on a cycle and some spanning tree contains e, removing e and adding another edge of that cycle reconnecting the tree gives a lighter spanning tree. So no MST contains e. II is true. I is false: an edge can be the lightest on one cycle and the heaviest on another. Take vertices X, Y, Z, W with XY = 1, YZ = 2, XZ = 3, ZW = 4, WX = 5. XZ = 3 is the lightest edge of cycle X-Z-W, yet it is the heaviest edge of triangle X-Y-Z, so by the cycle property no MST contains it (the MST is XY, YZ, ZW). Answer: (B) II only.

Concept: Cycle property: the unique heaviest edge of any cycle is in no MST. The trap is believing the converse for the lightest edge; an edge can be lightest on one cycle and heaviest on another.

Floyd-Warshall computes d_k(i,j), the shortest path using only intermediate vertices from {1..k}, from the k - 1 table: d_k(i,j) = min(d_(k-1)(i,j), d_(k-1)(i,k) + d_(k-1)(k,j)). Overlapping subproblems solved bottom-up in a table is dynamic programming. Answer: (C) Dynamic Programming paradigm.

Concept: Floyd-Warshall and Bellman-Ford are DP; Dijkstra and Prim are greedy. The recurrence over growing sets of allowed intermediate vertices is the giveaway.

Dimensions p = 10, 5, 20, 10, 5. Pairs: A₁A₂ = 1000, A₂A₃ = 1000, A₃A₄ = 1000. Triples: A₁..A₃ = min(1000 + 10·20·10, 1000 + 10·5·10) = 1500; A₂..A₄ = min(1000 + 5·10·5, 1000 + 5·20·5) = 1250. Full: split after A₁: 1250 + 10·5·5 = 1500; after A₂: 1000 + 1000 + 10·20·5 = 3000; after A₃: 1500 + 10·10·5 = 2000. Minimum 1500, from A₁((A₂A₃)A₄). Answer: 1500.

Concept: Matrix chain multiplication DP: m[i][j] = min over k of m[i][k] + m[k+1][j] + pᵢ₋₁pₖpⱼ. Greedy left-to-right order is not optimal.

Count recursive calls on the longest path: 1 (before decision 1) + 2 (decision 1 right branch) + 1 (after decision 2) + 1 (decision 3 call) = 5 calls of A(n/2). Worst case T(n) = 5T(n/2) + O(1). By the master theorem T(n) = Θ(n^(log₂ 5)), and log₂ 5 ≈ 2.32. Answer: 2.32 (accepted range 2.2 to 2.4).

Concept: Worst-case path through branching code determines the recurrence. With a = 5, b = 2 and constant extra work, the master theorem gives n^(log₂ 5). Counting all calls in the chart (6) instead of one path is the trap.

DFS visits each vertex once. When a vertex is visited, finding its neighbours in an adjacency matrix means scanning its entire row of n entries, regardless of how many edges it actually has. n vertices × n entries = Θ(n²). Answer: (C) Θ(n²).

Concept: The cost of DFS/BFS depends on the representation: Θ(n + m) with adjacency lists, Θ(n²) with an adjacency matrix. The trap is quoting Θ(n + m) out of habit.

The graph has no cycle, so a topological order exists. P and S have no incoming edges. R has incoming edges from P and S only. Q has incoming edges from P, R and S. So P and S must come first (in either order), then R, then Q. The valid orders are PSRQ and SPRQ. PQRS fails (Q before R), SRQP fails (P last), and PSRQ is not unique. Answer: (C).

Concept: A topological order places every vertex after all its predecessors; when two sources are independent, both orders are valid. The trap is assuming the order is unique.

Rewrite in nested (Horner-like) form: P(X) = ((X² + 4)·X² + 6)·X + 5. With one temporary t: t = X * X (1) t = t + 4 (2) t = t * X (3) t = t * X (4) now t = X⁴ + 4X² t = t + 6 (5) t = t * X (6) t = t + 5 (7) Seven operations. Fewer is not possible with one temporary, since X² cannot be kept while t is reused. Answer: 7.

Concept: Horner-style factoring to minimise operations. The trap is computing X² once and reusing it, which needs a second temporary (giving 6 with two variables).

Recursion depth = number of vertices on the DFS stack = length of a simple path DFS can follow, and DFS can be steered along any simple path. So find the longest simple path. Colour each 3 × 3 grid like a chessboard: corners and centre (5) versus edge-middles (4). A path through all 9 vertices must start and end on corners/centre. Path: snake through all 9 of the left grid ending at corner L(3,3) (9), go to X (10), enter R(3,1), a corner, and snake through all 9 of the right grid ending at a corner (19). To also reach Z the path would have to end the right grid at R(2,3), an edge-middle, which forces skipping a grid vertex, so still 19. Y is a dead end beside X. Answer: 19.

Concept: DFS recursion depth equals the longest simple path DFS can be steered along. The trap is counting all 21 vertices, ignoring the pendant vertices and the grid parity constraint.

Any fixed pivot rule (first, last or middle element) has an adversarial input where the chosen pivot is always the smallest or largest remaining element. Each partition then removes only one element, giving n + (n - 1) + ... = Θ(n²) comparisons. Choosing the middle position is not the same as choosing the median value. Answer: (A) O(n²).

Concept: Worst-case quicksort with a deterministic pivot position is quadratic. The trap is confusing 'central element' with the median, which would give O(n log n).

From position 9 there are exactly two possible moves: a unit step to 10, or the shortcut to 15 (9 is involved in only this one shortcut). Each costs one step, so T(9) = 1 + min(T(10), T(15)). Hence {y, z} = {10, 15} and yz = 150. Answer: 150.

Concept: Writing the DP recurrence from the available transitions. The trap is overthinking other shortcuts; 'at most one shortcut involving any number' rules them out at 9.

With simple uniform hashing each key independently lands in any of the 100 slots with equal probability, and chaining lets several keys share a slot. For the first 3 slots to stay empty each insertion must land in one of the other 97 slots: probability 97/100 each, independently. Total = (97 × 97 × 97)/100³. Answer: (A).

Concept: Independence of insertions under uniform hashing with chaining. The trap is option C, which assumes later keys cannot reuse an occupied slot (as with open addressing).

Each iteration takes the midpoint k. If x < listA[k] only j = k - 1 runs; if x > listA[k] only i = k + 1 runs; the range shrinks every time, so the loop terminates (A false). If x == listA[k], both conditions hold: j = k - 1 and i = k + 1, so i > j and the loop exits with k pointing at x, and the function returns k. So it finds x when present (D false) and returns -1 otherwise. This is binary search; it searches for x, not the maximum (C false). Answer: (B).

Concept: Tracing a binary search with two non-exclusive ifs. The trap is thinking the equality case causes an extra step that loses k; both updates fire together and end the loop at the right index.