Back to Subject

Unit 2: Problem Solving & Search in AI; AI problem design - Practice Quiz

INT428 — Artificial Intelligence Essentials 60 Questions
0 Correct 0 Wrong 60 Left
0/60

1 In AI problem solving, what is a state space?

Problem formulation and state space search Easy
A. The time taken to reach the solution
B. The final goal state only
C. The memory used by the search algorithm
D. The set of all possible states reachable from the initial state

2 Which of the following is NOT typically a component when formulating a search problem?

Problem formulation and state space search Easy
A. The initial state
B. The goal test
C. The set of actions
D. The programming language used to code the solution

3 Which search strategy explores all nodes at the current depth before moving to the next depth level?

Introduction to uninformed search Easy
A. A* search
B. Depth-first search
C. Breadth-first search
D. Greedy best-first search

4 Why is a strategy like breadth-first search called uninformed (or blind)?

Introduction to uninformed search Easy
A. It only works on informed graphs
B. It always fails to find a solution
C. It uses no problem-specific knowledge beyond the problem definition
D. It requires a trained neural network to operate

5 Which uninformed search algorithm uses a stack (last-in, first-out) data structure for its frontier?

Introduction to uninformed search Easy
A. Best-first search
B. Uniform-cost search
C. Depth-first search
D. Breadth-first search

6 In greedy best-first search, which value is used to decide which node to expand next?

Core search algorithms: Best-first search Easy
A. The path cost from the start
B. The sum
C. The depth of the node in the tree
D. The heuristic estimate to the goal

7 Best-first search selects nodes for expansion based on which of the following?

Core search algorithms: Best-first search Easy
A. The number of children a node has
B. An evaluation function
C. The alphabetical order of node names
D. A random selection each step

8 What is the evaluation function used by A* search?

A* search Easy
A.
B. only
C.
D. only

9 In the A* evaluation function , what does represent?

A* search Easy
A. The estimated cost from to the goal
B. The cost of the path from the start node to node
C. The heuristic error at node
D. The total number of nodes expanded

10 A* search is guaranteed to find an optimal solution when the heuristic is:

A* search Easy
A. Randomly generated at each step
B. Always equal to zero
C. Larger than the true cost
D. Admissible (never overestimates the true cost)

11 In the context of search, what is a heuristic?

Heuristic search Easy
A. A guaranteed exact solution to the problem
B. A rule of thumb that estimates how close a state is to the goal
C. A method to randomly shuffle the search order
D. A data structure for storing the frontier

12 A common heuristic for grid-based pathfinding problems is the:

Heuristic search Easy
A. Alphabetical distance
B. Binary search distance
C. Manhattan distance
D. Random walk distance

13 A Constraint Satisfaction Problem (CSP) is defined by variables, domains, and:

Constraint satisfaction Easy
A. A single fixed goal state only
B. A neural network weight matrix
C. A reward signal for each action
D. Constraints that specify allowable combinations of values

14 Which of the following is a classic example of a Constraint Satisfaction Problem?

Constraint satisfaction Easy
A. Map coloring with adjacent regions having different colors
B. Multiplying two matrices together
C. Sorting a list of numbers in ascending order
D. Computing the average of a dataset

15 In gradient descent, the parameters are updated in which direction?

Basics of optimization: gradient-based methods and metaheuristics Easy
A. Perpendicular to the gradient
B. Along the positive gradient of the loss function
C. In a completely random direction
D. Opposite to the gradient of the loss function

16 Which of the following is an example of a metaheuristic optimization method?

Basics of optimization: gradient-based methods and metaheuristics Easy
A. Matrix transposition
B. Linear search
C. Genetic algorithm
D. Binary tree traversal

17 In algorithm analysis, time complexity measures how the running time grows with respect to:

Complexity Easy
A. The number of comments in code
B. The color of the interface
C. The programmer's experience
D. The size of the input

18 Which term describes whether a search algorithm is guaranteed to find a solution if one exists?

Solution metrics Easy
A. Complexity
B. Optimality
C. Completeness
D. Admissibility

19 In machine learning based AI, why are data requirements important?

Data requirements Easy
A. Data quality has no effect on model performance
B. Models generally need sufficient, good-quality data to learn effectively
C. More data always slows learning and should be avoided
D. Data is only needed after the model is deployed

20 In reinforcement learning, what does an agent receive after taking an action in the environment?

Introduction to reinforcement learning for sequential decision problems Easy
A. A compiled program
B. A fixed heuristic value
C. A reward signal and a new state
D. A labeled training dataset

21 In formulating the 8-puzzle as a search problem, which component defines how one configuration transforms into another?

Problem formulation and state space search Medium
A. The transition (successor) function
B. The goal test predicate
C. The initial state descriptor
D. The path cost accumulator

22 A robot navigates a grid of cells and can be in any cell. If it can also carry one of distinct objects (or none), what is the size of the state space?

Problem formulation and state space search Medium
A.
B.
C.
D.

23 For a search tree with branching factor and shallowest goal at depth , which uninformed strategy uses only memory while remaining complete and optimal for unit-cost steps?

Introduction to uninformed search Medium
A. Bidirectional search
B. Breadth-first search
C. Uniform-cost search
D. Iterative deepening depth-first search

24 Uniform-cost search expands the node with the lowest value of which quantity?

Introduction to uninformed search Medium
A. , the path cost from the start
B. , the estimated cost to the goal
C. The node's depth in the tree
D.

25 Greedy best-first search selects the next node to expand based on which evaluation function?

Core search algorithms: Best-first search Medium
A.
B.
C.
D.

26 Why can greedy best-first search fail to find the optimal path even with a reasonable heuristic?

Core search algorithms: Best-first search Medium
A. It expands nodes in random order
B. It ignores the cost already spent to reach a node
C. It always expands the deepest node first
D. It cannot handle weighted edges at all

27 A* search is guaranteed to return an optimal solution in tree search when the heuristic is:

A* search Medium
A. Consistent but occasionally overestimating
B. Admissible (never overestimates the true cost)
C. Larger than the true cost by a constant
D. Always equal to zero

28 Given and for node , and and for node , which node does A* expand next?

A* search Medium
A. Node , because is larger
B. Either, since both have
C. Node , because is larger
D. Node , because is smaller

29 If heuristic dominates (i.e., for all and both are admissible), what can be said about A* using ?

Heuristic search Medium
A. It expands no more nodes than A* using
B. It becomes inadmissible
C. It always expands more nodes than with
D. It ignores path cost entirely

30 For the 8-puzzle, why is the Manhattan-distance heuristic preferred over the misplaced-tiles heuristic?

Heuristic search Medium
A. It ignores tile positions entirely
B. It overestimates to speed up search
C. It is easier to compute per node
D. It gives higher yet still admissible estimates

31 In a CSP, what does the Minimum Remaining Values (MRV) heuristic recommend?

Constraint satisfaction Medium
A. Choose the variable with the fewest legal values left
B. Choose the variable with the most constraints
C. Assign values in alphabetical order
D. Assign the value that rules out fewest options

32 After assigning a value to a variable, forward checking primarily does what?

Constraint satisfaction Medium
A. Assigns values to all remaining variables at once
B. Reorders all future variables randomly
C. Backtracks immediately to the root node
D. Removes inconsistent values from neighboring variables' domains

33 Map coloring with 3 colors on a graph where two adjacent regions share an edge is best modeled with which constraint type?

Constraint satisfaction Medium
A. A binary inequality constraint between adjacent regions
B. A global all-different over all regions
C. No constraint is required
D. A unary constraint on each region

34 In gradient descent with learning rate , the update rule for parameter is:

Basics of optimization: gradient-based methods and metaheuristics Medium
A.
B.
C.
D.

35 Which feature distinguishes simulated annealing from basic hill climbing?

Basics of optimization: gradient-based methods and metaheuristics Medium
A. It guarantees the global optimum in one pass
B. It always follows the steepest ascent direction
C. It sometimes accepts worse solutions to escape local optima
D. It requires a differentiable objective function

36 Breadth-first search on a tree with branching factor and goal depth has what worst-case time complexity?

Complexity Medium
A.
B.
C.
D.

37 Depth-first search on a tree with branching factor and maximum depth has what space complexity?

Complexity Medium
A.
B.
C.
D.

38 Which four properties are standard for evaluating a search algorithm's performance?

Solution metrics Medium
A. Latency, throughput, jitter, bandwidth
B. Accuracy, precision, recall, F1-score
C. Completeness, optimality, time complexity, space complexity
D. Bias, variance, noise, error

39 Compared to classical search, why do learning-based AI methods typically demand large labeled datasets?

Data requirements Medium
A. They avoid any need for a heuristic or objective
B. They compute exact solutions with no approximation
C. They must generalize patterns from examples rather than a defined model
D. They require no evaluation once trained

40 In a Markov Decision Process, the discount factor close to 1 causes the agent to:

Introduction to reinforcement learning for sequential decision problems Medium
A. Ignore all future rewards
B. Weight long-term future rewards heavily
C. Consider only the immediate reward
D. Randomize its action selection

41 Consider A* search with a heuristic that is admissible but not consistent. Which statement is true regarding the necessity of re-expanding already-expanded nodes?

A* search Hard
A. Re-expansion is required only when the branching factor exceeds the depth of the solution
B. Nodes never need re-expansion since admissibility alone guarantees optimal -values on first expansion
C. Re-expansion depends solely on tie-breaking and is unrelated to consistency
D. Nodes may need to be re-expanded because a shorter path to an already-closed node can be found later

42 Two admissible heuristics and are available. If for all , we say dominates . What is the guaranteed consequence for A* using versus ?

Heuristic search Hard
A. A* with requires exponentially more memory than with
B. A with never expands more nodes than A with (ignoring tie-breaking)
C. A* with becomes inadmissible and may return suboptimal solutions
D. A* with always finds a strictly shorter path than with

43 For the 8-puzzle, the state space contains configurations, but only half are solvable from any given goal. What property explains this partition?

Problem formulation and state space search Hard
A. The parity of the permutation (number of inversions) is invariant under legal moves
B. The blank tile position uniquely determines reachability
C. Each move changes the number of inversions by an odd amount, cycling through all states
D. The Manhattan distance heuristic partitions states into reachable classes

44 Iterative Deepening DFS (IDDFS) re-generates nodes at shallower depths multiple times. For a tree with branching factor and solution depth , what is the asymptotic ratio of nodes generated by IDDFS to those generated by a single BFS?

Introduction to uninformed search Hard
A. It grows linearly with , making IDDFS impractical
B. It approaches regardless of
C. It approaches the constant factor for large
D. It is exactly times the BFS node count

45 Greedy best-first search uses . On an infinite state space with a misleading heuristic, which failure mode is most characteristic?

Best-first search Hard
A. It degenerates exactly to uniform-cost search behavior
B. It always returns the optimal solution but with high memory cost
C. It can get trapped following a locally attractive but non-terminating path, failing to find any solution
D. It guarantees completeness but sacrifices optimality only slightly

46 In a CSP, enforcing arc consistency (AC-3) removes values but does not always yield a solution. Which scenario shows AC-3 terminating with all domains non-empty yet the CSP being unsatisfiable?

Constraint satisfaction Hard
A. Any binary CSP whose constraint graph is a tree
B. A CSP with only unary constraints on each variable
C. A CSP where every variable has a singleton domain after propagation
D. A 3-cycle of variables each with domain under all-different constraints

47 For a CSP whose constraint graph is a tree with variables and domain size , what is the worst-case time complexity of solving it after applying directional arc consistency?

Constraint satisfaction Hard
A.
B.
C.
D.

48 Gradient descent on the function with a fixed learning rate converges slowly. What property of this function causes the difficulty?

Basics of optimization: gradient-based methods and metaheuristics Hard
A. The high condition number of the Hessian causes zig-zagging along the steep direction
B. The gradient is undefined at the optimum
C. The function lacks a global minimum, causing divergence
D. The function is non-convex with multiple local minima

49 In simulated annealing, the acceptance probability for a worse move of magnitude at temperature is . What is the practical effect of a cooling schedule that decreases too rapidly?

Basics of optimization: gradient-based methods and metaheuristics Hard
A. The acceptance probability exceeds 1, causing invalid transitions
B. The search provably converges to the global optimum faster
C. The search never accepts worse moves and behaves like random walk
D. The search freezes into a nearby local optimum before adequately exploring the space

50 Uniform-cost search on a graph with non-negative edge costs, minimum cost , and optimal solution cost has worst-case complexity of:

Complexity Hard
A.
B. where is solution depth
C.
D.

51 Suppose A* uses a weighted evaluation with and admissible . What bound holds for the solution cost returned?

A* search Hard
A. The solution cost is unbounded and can be arbitrarily bad
B. The solution cost is at most (bounded suboptimality)
C. The solution is always optimal because is admissible
D. The solution cost is at most

52 Given two admissible heuristics , defining yields a heuristic that is:

Heuristic search Hard
A. Always consistent regardless of the properties of and
B. Inadmissible unless everywhere
C. Admissible and dominates both, but may lose consistency unless both are consistent
D. Admissible only if and never disagree

53 In Q-learning, the update is . Why is Q-learning called an off-policy algorithm?

Introduction to reinforcement learning for sequential decision problems Hard
A. It learns the optimal policy's values using the greedy regardless of the behavior policy generating actions
B. It requires the transition model to be known in advance
C. It can only be applied offline to logged data, never online
D. It updates the policy directly without estimating value functions

54 In a discounted MDP with discount factor and rewards bounded by , what is the tightest upper bound on any state's value ?

Introduction to reinforcement learning for sequential decision problems Hard
A.
B.
C.
D.

55 The Minimum Remaining Values (MRV) heuristic and the Degree heuristic are used in CSP backtracking. What is the correct role of the Degree heuristic?

Constraint satisfaction Hard
A. It selects the variable involved in the largest number of constraints on remaining unassigned variables, used as a tie-breaker for MRV
B. It selects the variable with the largest domain to maximize flexibility
C. It selects the value that rules out the fewest choices for neighbors
D. It orders values by how frequently they appear in solutions

56 When comparing search algorithms, four standard metrics are completeness, optimality, time complexity, and space complexity. For depth-first search on a finite graph with cycle checking, which combination is correct?

Solution metrics Hard
A. Incomplete and non-optimal; time , space
B. Complete and optimal; time , space
C. Complete and optimal; time , space
D. Complete but not optimal; time , space

57 A reinforcement learning agent must learn in an environment with a large continuous state space. Why does tabular Q-learning become impractical, motivating function approximation?

Data requirements Hard
A. Continuous rewards cannot be stored in a table of finite precision
B. The number of state-action entries grows unmanageably and most states are never visited, preventing generalization
C. Tabular methods require the transition model, which continuous spaces lack
D. The discount factor must be exactly 1 for continuous spaces

58 Two engineers formulate the same routing problem differently: one uses cities as states, the other uses (city, fuel-level) pairs. What is the primary consequence of the richer state representation?

Problem formulation and state space search Hard
A. It enlarges the state space but can capture constraints the simpler formulation cannot represent
B. It makes the problem unsolvable due to state explosion
C. It always reduces the branching factor and speeds up search
D. It guarantees the heuristic becomes consistent automatically

59 Genetic algorithms rely on crossover and mutation. What is the specific risk if the mutation rate is set far too low while relying almost entirely on crossover?

Basics of optimization: gradient-based methods and metaheuristics Hard
A. Crossover creates only infeasible offspring, halting progress
B. Premature convergence: the population loses diversity and cannot explore beyond recombinations of existing genes
C. Fitness values become negative, invalidating selection
D. The algorithm behaves identically to exhaustive search

60 Bidirectional search reduces complexity by searching forward from the start and backward from the goal. For it to work correctly, which requirement is most critical?

Introduction to uninformed search Hard
A. The graph must be a tree with no cycles
B. The predecessors of the goal state must be efficiently computable to run the backward search
C. The branching factor must be identical in both directions
D. The heuristic must be admissible in both directions
Previous MCQ
Unit 1
Next MCQ
Unit 3