UGC NET CS Practice Set 5

Explanation: An AVL tree maintains the property that the heights of left and right subtrees differ by at most 1. This balance guarantee ensures the height is always O(log n). Specifically, h < 1.4405 log₂(n+2) − 0.328.

Explanation: Dijkstra's algorithm uses a priority queue (min-heap) and requires all edge weights to be non-negative. It greedily selects the unvisited vertex with minimum distance. Time complexity is O((V+E) log V) with a binary heap.

Explanation: The DP solution uses a table of size (n+1) × (W+1). Each cell is computed in O(1) time, so the total complexity is O(n × W). This is pseudo-polynomial because W is not polynomial in the input size (which includes log W bits for W).

Explanation: An LRU cache needs O(1) access (hash map) and O(1) insertion/deletion at both ends and arbitrary positions (doubly linked list). The hash map stores key → node mappings, and the doubly linked list maintains the access order.

Explanation: While individual insertions may take O(n) when resizing, the total cost over n insertions is O(n). The doubling strategy ensures that expensive copies happen infrequently enough that the amortized cost per insertion is O(1) (shown by the aggregate or accounting method).

Explanation: Kruskal's algorithm sorts all edges in non-decreasing (increasing) order of weight and greedily adds the next lightest edge that doesn't form a cycle. Cycle detection is efficiently done using the Union-Find (Disjoint Set Union) data structure.

Explanation: Binary search halves the search space with each comparison. In the worst case (element not found or at the boundary), the number of comparisons is ⌊log₂ n⌋ + 1. For n=16, this is 4+1 = 5 comparisons.

Explanation: Counting sort is a non-comparison sorting algorithm that works by counting occurrences of each value. It runs in O(n + k) time where k is the range of input values. Merge sort, heap sort, and quick sort are all comparison-based with an Ω(n log n) lower bound.

Explanation: An adjacency matrix uses a V×V 2D array to represent edges, requiring O(V²) space regardless of the number of edges. An adjacency list uses O(V + E) space, which is more efficient for sparse graphs.

Explanation: Applying operator precedence: * has higher precedence than + and −. So A + (B*C) − D. Converting: B*C → BC*, then A + BC* → ABC*+, then ABC*+ − D → ABC*+D−.

Explanation: Building a heap using the bottom-up (sift-down) approach is O(n). Although there are O(n) nodes, most nodes are near the bottom and sift down only a short distance. The sum of sift-down distances is bounded by O(n), not O(n log n).

Explanation: Floyd-Warshall uses three nested loops over V vertices to consider all intermediate vertices for all pairs. Each iteration is O(1), giving a total of O(V³). It works with negative edges (but not negative cycles).

Explanation: The fractional knapsack problem can be solved optimally by a greedy algorithm: sort items by value/weight ratio and take items in decreasing order of this ratio, taking fractions if needed. The 0/1 knapsack, TSP, and LCS require DP or other approaches.

Explanation: In a circular queue using an array of size n, one slot is typically left empty to distinguish between full and empty states (both would have front == rear otherwise). So the maximum number of elements is n − 1.

Explanation: By the Master Theorem: a=2, b=4, f(n)=n^(1/2). log_b(a) = log₄(2) = 1/2. f(n) = n^(1/2) = n^(log_b a). This is Case 2, so T(n) = Θ(n^(1/2) log n) = Θ(√n log n).

Explanation: Topological sorting is a linear ordering of vertices in a directed graph such that for every edge u→v, u comes before v. This is only possible if the graph has no directed cycles (i.e., it is a DAG). A cycle would create contradictory ordering requirements.

Explanation: Once the DFA is built, pattern matching processes each character of the text exactly once (one state transition per character), giving O(n) matching time. Building the DFA takes O(m × |Σ|) time where |Σ| is the alphabet size, so total is O(m|Σ| + n).

Explanation: DFAs, NFAs, and regular expressions all recognize exactly the class of regular languages. This equivalence is established by the subset construction (NFA→DFA), Kleene's theorem (regex↔FA), and the Myhill-Nerode theorem.

Explanation: A DFA for divisibility by k has exactly k states, representing remainders 0, 1, ..., k−1. For divisibility by 3, we need 3 states (remainder 0 is the accepting state). State transitions are determined by: new_remainder = (2 × old_remainder + bit) mod 3.

Explanation: {aⁿbⁿ | n ≥ 0} is not regular — it requires matching the number of a's and b's, which needs unbounded counting. This is proved using the pumping lemma for regular languages. It is a context-free language recognized by a PDA.

Explanation: A pushdown automaton (NFA + stack) recognizes exactly the class of context-free languages. The equivalence between CFGs and PDAs is a fundamental result. Deterministic PDAs recognize a proper subset (deterministic CFLs).

Explanation: The halting problem (does a given TM halt on a given input?) is undecidable (proved by Turing via diagonalization). However, it is recognizable (recursively enumerable): we can simulate the TM and accept if it halts. Its complement (non-halting) is not even recognizable.

Explanation: The intersection of a regular language and a context-free language is always context-free. This is proved by the product construction: combining the DFA for L₁ with the PDA for L₂ to get a PDA for L₁ ∩ L₂. Note: the intersection of two CFLs is NOT necessarily context-free.

Explanation: An LL(1) parser uses FIRST and FOLLOW sets to build its predictive parsing table. FIRST(α) gives the set of terminals that can begin strings derived from α. FOLLOW(A) gives terminals that can appear immediately after non-terminal A.

Explanation: NP (Nondeterministic Polynomial) is the class of decision problems for which a 'yes' answer can be verified in polynomial time given a certificate/witness. Equivalently, they can be solved in polynomial time by a nondeterministic Turing machine. P ⊆ NP, and whether P = NP is open.

Explanation: SAT (Boolean Satisfiability) was the first problem proved NP-complete (Cook-Levin theorem). Shortest path and MST are in P. Sorting is also in P. SAT is NP-complete: it is in NP (a satisfying assignment is a polynomial-time verifiable certificate) and every NP problem reduces to it.

Explanation: Tokens (identifiers, keywords, numbers, operators) are defined by regular expressions and recognized by finite automata (DFA). Tools like Lex/Flex convert regular expression specifications into DFA-based lexical analyzers.

Explanation: LR(1) items include a lookahead symbol in each item, providing more precise information about when to reduce. SLR(1) uses FOLLOW sets (less precise) for reduction decisions. This makes LR(1) able to handle more grammars without conflicts.

Explanation: Common subexpression elimination (CSE) identifies expressions that are computed more than once and replaces redundant computations with the previously computed value. It is a machine-independent optimization because it operates on the intermediate code regardless of the target architecture.

Explanation: The grammar S → aSb adds one 'a' on the left and one 'b' on the right in each derivation, and S → ε terminates. After n applications of the first rule: S ⇒ aSb ⇒ aaSbb ⇒ ... ⇒ aⁿSbⁿ ⇒ aⁿbⁿ. So L = {aⁿbⁿ | n ≥ 0}.