UGC NET CS Practice Set 7

Explanation: In RL, the agent aims to maximize the expected cumulative (discounted) reward: R = Σ γ^t × r_t, where γ ∈ [0,1] is the discount factor. This balances immediate and future rewards. Maximizing only immediate reward is a greedy strategy that may not be globally optimal.

Explanation: Genetic algorithms are metaheuristic optimization algorithms inspired by the process of natural selection. They use operations analogous to biological evolution: selection (fitness-based), crossover (recombination), and mutation to evolve solutions over generations.

Explanation: A semantic network represents knowledge as a graph where nodes represent concepts/objects and labeled directed edges represent relationships between them (is-a, has-a, part-of, etc.). It supports inheritance through is-a hierarchies.

Explanation: Supervised learning uses labeled training data (input-output pairs) to learn a mapping function. Classification (discrete output) and regression (continuous output) are the two main supervised tasks. K-means is unsupervised (no labels).

Explanation: Alpha-beta pruning optimizes the minimax algorithm for game trees by eliminating branches that cannot affect the final decision. Alpha is the best value MAX can guarantee, beta is the best value MIN can guarantee. When alpha ≥ beta, the branch is pruned.

Explanation: NLP involves morphological analysis (word structure), syntactic parsing (sentence structure), semantic analysis (meaning), pragmatics (context), and discourse. Pixel-level image segmentation is a computer vision task, not NLP.

Explanation: IDDFS repeats DFS with increasing depth limits. Although nodes are revisited, the total work is dominated by the last iteration: (d+1)b^0 + d·b^1 + ... + 1·b^d = O(b^d), the same order as BFS. IDDFS combines BFS's completeness/optimality with DFS's linear space O(bd).

Explanation: Decision trees (e.g., ID3, C4.5) use information gain (reduction in entropy after splitting) to select the attribute that best separates the classes. CART uses Gini impurity. MSE is for regression, Euclidean distance for clustering/KNN.

Explanation: Resolution is a proof procedure that works on formulas in conjunctive normal form (CNF). The resolution rule: from (A ∨ B) and (¬B ∨ C), derive (A ∨ C). It is sound and complete for propositional logic. To prove a statement, negate it and show the resolvent leads to the empty clause.

Explanation: Backpropagation computes the gradient of the loss function with respect to each weight by applying the chain rule of calculus from the output layer backward through hidden layers. This enables efficient gradient computation for gradient descent optimization.

Explanation: The 'naive' assumption in Naive Bayes is that all features are conditionally independent given the class label: P(x₁,...,xₙ|C) = ∏P(xᵢ|C). Despite this strong (often unrealistic) assumption, Naive Bayes performs surprisingly well in practice for text classification and spam filtering.

Explanation: CSPs are solved using backtracking search enhanced with constraint propagation techniques like arc consistency (AC-3), forward checking, and heuristics like MRV (Minimum Remaining Values) and LCV (Least Constraining Value). Examples include Sudoku, map coloring, and scheduling.

Explanation: Hill climbing is a local search algorithm that iteratively moves to the neighbor with the highest value (for maximization). It is greedy, incomplete, and can get stuck at local optima, plateaus, and ridges. Variants include stochastic hill climbing and random restarts.

Explanation: Simulated annealing allows moves to worse states with a probability P = e^(−ΔE/T) that decreases as the 'temperature' T is gradually reduced. This helps escape local optima. At T=0 it behaves like hill climbing. The 'population' approach describes genetic algorithms.

Explanation: KNN is a lazy (instance-based) learner — it stores all training data and delays computation until a query is made. At prediction time, it finds the k nearest training examples and votes (classification) or averages (regression). There is no explicit training phase.

Explanation: A heuristic is admissible if it never overestimates the actual cost to reach the goal: 0 ≤ h(n) ≤ h*(n) for all n, where h*(n) is the true cost. Admissibility guarantees A* finds the optimal solution. h(n)=0 is admissible (reduces to Dijkstra's) but uninformative.

Explanation: Overfitting occurs when a model learns the training data too well, including noise and outliers, resulting in high accuracy on training data but poor generalization to unseen data. It is typically caused by excessive model complexity relative to the amount of training data.

Explanation: Q-learning is a model-free (no environment model needed), off-policy (learns optimal policy while following an exploratory policy) TD (temporal difference) method. It updates Q(s,a) ← Q(s,a) + α[r + γ max Q(s',a') − Q(s,a)]. It converges to optimal Q-values under sufficient exploration.

Explanation: Frames (Minsky, 1975) are structured knowledge representation units similar to objects in OOP. A frame has slots (attributes) with facets (constraints, default values, procedures). They support inheritance through is-a hierarchies, much like class inheritance in OOP.

Explanation: B does not appear on the right side of any FD, so B must be in every key. AB⁺ = {A,B,C,D} (AB→C→D) ✓. BC⁺ = {B,C,D,A} (C→D, D→A) ✓. BD⁺ = {B,D,A,C} (D→A, AB→C) ✓. All are minimal: B alone gives {B}, and A,C,D alone don't give all attributes. So the candidate keys are {AB, BC, BD}.

Explanation: In a B-tree of order m=5, each node has at most 4 keys and 5 children. At height 0: 1 node with 4 keys. At height 1: 5 nodes × 4 keys = 20. At height 2: 25 nodes × 4 keys = 100. Total = 4 + 20 + 100 = 124.

Explanation: Candidate key is A (A→B→C). A→B: left side is superkey, OK for 3NF/BCNF. B→C: B is not a superkey and C is not a prime attribute. This is a transitive dependency A→B→C, violating 3NF. There are no partial dependencies (single-attribute key), so it's in 2NF.

Explanation: The BST has root 50, left subtree (30 with children 20, 40), right subtree (70 with children 60, 80). Postorder (Left, Right, Root): 20, 40, 30, 60, 80, 70, 50.

Explanation: A non-terminal A is nullable if it can derive the empty string ε (A ⇒* ε). Identifying nullable non-terminals is important for converting a CFG to Chomsky Normal Form and for computing FIRST sets in parsing.

Explanation: In TCP slow start, the congestion window (cwnd) increases by 1 MSS for each ACK received. Since each RTT approximately doubles the number of outstanding segments acknowledged, cwnd effectively doubles each RTT — hence exponential growth despite the name 'slow start'.

Explanation: The token bucket algorithm allows traffic bursts up to the bucket capacity (the maximum number of tokens that can be stored). Tokens are added at a constant rate; each packet consumes tokens. When the bucket is full, accumulated tokens allow a burst of traffic.

Explanation: By processing elements in pairs and comparing with current min/max, we need 3 comparisons per pair (1 to compare the pair + 1 for min + 1 for max). For n elements, this gives ⌈3n/2⌉ − 2 comparisons, which is optimal. The naive approach needs 2(n−1) = 2n−2.

Explanation: /20 means the first 20 bits are the network portion. The host portion is 12 bits. 172.16.32.0 in binary: 10101100.00010000.0010|0000.00000000. Setting all host bits to 1: 10101100.00010000.0010|1111.11111111 = 172.16.47.255.

Explanation: HAVING filters groups created by GROUP BY, typically based on aggregate function results (e.g., HAVING COUNT(*) > 5). WHERE filters individual rows before grouping. HAVING is evaluated after GROUP BY, while WHERE is evaluated before it.

Explanation: A sorting algorithm is stable if it preserves the relative order of equal elements. Merge sort and insertion sort are stable. Quicksort, heapsort, and selection sort are not stable in their standard implementations.