Below are a set of sample revision test questions—with accompanying explanations
(“rationales”)—that cover several core areas of artificial intelligence as discussed in Artificial
Intelligence: A Modern Approach (Second Edition). These questions aren’t copied from any
manual but are designed to help you review key concepts and techniques similar to those
explored in the exercise solutions manual. You can use these as self‐assessment tools or
study prompts.
Revision Test 1: Search Algorithms
Question 1:
Compare the key differences between Breadth-First Search (BFS), Depth-First Search (DFS), and A*
Search. Under what conditions is each algorithm most appropriate?
Rationale:
o BFS: Explores all nodes at one depth before moving deeper; guarantees optimality for
unweighted graphs but may require high memory.
o DFS: Explores as deep as possible along one branch before backtracking; uses less
memory but can get stuck in deep or infinite paths and does not guarantee optimality.
o A* Search: Uses a heuristic to guide exploration; if the heuristic is admissible (never
overestimates), A* finds an optimal solution more efficiently than uninformed search
methods.
This question tests your understanding of algorithm characteristics and their
appropriate contexts.
Question 2:
Explain how heuristic functions affect the performance of A* Search. What properties must a heuristic
have to ensure optimality?
Rationale:
o The heuristic function estimates the cost from a given node to the goal.
o Admissibility: The heuristic must never overestimate the actual minimum cost.
o Consistency (or Monotonicity): The estimated cost from the current node to the goal
should be no greater than the cost from the current node to a neighbor plus the
estimated cost from that neighbor to the goal.
This reinforces the importance of choosing good heuristics in search algorithms.
Revision Test 2: Constraint Satisfaction Problems (CSPs)
, Question 3:
Describe the backtracking search algorithm for solving CSPs. What improvements can be made to the
basic algorithm to reduce the search space?
Rationale:
o Basic Backtracking: Assign values to variables one at a time and backtrack when a
constraint is violated.
o Improvements:
Forward Checking: After assigning a variable, eliminate inconsistent values from
the domains of neighboring variables.
Arc Consistency (AC-3): Enforce constraints locally to reduce domains before or
during search.
Variable and Value Ordering Heuristics: Such as Minimum Remaining Values
(MRV) and Least Constraining Value (LCV) to decide which variable to assign
next and in what order.
This question examines both the algorithm’s foundation and optimization
techniques.
Question 4:
How can constraint propagation be used in solving CSPs, and why is it effective?
Rationale:
o Constraint propagation reduces the domains of variables by repeatedly applying
constraints until no further reduction is possible.
o It is effective because it can prune large portions of the search space early, reducing the
number of potential assignments that must be considered.
This question tests your understanding of how local consistency techniques improve
search efficiency.
Revision Test 3: Logical Inference and Knowledge Representation
Question 5:
Outline the process of converting a natural language statement into a logical expression suitable for
inference in a propositional logic system. What are common pitfalls during this translation?
Rationale:
o Process:
1. Identify the propositions (atomic statements).
2. Define logical connectives (AND, OR, NOT, IF-THEN) to structure the statement.
(“rationales”)—that cover several core areas of artificial intelligence as discussed in Artificial
Intelligence: A Modern Approach (Second Edition). These questions aren’t copied from any
manual but are designed to help you review key concepts and techniques similar to those
explored in the exercise solutions manual. You can use these as self‐assessment tools or
study prompts.
Revision Test 1: Search Algorithms
Question 1:
Compare the key differences between Breadth-First Search (BFS), Depth-First Search (DFS), and A*
Search. Under what conditions is each algorithm most appropriate?
Rationale:
o BFS: Explores all nodes at one depth before moving deeper; guarantees optimality for
unweighted graphs but may require high memory.
o DFS: Explores as deep as possible along one branch before backtracking; uses less
memory but can get stuck in deep or infinite paths and does not guarantee optimality.
o A* Search: Uses a heuristic to guide exploration; if the heuristic is admissible (never
overestimates), A* finds an optimal solution more efficiently than uninformed search
methods.
This question tests your understanding of algorithm characteristics and their
appropriate contexts.
Question 2:
Explain how heuristic functions affect the performance of A* Search. What properties must a heuristic
have to ensure optimality?
Rationale:
o The heuristic function estimates the cost from a given node to the goal.
o Admissibility: The heuristic must never overestimate the actual minimum cost.
o Consistency (or Monotonicity): The estimated cost from the current node to the goal
should be no greater than the cost from the current node to a neighbor plus the
estimated cost from that neighbor to the goal.
This reinforces the importance of choosing good heuristics in search algorithms.
Revision Test 2: Constraint Satisfaction Problems (CSPs)
, Question 3:
Describe the backtracking search algorithm for solving CSPs. What improvements can be made to the
basic algorithm to reduce the search space?
Rationale:
o Basic Backtracking: Assign values to variables one at a time and backtrack when a
constraint is violated.
o Improvements:
Forward Checking: After assigning a variable, eliminate inconsistent values from
the domains of neighboring variables.
Arc Consistency (AC-3): Enforce constraints locally to reduce domains before or
during search.
Variable and Value Ordering Heuristics: Such as Minimum Remaining Values
(MRV) and Least Constraining Value (LCV) to decide which variable to assign
next and in what order.
This question examines both the algorithm’s foundation and optimization
techniques.
Question 4:
How can constraint propagation be used in solving CSPs, and why is it effective?
Rationale:
o Constraint propagation reduces the domains of variables by repeatedly applying
constraints until no further reduction is possible.
o It is effective because it can prune large portions of the search space early, reducing the
number of potential assignments that must be considered.
This question tests your understanding of how local consistency techniques improve
search efficiency.
Revision Test 3: Logical Inference and Knowledge Representation
Question 5:
Outline the process of converting a natural language statement into a logical expression suitable for
inference in a propositional logic system. What are common pitfalls during this translation?
Rationale:
o Process:
1. Identify the propositions (atomic statements).
2. Define logical connectives (AND, OR, NOT, IF-THEN) to structure the statement.
