📘 UNIT I – Problem Solving by Search

Introduction to AI | Intelligent Agents | Uninformed & Informed Search | Hill Climbing |

Simulated Annealing

⭐ ONE-MARK QUESTIONS (20 Questions)

Q1. What does the term 'Artificial Intelligence' stand for, and who coined it?
Q2. Define the term 'Agent' in the context of AI.
Q3. What is a percept in AI terminology?
Q4. What is a percept sequence?
Q5. Define the agent function.
Q6. What is an agent program?
Q7. Name the four categories of intelligent systems proposed by Luger and Stubberfield.
Q8. What is the Turing Test? Who proposed it?
Q9. Differentiate between strong AI and weak AI.
Q10. What is state space representation in problem solving?
Q11. Define initial state and goal state in a state space problem.
Q12. What is an operator in problem solving?
Q13. State the four properties used to evaluate a search algorithm.
Q14. What is the time complexity of Breadth-First Search (BFS)?
Q15. What is the space complexity of Depth-First Search (DFS)?
Q16. Define Iterative Deepening Depth-First Search (IDDFS).
Q17. What is a heuristic function?
Q18. State the evaluation function used in Greedy Best-First Search.
Q19. What does f = g + h represent in A* algorithm?
Q20. Define a local maximum in the context of Hill Climbing.
Q21. What is simulated annealing? What real-world inspiration is it based on?
Q22. What is the admissibility condition for a heuristic in A*?
Q23. Name two disadvantages of BFS.
Q24. What does PEAS stand for in agent design?
Q25. What is a vacuum cleaner agent?

📝 FIVE-MARK QUESTIONS (10 Questions)

Q1. Explain the four types of intelligent systems with examples (Think humanly, Think rationally, Act
humanly, Act rationally).
Q2. Describe the Water Jug Problem with state representation and a sequence of operators to solve
it.
Q3. Explain Breadth-First Search with an algorithm and its completeness, optimality, time and space
complexities.
Q4. Explain Depth-First Search with its algorithm, advantages, disadvantages, and complexities.
Q5. Compare BFS and DFS with respect to completeness, optimality, time complexity, and space
complexity.
Q6. Explain Iterative Deepening DFS (IDDFS). Why is it considered a preferred uninformed search
strategy?
Q7. Describe the 8-Puzzle problem. How is it formulated as a state space search problem?
Q8. Explain Greedy Best-First Search with the Romania path example. Is it complete and optimal?
Q9. Explain the Hill Climbing algorithm. What are the problems associated with it?
Q10. What is Simulated Annealing? How does it overcome local maxima in Hill Climbing?

🏆 TEN-MARK QUESTIONS (10 Questions)

Q1. What is Artificial Intelligence? Discuss its history, foundations, and sub-areas in detail. What are
the differences between strong AI and weak AI?
Q2. Explain the concept of Intelligent Agents. Describe the PEAS framework. Discuss the four types
of intelligent systems (Think/Act humanly/rationally) with suitable examples.
Q3. Define state space representation. Explain how the 8-Puzzle problem is formulated as a state
space search. Illustrate with a search tree showing BFS and DFS traversal.
Q4. Explain in detail the A* search algorithm. How does f = g + h work? Show a step-by-step example
of A* applied to the Romania map problem. Prove its admissibility.
Q5. Explain Iterative Deepening A* (IDA*). How does it improve upon A*? Compare its time and
space complexity with BFS, DFS, IDDFS, and A*.
Q6. Discuss Heuristic Search Strategies in detail. Explain Greedy Best-First Search, Hill Climbing, and
Simulated Annealing. Mention the limitations of each and how they are overcome.
Q7. Explain in detail BFS and DFS with full algorithms. Apply both to the Water Jug Problem.
Compare their efficiency and suitability for different scenarios.
Q8. Describe the General Problem Solver (GPS). Explain control strategies for problem solving.
Discuss the Water Jug problem solution step by step using BFS.
Q9. What are the properties of search algorithms? Describe uninformed search methods (BFS, DFS,
IDDFS, Bidirectional Search) with their properties and complexities.
Q10. Explain Local Search in Continuous Spaces. Discuss Hill Climbing, Simulated Annealing, and
the concept of gradient-based methods. How do these algorithms handle plateaus and ridges?
📘 UNIT II – Adversarial Search, CSP & Propositional Logic
Alpha-Beta Pruning | Minimax | Constraint Satisfaction | Forward/Backward Chaining

⭐ ONE-MARK QUESTIONS (20 Questions)

Q1. What is adversarial search?
Q2. Define the Minimax algorithm.
Q3. Who are Max and Min in a two-player game?
Q4. What is a terminal state in a game tree?
Q5. Define the utility function in game playing.
Q6. What is Alpha-Beta Pruning?
Q7. Define alpha cutoff and beta cutoff in Alpha-Beta Pruning.
Q8. What is a Constraint Satisfaction Problem (CSP)?
Q9. Give an example of a CSP.
Q10. What is a constraint graph?
Q11. Define a consistent assignment in CSP.
Q12. What is backtracking search in CSP?
Q13. Define constraint propagation.
Q14. What is a Knowledge-Based Agent?
Q15. What is the Wumpus World?
Q16. Define propositional logic.
Q17. What is a model in propositional logic?
Q18. Define entailment in logic.
Q19. What is a Horn clause?
Q20. Define Modus Ponens.
Q21. What is Forward Chaining?
Q22. What is Backward Chaining?
Q23. How is FC different from BC?
Q24. What is proof by resolution?
Q25. What is the difference between completeness and soundness of an inference algorithm?

📝 FIVE-MARK QUESTIONS (10 Questions)

Q1. Explain the Minimax algorithm with an example game tree. What are its properties
(completeness, optimality, time and space complexity)?
Q2. Explain Alpha-Beta Pruning with a suitable example. What are alpha and beta values?
Q3. Describe the Constraint Satisfaction Problem. Formulate the Map Coloring problem as a CSP.
Q4. Explain Forward Chaining with a step-by-step example using Horn clauses.
Q5. Explain Backward Chaining with a goal-driven example. How is it different from Forward
Chaining?
Q6. Describe the Wumpus World environment. State the rules and the percepts an agent receives.
Q7. Explain propositional logic: syntax, semantics, and the concept of satisfiability and validity.
Q8. What is proof by resolution? Explain with an example.
Q9. Compare Forward and Backward Chaining in terms of data-drivenness, goal-drivenness, and
efficiency.
Q10. Explain backtracking search for CSPs and how constraint propagation improves its efficiency.

🏆 TEN-MARK QUESTIONS (10 Questions)

Q1. Explain the Minimax algorithm in detail. Apply it to a game tree with at least 3 levels. Discuss its
time and space complexity and limitations.
Q2. Explain Alpha-Beta Pruning in detail with a complete worked example. How does it reduce the
nodes explored compared to Minimax? What is the best-case complexity?
Q3. Define and explain Constraint Satisfaction Problems (CSP) in detail. Explain constraint
propagation, arc consistency, and backtracking search with an example (Map Coloring or N-Queens).
Q4. Describe the Wumpus World. Show how a Knowledge-Based Agent reasons in the Wumpus
World using propositional logic. Illustrate with percept sequences and derived inferences.
Q5. What is propositional logic? Explain its syntax, semantics, and inference rules. Describe proof by
resolution, Horn clauses, and forward and backward chaining algorithms with examples.
Q6. Describe the Forward Chaining algorithm in detail. Apply it to the crime problem (American-West
example) showing each iteration of inference.
Q7. Describe the Backward Chaining algorithm in detail with the crime example. Compare it to
Forward Chaining in terms of efficiency and direction of reasoning.
Q8. Explain Propositional Theorem Proving in detail. Discuss Inference and proofs, resolution
method, Horn clauses, forward and backward chaining, and Davis-Putnam algorithm.
Q9. Explain adversarial game-tree search. Discuss Optimal Decisions in Games, Minimax decisions,
and how Alpha-Beta Pruning improves performance. Illustrate with full worked examples.
Q10. Define CSP and explain all methods for solving CSPs: backtracking search, arc consistency,
forward checking, constraint propagation, local search (min-conflicts heuristic). Use N-Queens as the
running example.
📘 UNIT III – Logic and Knowledge Representation
First-Order Logic | Unification | Forward & Backward Chaining (FOL) | Resolution

⭐ ONE-MARK QUESTIONS (20 Questions)

Q1. What is First-Order Logic (FOL)?
Q2. Define a constant symbol in FOL.
Q3. What is a predicate symbol?
Q4. Define a function symbol in FOL.
Q5. What is a term in FOL?
Q6. Define an atomic sentence in FOL.
Q7. What is universal quantification (∀)?
Q8. What is existential quantification (∃)?
Q9. State De Morgan's rules for quantifiers.
Q10. What is the equality symbol in FOL?
Q11. Define unification.
Q12. What is a Most General Unifier (MGU)?
Q13. What is Skolemization?
Q14. Define a Skolem constant.
Q15. What is Conjunctive Normal Form (CNF)?
Q16. State the resolution inference rule for FOL.
Q17. What is a definite clause?
Q18. What is Generalized Modus Ponens?
Q19. Define the kinship domain in FOL.
Q20. What are axioms in FOL?
Q21. What are theorems in FOL?
Q22. Define the subsumption lattice.
Q23. What is predicate indexing?
Q24. What is the difference between propositional logic and FOL?
Q25. What is Ontological Engineering?

📝 FIVE-MARK QUESTIONS (10 Questions)

Q1. Explain the syntax and semantics of First-Order Logic. Define constant symbols, predicate
symbols, function symbols, terms, and atomic sentences with examples.
Q2. Explain universal and existential quantification in FOL with examples. Show the connections
between ∀ and ∃ using De Morgan's rules.
Q3. Explain the Unification algorithm with examples. What is the Most General Unifier (MGU)? What
is the Occur Check?
Q4. Explain Generalized Modus Ponens with an example from the FOL forward chaining crime
problem.
Q5. Describe Forward Chaining in First-Order Logic using the Crime Example (Colonel West). Show
each step of inference.
Q6. Describe Backward Chaining in First-Order Logic with the proof tree for Criminal(West).
Q7. Explain the steps for converting a first-order sentence into Conjunctive Normal Form (CNF).
Q8. Explain the Resolution Inference Rule in FOL. Show how KB ⊨ α is proved by deriving the empty
clause.
Q9. Describe the Wumpus World in FOL. Write axioms for adjacency, Breezy squares, and pits using
first-order logic.
Q10. Explain the kinship domain representation in FOL. Write axioms for mother, father, sibling,
grandparent, and husband relationships.

🏆 TEN-MARK QUESTIONS (10 Questions)

Q1. Explain the Syntax and Semantics of First-Order Logic in detail. Include constant, predicate and
function symbols, terms, atomic sentences, complex sentences, quantifiers, equality, and
interpretation.
Q2. Explain the Knowledge Engineering process in First-Order Logic. Apply it to the Wumpus World
and the Kinship Domain. Write at least 8 axioms for each domain.
Q3. Explain Inference in First-Order Logic. Discuss Propositional vs FOL Inference, Unification and
Lifting, Universal and Existential Instantiation, and Reduction to Propositional Inference.
Q4. Explain the FOL Forward Chaining algorithm in detail. Apply it to the Colonel West (Crime)
example. Show how pattern matching, incremental chaining, and irrelevant facts affect efficiency.
Q5. Explain the FOL Backward Chaining algorithm in detail. Apply it to Criminal(West). Show the full
proof tree. Compare with Forward Chaining in efficiency and use cases.
Q6. Explain Resolution in FOL. Convert the sentence 'Everyone who loves all animals is loved by
someone' into CNF. Show each conversion step. Apply Resolution to prove West is a Criminal.
Q7. What is Knowledge Representation? Explain Ontological Engineering. Discuss Categories and
Objects, Events, Mental Events, Reasoning Systems for Categories, and Reasoning with Default
Information.
Q8. Describe Prolog as a Logic Programming Language. Explain the execution model, depth-first
backward chaining, negation as failure, the occur check, AND-parallelism and OR-parallelism.
Q9. Explain the complete process of FOL Resolution Theorem Proving: CNF conversion, resolution
rule, resolution proof by contradiction, with a fully worked example for the Crime Problem.
Q10. Write and explain the full set of axioms for the Wumpus World in First-Order Logic. Show how
the agent uses these axioms and percept inputs to infer safe squares and the wumpus location.
📘 UNIT IV – Planning
Classical Planning | PDDL | Planning Graphs | Hierarchical Planning | Multi-Agent Planning

⭐ ONE-MARK QUESTIONS (20 Questions)

Q1. What is classical planning in AI?
Q2. Define PDDL (Planning Domain Definition Language).
Q3. What is a fluent in PDDL?
Q4. What is a closed-world assumption?
Q5. Define an action schema in PDDL.
Q6. What is a precondition of an action?
Q7. What is the effect of an action in PDDL?
Q8. Define forward state-space search in planning.
Q9. What is backward (regression) search in planning?
Q10. What is PlanSAT?
Q11. What is Bounded PlanSAT?
Q12. What is a planning graph?
Q13. Define mutex (mutually exclusive) relations in a planning graph.
Q14. What are inconsistent effects in planning graphs?
Q15. What is GRAPHPLAN?
Q16. What is hierarchical planning?
Q17. Define a Hierarchical Task Network (HTN).
Q18. What is multi-agent planning?
Q19. Define a social law in multi-agent systems.
Q20. What is the difference between multibody and multi-agent planning?
Q21. What is the air cargo transport problem?
Q22. What is serializable sub goals?
Q23. What is the role of SATPLAN in classical planning?
Q24. What are successor-state axioms?
Q25. Define the 'plan first, schedule later' approach in real-world planning.

📝 FIVE-MARK QUESTIONS (10 Questions)

Q1. Explain the PDDL representation with the Air Cargo Transport example. Define actions Load,
Unload, and Fly.
Q2. Describe forward state-space search in planning. What are its advantages and limitations?
Q3. Describe backward (regression) state-space search in planning. When is it used?
Q4. Explain planning graphs. How are levels S0, A0, S1 etc. constructed? What is the mutex relation?
Q5. Explain the GRAPHPLAN algorithm. What is its termination condition?
Q6. Describe Hierarchical Planning (HTN). Why is hierarchy useful for planning in complex domains?
Q7. Explain Multi-Agent Planning with the doubles tennis example. What is the coordination
problem?
Q8. Describe SATPLAN. How is a PDDL planning problem translated to a SAT problem?
Q9. Explain PlanSAT and Bounded PlanSAT. What is the complexity class of classical planning?
Q10. Discuss the analysis of planning approaches. What are serializable sub goals and how do they
reduce complexity?

🏆 TEN-MARK QUESTIONS (10 Questions)

Q1. Define Classical Planning. Explain PDDL with its components: state representation, initial state,
action schemas (preconditions and effects), and goal. Use the Air Cargo Transport problem as a
running example.
Q2. Explain Forward State-Space Search and Backward State-Space Search for planning problems.
Discuss their challenges, heuristics, and how admissible heuristics are derived from relaxed
problems.
Q3. Explain Planning Graphs in detail. Define levels, action nodes, literal nodes, mutex links
(inconsistent effects, interference, competing needs, inconsistent support). Show how GRAPHPLAN
uses it.
Q4. Explain Hierarchical Planning (HTN Planning) in detail. How does HTN differ from classical
planning? How does it decompose abstract actions into primitive actions? Discuss with an example.
Q5. Describe Multi-Agent Planning in detail. Explain multi-effector planning, multibody planning, and
true multi-agent planning. Discuss cooperation, competition, coordination, and social laws.
Q6. Discuss SATPLAN as an approach to classical planning. Explain the translation steps
(propositionalizing actions, successor-state axioms, goal, initial state). What are its advantages and
disadvantages?
Q7. Explain Planning and Acting in Nondeterministic Domains. How are PDDL action schemas
extended? What role do percept schemas play? Discuss with the paint-matching example.
Q8. Explain Time, Schedules, and Resources in planning. Discuss the 'plan first, schedule later'
approach. What resource and temporal constraints must planners satisfy in real-world settings?
Q9. Analyze Classical Planning Approaches. Compare forward search, backward search, planning
graphs (GRAPHPLAN), SATPLAN, and partial-order planning in terms of efficiency, completeness,
and applicability.
Q10. Explain the complexity of Classical Planning. Define PlanSAT and Bounded PlanSAT. Show why
they are in PSPACE. How does function symbols affect decidability? Discuss decomposability and
serializable sub goals.
📘 UNIT V – Uncertain Knowledge and Learning
Probability | Bayes' Rule | Bayesian Networks | Learning | Decision Trees | ILP

⭐ ONE-MARK QUESTIONS (20 Questions)

Q1. Define probability in the context of AI.
Q2. What is prior probability?
Q3. What is posterior probability?
Q4. Define conditional probability.
Q5. State Bayes' theorem formula.
Q6. What is a Bayesian Network?
Q7. Define a Directed Acyclic Graph (DAG).
Q8. What is a Conditional Probability Table (CPT)?
Q9. What does P(A|B) represent?
Q10. Define independence of two random variables.
Q11. What is a full joint probability distribution?
Q12. State the three axioms of probability theory.
Q13. What is a random variable?
Q14. Define the sample space.
Q15. What is marginal probability?
Q16. What is Dempster-Shafer theory?
Q17. What is a belief function in Dempster-Shafer theory?
Q18. Define supervised learning.
Q19. What is unsupervised learning?
Q20. Define reinforcement learning.
Q21. What is a decision tree?
Q22. Define entropy in the context of decision trees.
Q23. What is information gain?
Q24. What is pruning in a decision tree?
Q25. Define Inductive Logic Programming (ILP).

📝 FIVE-MARK QUESTIONS (10 Questions)

Q1. Explain Bayes' theorem with the Meningitis-Stiff Neck example. Derive P(meningitis | stiff neck).
Q2. Describe Bayesian Networks. What are the two components of a Bayesian Network? Explain with
the Cavity/Toothache example.
Q3. Explain the full joint probability distribution. Show how conditional probabilities are computed
from a joint distribution table.
Q4. Describe the Naive Bayes Classifier. How is it derived from Bayes' rule? When is it used?
Q5. Explain Dempster-Shafer Theory with the murder mystery example. Define mass function, belief,
and plausibility.
Q6. Describe the forms of learning: supervised, unsupervised, reinforcement, and semi-supervised
learning.
Q7. Explain the Decision Tree Learning algorithm with an example. What is the IMPORTANCE
function based on entropy?
Q8. Describe Explanation-Based Learning (EBL). What are the four steps of the EBL process?
Q9. Explain Inductive Logic Programming (ILP). Why is it preferred over attribute-based learning?
Describe top-down inductive learning.
Q10. Explain the current-best-hypothesis algorithm for learning. Distinguish between generalization
and specialization.

🏆 TEN-MARK QUESTIONS (10 Questions)

Q1. Explain Probabilistic Reasoning in detail. Discuss acting under uncertainty, basic probability
notation, prior and posterior probability, conditional probability, independence, and Bayes' theorem
with examples.
Q2. Explain Bayesian Networks in detail. Describe the structure (DAG, CPT), how to construct a
Bayesian net, how to compute joint probabilities from the net, and how to do inference using the
home domain example.
Q3. Explain Approximate Inference in Bayesian Networks. Discuss Direct Sampling, Likelihood
Weighting, and Markov Chain Monte Carlo (MCMC) methods. When is approximate inference
preferred?
Q4. Describe Dempster-Shafer Theory in detail. Explain mass functions, belief, plausibility, the
combination rule, and characteristics. Compare with Bayesian probability theory. Give the murder
mystery example.
Q5. Explain Decision Tree Learning in detail. Discuss the DECISION-TREE-LEARNING algorithm,
entropy, information gain, the expressiveness of decision trees, pruning, and issues (missing data,
continuous attributes).
Q6. Discuss the Forms of Learning in AI. Explain supervised, unsupervised, reinforcement, and
semi-supervised learning. Discuss what components of an agent can be improved and what
representations are used.
Q7. Explain Knowledge in Learning. Discuss the logical formulation of learning,
current-best-hypothesis search, least-commitment search (version space), and the G-set and S-set
boundary representations.
Q8. Explain Explanation-Based Learning (EBL) in detail. Describe the EBL process with a concrete
example. Discuss how EBL trades off between reasoning cost and retrieval speed.
Q9. Explain Inductive Logic Programming (ILP) in detail. Describe top-down inductive learning
(clause specialization) and inverse resolution. Discuss inverse deduction and how it generates
hypotheses.
Q10. Explain the Bayesian approach to supervised learning. Discuss hypothesis spaces, Ockham's
razor, the realizability of a learning problem, regression vs. classification, conditional probability
distributions, and the Naive Bayes Classifier.