Unit 2 - Practice Quiz

The state space is a fundamental concept in AI, representing the complete set of configurations or states a problem can be in, connected by actions or transitions.

Uninformed (or blind) search algorithms explore the search space systematically without any extra information about the problem, such as how far a state is from the goal. They only know the problem definition.

A heuristic function provides an educated guess or an estimate of the cost to reach the goal from a given state . It guides informed search algorithms towards more promising states.

A* search uses an evaluation function , where is the actual cost from the start node to node , and is the estimated cost from node to the goal.

A CSP is defined by a set of variables, a domain of values for each variable, and a set of constraints. The solution is an assignment of values that violates no constraints.

Gradient Descent is an optimization algorithm that aims to find a local minimum of a function by repeatedly moving in the direction of the steepest descent, which is the negative of the gradient.

The core loop of reinforcement learning involves an agent taking an action in an environment, and the environment responding with a new state and a reward signal (positive or negative) that indicates the quality of the action.

Key metrics for search algorithms include completeness, optimality (does it find the best solution?), time complexity, and space complexity.

A well-defined problem has four essential components: an initial state, a set of possible actions, a transition model (or action function), and a goal test. The initial state is where the agent begins.

Depth-First Search (DFS) always expands the deepest node in the current frontier. It explores as far as possible along each branch before backtracking.

Greedy Best-First Search uses only a heuristic function to estimate the distance to the goal and always expands the node that appears to be closest, ignoring the cost already incurred to reach that node.

An admissible heuristic is an optimistic one; its estimated cost is always less than or equal to the actual cost of the cheapest path from node to the goal. Admissibility is a crucial property for A* to guarantee optimality.

The map coloring problem, where no two adjacent regions can have the same color, is a classic CSP. The variables are the regions, the domains are the available colors, and the constraints are that adjacent regions must have different colors.

Metaheuristics like Genetic Algorithms or Simulated Annealing are general-purpose optimization strategies that orchestrate a search process, often for problems where finding an exact, optimal solution is too difficult.

Space complexity refers to the maximum number of nodes stored in memory at any one time during the search. It's a critical measure of an algorithm's resource requirements.

To formulate a route-finding problem, the essential data is the state space, which is represented by a graph of locations and the connections between them, including costs like distance or travel time.

If , the evaluation function becomes . The search will then prioritize expanding the node with the lowest path cost from the start, which is the exact behavior of Uniform-Cost Search.

A policy is a strategy or mapping from states to actions. The agent learns a policy that tells it what action to take in any given state to maximize its total expected reward over the long run.

An optimal algorithm is one that, if a solution exists, will find the one with the highest quality according to the problem's cost function (e.g., the one with the lowest path cost).

The goal test is a critical part of problem formulation. It's a function that takes a state as input and returns true if it is a solution to the problem, and false otherwise, telling the search when to stop.

The abstract state space (the set of all reachable board configurations) remains the same regardless of how a state is represented in code. The conceptual actions (moving the blank tile) and the goal configuration are also unchanged. Changing the data structure from a 2D array to a string is a choice of implementation, not a change to the formal definition of the problem itself.

In a graph with infinite paths, Depth-First Search is not complete. It may follow a deep or infinite path and never backtrack to find a shallow solution on another branch. Breadth-First Search explores layer by layer, guaranteeing that it will find the shallowest solution first and is therefore complete.

If the heuristic is always 0, the A evaluation function becomes . The search will then prioritize expanding the node with the lowest path cost from the start, which is the exact definition of Uniform Cost Search. A is a generalization of UCS.

The A* evaluation function is . To calculate , we need and .

• The cost to reach M, , is the cost to reach its parent N plus the step cost from N to M: .
• The heuristic for M, , is given as 6.
• Therefore, .

The Minimum Remaining Values (MRV) heuristic advises choosing the variable with the fewest legal values remaining in its domain. This is a 'fail-first' strategy. By picking the most constrained variable, if there is a path that will lead to a failure (a dead end with no legal values), this heuristic makes it more likely to discover that failure sooner, allowing the algorithm to backtrack and prune that entire subtree from the search space.

Simulated Annealing is a metaheuristic optimization algorithm that can escape local minima. It does this by occasionally accepting moves to worse solutions, with the probability of acceptance decreasing over time (as the 'temperature' parameter cools). Gradient-based methods, by their nature, follow the slope downwards and will stop at the first minimum they find, whether it's local or global.

In imbalanced datasets, accuracy can be highly misleading. A simple model that always predicts the majority class (in this case, 'not spam') would achieve an accuracy of 99%. However, it would fail to identify any spam emails at all, making it completely ineffective for its intended purpose. Metrics like Precision, Recall, and F1-score are much more informative in such scenarios.

The Markov Property is the fundamental assumption of an MDP. It states that the effects of an action taken in a state depend only on that state and not on the prior history of actions and states. In other words, the current state contains all the information needed to decide the future, and the history of how the agent got to is irrelevant for future transitions.

Greedy Best-First Search expands the node that it estimates to be closest to the goal, based solely on the heuristic . It completely ignores the cost to reach that node, . This can lead it down a path that seems promising initially but turns out to be very long and costly overall. Therefore, it is optimal neither in terms of path cost nor completeness (it can get stuck in loops).

When a variable X is assigned a value, Forward Checking checks each unassigned variable Y connected to X and deletes values from Y's domain that are inconsistent. Arc Consistency is more powerful; it propagates constraints. After a value is removed from Y's domain, it will then check all neighbors of Y to see if their domains are now inconsistent, and so on, until no more values can be removed.

UCS finds the optimal (lowest cost) path by always expanding the node with the lowest path cost . This strategy works as long as path costs never decrease. This is guaranteed if all step costs are non-negative. The strict positivity () ensures the algorithm terminates by preventing infinite loops with zero-cost cycles. UCS does not use a heuristic.

Selection (like roulette wheel or tournament selection) ensures that fitter individuals are more likely to be chosen for reproduction, pushing the population's average fitness up (exploitation). Mutation introduces random changes into the individuals' genetic code, creating new, unexplored possibilities and preventing the algorithm from getting stuck in a local optimum by maintaining genetic diversity (exploration).

A highly complex model has a high capacity to learn, meaning it can fit very intricate patterns. When the dataset is small, the model has enough capacity to essentially 'memorize' the training examples, including their noise and random fluctuations. This leads to high performance on the data it has seen (training accuracy) but a failure to learn the underlying general pattern, resulting in poor performance on new data (poor generalization). This phenomenon is known as overfitting.

This strategy dedicates an initial period exclusively to exploration (taking random actions to learn about the environment) and then switches to a purely exploitative phase (always choosing the best-known action). While simple, it's a valid way to handle the trade-off. An Epsilon-Greedy policy would mix exploration and exploitation throughout the entire learning process, not separate them into distinct phases.

A more specific goal test prunes branches of the search tree earlier. For example, if the goal is 'get to city C', the search might be large. If the goal is 'get to city C with less than $100 in cost and in under 2 hours', many paths that would have been explored in the first problem will be immediately discarded because they violate the new constraints, effectively reducing the portion of the state space that needs to be searched.

Admissibility (never overestimating the cost) is the crucial property that guarantees A*'s optimality. If a heuristic overestimates the cost from a node N on an optimal path, its -value might become higher than the -value of a node on a suboptimal path. This could cause the algorithm to commit to the suboptimal path and find a goal state there first, returning a solution that is not the least-cost one.

In large-scale ML, datasets can contain millions or billions of examples. Calculating the true gradient requires summing over all of them, which is computationally prohibitive for each weight update. SGD (or mini-batch SGD) approximates the gradient using a single example or a small batch. While this estimate is noisy, it is far cheaper to compute, allowing for much faster and more frequent updates, which often leads to faster convergence in practice.

The Degree Heuristic advises choosing the variable that is involved in the largest number of constraints on other unassigned variables. In map coloring, this means picking the country that borders the most neighbors. Like MRV, this is a 'fail-first' strategy. By coloring the most constraining region first, it helps to quickly prune the search space and detect dead ends early.

A solution metric is a performance measure that defines what a 'good' solution looks like. It is how you score the output of your AI system. Examples include accuracy for classification, mean squared error for regression, path cost for a search problem, or cumulative reward in reinforcement learning. Choosing the right metric is critical as it dictates how the system is optimized and evaluated.

This is the core distinction. A model-based agent first learns a model of 'how the world works' (e.g., ). It can then use this model to 'plan' by simulating future outcomes. A model-free agent, like one using Q-learning, skips building an explicit model and learns directly what to do (a policy) or how good it is to be in a state/take an action (a value function) through trial and error.

Consistency (or the triangle inequality, ) is a stronger condition than admissibility. When a heuristic is consistent, A is guaranteed to find the optimal path to any node the first time it is expanded. If the heuristic is only admissible, it's possible for the algorithm to find a suboptimal path to a node first. Later, it might discover a new, cheaper path to , requiring it to be re-added to the frontier and potentially re-expanded. This is why some A implementations need to handle re-opening nodes from the closed set. Admissibility alone is sufficient to guarantee an optimal solution is found at the end, but consistency ensures efficiency by preventing re-expansions of optimal paths.

AC-3 enforces arc consistency for all pairs of variables in the entire CSP. This means for any arc , every value in the domain of has at least one supporting value in the domain of . Forward Checking, after assigning a value to a variable , checks all unassigned variables that share a constraint with and removes values from inconsistent with the assignment. Because AC-3 was run beforehand, the initial assignment to the first variable (say ) will not cause any immediate domain wipes for its neighbors. Any value in a neighbor's domain already has support, and the first assignment simply selects one of those supports. The real power of Forward Checking is seen after the second assignment and beyond, where new inconsistencies can arise that AC-3 (as a one-off pre-processor) didn't account for.

This question targets the core difference between on-policy (SARSA) and off-policy (Q-Learning) methods. Q-Learning is off-policy, meaning it updates its action-value function using a policy that is different from the one it uses to generate behavior. The behavior policy is -greedy, but the update policy is purely greedy. The Q-learning update rule is: . The term represents the estimated optimal future value from state , regardless of which action is actually taken next. SARSA, an on-policy algorithm, would have used in its update, thus using the value of the action that was actually taken.

Saddle points are regions where the gradient is close to zero, but they are not local minima. Standard Gradient Descent can get stuck or slow down dramatically in these regions. Gradient Descent with Momentum accumulates a velocity vector from past gradients. When it enters a saddle point region, even if the current gradient is small, the accumulated momentum helps it 'overshoot' the saddle point and continue descending on the other side. A small learning rate would make it even more likely to get stuck. Newton's method is attracted to points where the gradient is zero, which includes saddle points, and can get stuck there as well.

The state space consists of nodes representing the squares on the board. An edge exists between two nodes if a knight can move between them. Since a knight's move is reversible (if you can go from A to B, you can go from B to A), the graph is undirected. It is not a tree because there are multiple paths between squares (cycles exist). It is not a DAG for the same reason. While it is true that all squares are reachable (for ), this describes a property of the graph (connectivity), not its fundamental structure. The most precise description is an undirected graph where the degree of each node (number of possible moves) varies based on its position: a corner square has 2 moves, an edge square might have 3 or 4, and a central square has 8. This variance is a key feature of the graph structure.

This problem is a classic example of the Orienteering Problem. The goal is not necessarily to visit all points (like TSP) but to collect the maximum possible reward (by visiting a subset of valuable POIs) within a strict budget or constraint (the battery life, which translates to a maximum path cost/time). A TSP formulation is incorrect because it assumes all 100 points must be visited, which might be impossible. A simple greedy approach is unlikely to be optimal, as it might lead the drone far away for a high-reward POI, leaving no battery to return. VRP is irrelevant as there is only one 'vehicle' (drone).

Using an inadmissible heuristic of the form for turns the A algorithm into a variant known as Weighted A. This algorithm is no longer guaranteed to be optimal. However, it has a bounded sub-optimality. The cost of the solution found is guaranteed to be at most times the cost of the optimal solution. This provides a trade-off: you sacrifice guaranteed optimality for often much faster search speeds, as the search becomes more 'greedy' and directed towards the goal.

This is a worst-case scenario for both algorithms. A standard DFS would traverse the entire left subtree before moving to the right, expanding almost all nodes. IDS would do the same. Let's analyze the nodes generated by IDS. The last iteration (depth limit ) expands the entire tree. The second-to-last iteration (depth limit ) expands the entire tree up to that depth. The total nodes generated by IDS is , which is asymptotically dominated by the last two levels. In a binary tree, the number of nodes generated by IDS is approximately times the number generated by BFS, where . So IDS generates about twice the nodes of BFS. In this specific worst-case for DFS, it explores the entire tree, similar to BFS. Therefore, IDS will expand roughly twice the number of nodes as this worst-case DFS. A common misconception is that IDS is much less efficient, but in a tree with a reasonable branching factor, the cost is dominated by the last level, making it asymptotically similar to BFS in time but superior in space.

The MRV heuristic chooses the variable with the fewest remaining legal values. The Degree Heuristic chooses the variable involved in the largest number of constraints on other unassigned variables. At the start of the search, all domains are full, so MRV has no basis for making a choice (it sees a tie between all variables). In this situation, the Degree Heuristic is a powerful tie-breaker. By choosing a variable with a high degree, we are attempting to prune the search space more effectively early on. For example, assigning a value to a highly connected variable will constrain its many neighbors, hopefully detecting failures earlier. Once the search is underway, MRV often becomes more effective as domain sizes shrink.

An value very close to 1 means the temperature decreases very slowly (a slow annealing schedule). This allows the algorithm to spend a long time at higher temperatures, where it has a high probability of accepting worse moves, enabling it to explore the entire search space broadly and escape local optima. As the temperature eventually cools, it will transition to exploitation and settle into a good minimum. This slow cooling increases the probability of finding the global optimum but comes at the cost of a much longer runtime. A value of close to 0 would cause rapid cooling, making the algorithm behave like hill-climbing.

The Bellman Optimality Equation for the optimal value function is: This equation states that the value of being in state under the optimal policy is found by choosing the action that maximizes the expected return. The expected return for a given action is the sum over all possible next states of: the probability of transitioning to () times the sum of the immediate reward () and the discounted value of that next state under the optimal policy (). The other options are incorrect: one describes the Markov property, another is a purely greedy (and suboptimal) policy, and another omits the crucial discounting and expectation components.

The problem of sorting a permutation using adjacent swaps is equivalent to Bubble Sort. The number of swaps required to transform one permutation into another is related to the number of inversions between them. The maximum number of inversions in a permutation of items is when it is in reverse sorted order, which has inversions. Since each adjacent swap can reduce the number of inversions by at most one, this gives a lower bound. It is also an upper bound, as Bubble Sort can sort any permutation in this many swaps. Therefore, the longest shortest path (diameter) between the identity permutation and the reverse permutation is , which is in .

A with an admissible heuristic is guaranteed to find the optimal path, which has a cost of 50. GBFS is guided solely by the heuristic and ignores the path cost . For GBFS to find a suboptimal path of cost 100, it must have been 'lured' by promising heuristic values down a path that turned out to be expensive. This means it must have chosen to expand a node that was not on the true optimal path, otherwise it would have followed the optimal path. The other options are not necessarily true. GBFS could find the suboptimal path without exceeding 50 until the very end. The initial heuristic value is an estimate for the optimal path (50), so it's likely less than or equal to 50, not greater. A could potentially expand fewer nodes if the heuristic is very accurate and guides it directly to the goal while GBFS gets lost in a large, cheap-in-heuristic-value but expensive-in-reality section of the state space.

This is a classic case of a severe class imbalance problem. When the positive class (having a rare disease) is extremely rare, a naive classifier can achieve very high accuracy by simply always predicting the majority negative class. This 'accuracy paradox' makes accuracy a useless metric. The critical goal is to correctly identify the few positive cases. Precision (of the positive predictions, how many are correct?) and Recall (of all actual positive cases, how many did the model find?) are far more informative. The F1-Score, which is the harmonic mean of Precision and Recall, provides a single score that balances this trade-off, giving a much better assessment of the model's utility.

An effective state representation must be canonical and complete. An image from a single perspective is highly problematic because it's ambiguous (you can't see the other faces) and not canonical (multiple cube states can look identical from one angle, and the same state can produce different images depending on lighting and global orientation). This makes it nearly impossible to check for visited states (a critical part of A*) or to compute a consistent heuristic. The other options, while different, are all complete and canonical representations of the cube's permutation state, allowing for effective generation of successor states and heuristic calculation.

The defining characteristic of UCS (Dijkstra's Algorithm) is that it explores the state space in order of increasing path cost . This guarantees that the first time it reaches the goal node, it has found the path with the minimum possible cost. BFS explores in order of increasing depth (number of edges). In a graph with non-uniform costs, the shallowest path is often not the cheapest one. For example, a path A->B->Goal with costs (10, 10) is shallower than A->C->D->Goal with costs (1, 1, 1), but the latter is far cheaper. BFS would find the first path and stop, while UCS would find the second. UCS is an uninformed search (it has no heuristic), and it generally has worse or equal space complexity to BFS as its frontier can be large. Neither can handle negative edge costs without modification.

A heuristic dominates if for all states . An admissible heuristic never overestimates the true cost. \n1. (misplaced tiles) is admissible because each misplaced tile must be moved at least once. \n2. (Manhattan distance) is admissible because each tile must move at least its Manhattan distance, and moves do not interfere with each other in this calculation (i.e., moving one tile doesn't move another closer). \n3. is not admissible. A single move can fix a misplaced tile, so the cost is 1, but would estimate 2. \n4. . Since every tile that is a non-zero Manhattan distance from its goal is also a misplaced tile, is always greater than or equal to . Therefore, . \nComparing the admissible heuristics and , provides a more accurate (and always greater or equal) estimate. Therefore, is admissible and dominates .

The credit assignment problem is a core challenge in RL, especially for tasks with delayed rewards (e.g., winning a game of chess). When a reward is received, how do we know which of the many preceding actions were crucial for that success? Standard one-step TD methods (like Q-learning) propagate this reward information back only one step at a time, which can be very slow. Eligibility traces provide a mechanism to bridge this temporal gap. They maintain a short-term memory of recently visited state-action pairs, and when a TD error occurs (e.g., a reward is received), this error is used to update all of the preceding pairs in the trace, weighted by how long ago they occurred. This allows for more efficient propagation of credit (or blame) through time.

In complex, non-convex landscapes like those of neural networks, training involves two phases: exploration and exploitation. A high initial learning rate encourages exploration; the large, noisy steps (due to both the rate and the stochastic nature of the gradients) can help the optimizer jump out of sharp, suboptimal local minima or move past saddle points. As training progresses, the model is hopefully in a 'good' region of the loss landscape. At this point, the learning rate is decreased (annealed) to allow the optimizer to take smaller steps and carefully converge to the bottom of this wide, promising basin without overshooting it. A small fixed learning rate might get permanently stuck in the first poor local minimum it encounters.

This is a key property of A when used with a consistent heuristic. A always expands the node with the lowest -value on the frontier. Let be the node just expanded. Let be any successor of . The cost to get to through is . Because the heuristic is consistent, . Rearranging this, we get , which simplifies to . This means that the -value along any path is non-decreasing. Since A* always picks the node with the minimum -value to expand, the sequence of -values of the nodes it expands must also be non-decreasing. It's not strictly increasing because multiple nodes can have the same -value.