UGC NET CS Practice Set 8

Explanation: Red-black trees are self-balancing BSTs with O(log n) height. Deletion involves finding the node O(log n), removing it, and performing at most O(log n) rotations and recolorings to restore the red-black properties. Total: O(log n).

Explanation: In DFS of a directed graph, a back edge (from a descendant to an ancestor in the DFS tree) indicates the presence of a cycle. A directed graph is acyclic (DAG) if and only if its DFS produces no back edges.

Explanation: A binary heap provides O(log n) insertion and O(log n) deletion of the min/max element, with O(1) peek. A sorted array gives O(1) deletion but O(n) insertion. An unsorted linked list gives O(1) insertion but O(n) deletion. A hash table doesn't maintain order.

Explanation: The DP solution for matrix chain multiplication fills an n×n table where each cell (i,j) considers all possible split points k between i and j. The three nested loops (chain length l, starting position i, split point k) give O(n³) time.

Explanation: In the subset construction (NFA to DFA conversion), each DFA state corresponds to a set (subset) of NFA states. The DFA state is accepting if it contains at least one accepting NFA state. The resulting DFA may have up to 2^n states for an n-state NFA.

Explanation: DFAs and NFAs are equivalent in power — they both recognize exactly the class of regular languages. Every NFA can be converted to an equivalent DFA using the subset construction (though the DFA may have exponentially more states). The key advantage of NFAs is succinctness.

Explanation: OSPF is a link-state routing protocol. Each router floods its link-state information to all other routers in the area, so every router builds a complete topology map (link-state database) and independently computes shortest paths using Dijkstra's algorithm.

Explanation: SLR parsing uses FOLLOW sets to determine when to reduce. A shift-reduce conflict occurs when a state has both a shift action and a reduce action on the same terminal. This happens because FOLLOW sets can be too imprecise, which is why LR(1) parsing (with lookahead in items) is more powerful.

Explanation: In the Chomsky hierarchy: Type 0 = recursively enumerable (TM), Type 1 = context-sensitive (linear bounded automata), Type 2 = context-free (PDA), Type 3 = regular (DFA/NFA). Each type is a proper subset of the one above: Type 3 ⊂ Type 2 ⊂ Type 1 ⊂ Type 0.

Explanation: AES (Rijndael) is a symmetric block cipher with a fixed block size of 128 bits and key sizes of 128, 192, or 256 bits (10, 12, or 14 rounds respectively). Unlike DES, AES does NOT use a Feistel network — it uses a substitution-permutation network (SPN).

Explanation: Mutation testing assesses the quality of a test suite by introducing small syntactic changes (mutations) to the program (e.g., changing + to −, swapping conditions) and checking if the test suite detects them (kills the mutant). A high mutation score indicates an effective test suite.

Explanation: A tree is a connected acyclic graph. A tree with n vertices always has exactly n − 1 edges. This is a fundamental property: removing any edge disconnects the tree, and adding any edge creates a cycle.

Explanation: An operator grammar is a context-free grammar where no production has two adjacent non-terminals on the right-hand side (no ε-productions allowed either). This enables operator-precedence parsing, which uses precedence relations (<, =, >) between terminal pairs to parse expressions.

Explanation: The wait-for graph is derived from the resource allocation graph by removing resource nodes and collapsing the edges. If process P waits for a resource held by process Q (P → Resource → Q), an edge P → Q is added in the wait-for graph. A cycle in this graph indicates deadlock.

Explanation: In a B+ tree, internal nodes store only keys and child pointers (acting as separators/index entries). Actual data records or pointers to data records are stored ONLY in leaf nodes. This is a key difference from B-trees, where data can appear in all nodes.

Explanation: Prim's algorithm grows the MST from a starting vertex by repeatedly adding the minimum-weight edge that connects a vertex in the tree to a vertex not yet in the tree. This is a cut property application. Kruskal's, in contrast, adds the globally lightest edge that doesn't form a cycle.

Explanation: Register allocation is modeled as graph coloring on the interference graph. Variables that are simultaneously live are connected by edges. Assigning k registers to variables without conflicts is equivalent to k-coloring the interference graph. Graph coloring is NP-complete in general.

Explanation: Dijkstra's algorithm assumes non-negative edge weights. With negative edges, a vertex marked as finalized may later have a shorter path discovered through a negative edge, violating the greedy invariant. Bellman-Ford handles negative weights (but not negative cycles).

Explanation: An unbalanced BST can degenerate into a linked list (e.g., inserting sorted data), giving height = n−1. Insertion requires traversing from root to leaf, which is O(height) = O(n) in the worst case. Self-balancing trees (AVL, red-black) guarantee O(log n).

Explanation: Radix sort processes d digits, performing a stable counting sort for each digit. Each counting sort is O(n + b) where b is the base (number of possible digit values). Total: O(d × (n + b)). For fixed d and b, this is O(n) — linear time.

Explanation: The greedy choice of always selecting the next activity with the earliest finish time (among those compatible with already selected activities) always yields an optimal solution for the unweighted activity selection problem. This is proved using exchange argument/greedy stays ahead.

Explanation: Bellman-Ford runs V−1 iterations of edge relaxation (sufficient for shortest paths in a graph without negative cycles, since shortest paths have at most V−1 edges). A V-th iteration that still reduces some distance proves a negative-weight cycle exists.

Explanation: The DP solution for LCS builds an (m+1)×(n+1) table where each cell is computed in O(1) time using the recurrence: if characters match, L[i][j] = L[i-1][j-1]+1; otherwise L[i][j] = max(L[i-1][j], L[i][j-1]). Total: O(m×n) time and space.

Explanation: Each router that forwards an IPv4 packet decrements the TTL by at least 1. If TTL reaches 0, the router discards the packet and sends an ICMP Time Exceeded message to the source. This prevents packets from looping indefinitely due to routing errors.

Explanation: Thrashing occurs when the system's working set of all active processes exceeds available physical memory. The system spends most of its time handling page faults (swapping pages between RAM and disk), causing CPU utilization to plummet. The working set model helps prevent it.

Explanation: L = {aⁿbⁿcⁿ | n ≥ 1} is NOT context-free (can be shown using the CFL pumping lemma). It IS context-sensitive: a linear bounded automaton can recognize it, and a context-sensitive grammar can generate it. It does not require a full Turing machine.

Explanation: UDP is connectionless, has no built-in reliability/ordering/flow control, and has minimal overhead (8-byte header vs TCP's 20). It is preferred for real-time applications (VoIP, video streaming, gaming, DNS queries) where low latency matters more than guaranteed delivery.

Explanation: The Dijkstra-Scholten algorithm detects termination in distributed computations built on a diffusing computation model. It maintains a spanning tree of the active processes and detects global termination when the tree collapses to the root and the root becomes idle.

Explanation: The iterative/incremental model allows revisiting earlier phases to accommodate changes. Each iteration goes through requirements → design → implementation → testing, with each cycle producing an increment of the software. The pure waterfall model does not support going back.

Explanation: Preimage resistance (one-wayness): given h, it's infeasible to find m with H(m) = h. Second preimage resistance: given m₁, it's infeasible to find m₂ ≠ m₁ with H(m₁) = H(m₂). Collision resistance: it's infeasible to find ANY two messages m₁ ≠ m₂ with H(m₁) = H(m₂).