1.

Use unification to find the most general unifier (MGU) for the following pair of predicates:

f(g(X), Y) and f(Z, g(a))

2. Consider a game tree with a depth of 3 and branching factor 2.

Show how Alpha-Beta pruning reduces the number of nodes evaluated compared to plain Minimax.

3. In a graph-based problem, a robot can move in a 2D grid. Use Manhattan Distance to compute the
heuristic between start (1,1) and goal (4,5).

4. A* uses f(n) = g(n) + h(n) where:

g(n) = cost so far = 4

h(n) = heuristic estimate = 5

If another path to same node has g'(n) = 3 and h(n) same, which path is preferred?

5. Use truth table to verify whether the statement

(¬𝑃∨𝑄) ⊃ (𝑃⊃𝑄) (¬P∨Q) ⊃(P⊃Q)

is a tautology.

SECTION B – Long Answer / Descriptive Questions

1. Consider a CSP with 6 variables (A to F) with domain {0,1,...,9} and constraints:

Uniqueness: Variables A to F carry unique values.

R1: A + C = B, where A, B and C carry unique values.

R2: 2A + 2C = E, where A, C and E carry unique values.

R3: A + 2B = F, where A, B and F carry unique values.

R4: A + D = 2B, where A, B and D carry unique values.

Let the Generalized-Look-Ahead algorithm with Select-Value-Forward-Checking solve the CSP using
variable ordering A,C,B,E,F,D and value ordering 0,1,...,9

Show that the partial assignment {A=1,C=3} lead to a solution

2. Let S = { clear(A), on(A,C), onTable(C), holding(B) }, Calculate the resulting state S3 when the action
sequence [ Putdown(B), Pickup(B) ] is applied to the state S?.

Define AND-OR graph. Explain with example

Prove that following are tautologies?

(i). [P ∧ Q] ⊃ [P ∨ Q]

(ii) [(P ∨ Q) ⊃ R] ⊃ [(P ∧ Q) ⊃ R]

(iii) [(P ∨ Q) ⊃ R] ⊃ [P ⊃ R]

What are Genetic Algorithms and how do they work?

3. Explain the difference between Depth-First Search (DFS) and Breadth-First Search (BFS)

4. Define Constraint Satisfaction Problems (CSP) and mention some common techniques to solve
them..

5. What is Alpha-Beta Pruning in game trees and how does it improve Minimax?

6. What is a heuristic function and how is it used in heuristic search algorithms like A* and Hill
Climbing?

7. Describe the concept of a "state space" and how it is represented in search algorithms.

8. What is the difference between a greedy algorithm and a dynamic programming approach?

9. What is the difference between a global optimum and a local optimum in optimization problems?

10. How does the Minimax algorithm work in decision-making for game-playing AI?
11. Explain the concept of backtracking in Constraint Satisfaction Problems (CSP).

12. What is the role of the cost function in search algorithms like A*?

13. Explain the concept of the "search space" in the context of AI algorithms.

14. What are Genetic Algorithms and how are they applied to optimization problems?

15. Explain the concept of Weighted A* and its advantages over the traditional A* algorithm.

16. What is a Rete Network, and how does it improve the efficiency of a rule-based expert system?

applied to optimization problems?

15. Explain the concept of Weighted A* and its advantages over the traditional A* algorithm.

16. What is a Rete Network, and how does it improve the efficiency of a rule-based expert system?

17. What are uninformed search strategies? Compare Depth-First Search, Breadth-First Search, and
Uniform Cost Search with respect to completeness, time complexity, and optimality.

18. Explain the difference between forward chaining and backward chaining in rule-based systems.
In what scenarios is each one preferred?

19. Define admissible and consistent heuristics in the context of informed search algorithms. Why
are these properties important for the A algorithm?*

20. What are fuzzy logic systems? How do they differ from classical logic systems? Describe with an
example involving decision-making under uncertainty.

21. Describe the working of the AC-3 algorithm used for achieving arc consistency in CSPs. Provide a
step-by-step example to illustrate the process.

22. What is reinforcement learning? Explain key concepts such as reward, policy, value function, and
the exploration-exploitation trade-off.

23. Differentiate between model-based and model-free learning. How does Q-learning fit into this
classification?

24. Discuss the difference between deterministic and stochastic environments in AI. Give examples
of AI problems that fit into each category.

25. What is the role of utility theory in decision-making under uncertainty? How is it used to model
rational preferences?

26. Compare and contrast the concepts of satisfiability and entailment in propositional logic. How
are they checked in logic-based AI systems?

27. Explain the working of the A* search algorithm. Include a step-by-step example with a small
graph.
28. What is logical entailment in propositional logic? How is it used in AI for inference? Explain with
examples.

29. Discuss the components of an intelligent agent. Differentiate between simple reflex agents,
model-based agents, and goal-based agents.

30. What is the frame problem in knowledge representation? How do modern approaches attempt
to solve it?

31. Explain the structure and working of a rule-based expert system. Include the roles of inference
engine, working memory, and rule base.

32. Describe the concept of local search algorithms. How do Simulated Annealing and Hill Climbing
differ in handling local optima?

33. Write a detailed note on Bayesian Networks and how they help in probabilistic reasoning.

34. Explain the idea of arc consistency in CSP. Illustrate with an example how AC-3 algorithm
enforces arc consistency.

35. Describe the Minimax algorithm used in adversarial search. How does Alpha-Beta Pruning
optimize its performance? Provide an example tree to illustrate.

36. Explain Genetic Algorithms as a search and optimization technique. Discuss the role of selection,
crossover, and mutation with a simple example.

37. What is the difference between knowledge representation and knowledge reasoning in AI?
Describe with examples the use of semantic networks and frames.

38. Discuss the concept of First-Order Predicate Logic (FOPL). How does it differ from Propositional
Logic, and why is it more expressive for AI reasoning?

39. Explain the working of a forward chaining inference mechanism in rule-based systems. Use an
example to show how new facts are derived.

40. Describe Constraint Satisfaction Problems (CSP) and explain common solving strategies like
backtracking, forward checking, and constraint propagation.

41. What is the role of heuristics in informed search algorithms? Compare Greedy Best-First Search
and A with examples showing their performance.*

42. Explain Markov Decision Processes (MDPs) and the concept of utility in AI. How is the Bellman
equation used in solving MDPs? Provide a simple example.

SECTION C – Either / Or Type Questions

(1) Explain the concept of state space search with reference to AI problem-solving.

(2) What is a search strategy? Compare informed and uninformed search strategies.

(3) Describe the difference between Propositional Logic and First-Order Predicate Logic.

(4) Explain Horn clauses and how they are useful in logic programming (e.g., Prolog).

(5) What are the advantages and disadvantages of Greedy Best-First Search?

(6) Describe the differences between Minimax and Expectimax algorithms in game-playing agents.

(7) What is a planning problem in AI? Explain STRIPS representation.

(8) What is non-monotonic reasoning and how does it differ from classical logic?

(9) What is the importance of utility-based agents in decision-making?

(10) Define and explain Markov Decision Process (MDP) with an example.

(11) What are the key components of a search problem in AI? Describe how each component
influences the solution process.

(12) Explain the concept of heuristic evaluation functions in informed search strategies. How do they
affect the performance of algorithms like A*?

(13) Differentiate between depth-limited search and iterative deepening depth-first search (IDDFS).
Discuss scenarios where each is preferred.

(14) What is unification in First-Order Logic? Explain its significance in automated reasoning systems.

(15) Compare the use of forward chaining and backward chaining in inference systems. Provide an
example for each.

(16) What is a knowledge base in AI? How do logic-based and rule-based systems represent
knowledge?

(17) Explain the use of constraint propagation in solving CSPs. How does it reduce the search space?

(18) What is the difference between a deterministic and a non-deterministic environment in AI?

(19) Describe the characteristics and functioning of recurrent neural networks (RNNs). Where are
they typically applied in AI?

(20) What are belief networks (Bayesian Networks)? Explain how they model probabilistic
relationships between variables.

(21) What are partial-order planners in AI? How do they differ from total-order planners?

(22) Define the concept of frame-based knowledge representation. How does it differ from semantic
networks?
(23) Explain the concept of default reasoning in non-monotonic logic. Provide an example where it is
applicable.

(24) What are the limitations of classical logic in modeling real-world reasoning? How does fuzzy
logic attempt to overcome them?

(25) Describe the steps involved in solving an AI planning problem using Graphplan.

Q1: What is the Turing Test, and why is it significant in AI?

Q2: What is the Dartmouth Conference, and why is it considered the birth of AI as a
field?
Q3: Describe the difference between Depth-First Search (DFS) and Breadth-First
Search (BFS).
Q4: What is the Traveling Salesman Problem (TSP), and how does heuristic search help
solve it?
Q5: What are Genetic Algorithms, and how do they work?
Q6: What is the A algorithm, and why is it considered an informed search algorithm?*
Q7: What is IDA, and how does it differ from A?**
Q8: What is Alpha-Beta pruning, and how does it improve the Minimax algorithm?
Q9: What is Goal Stack Planning, and how does it help in automated planning?
Q10: What is the Means-Ends Analysis technique in AI problem-solving?
Q11: What is an Inference Engine in a Rule-Based Expert System?
Q12: What is the difference between forward chaining and backward chaining?
Q13: How does Arc Consistency help in solving CSPs?

-------------------------------------------------------------------------------------------

Problem 1: Depth First Search (DFS)

Given the following state space tree, use Depth First Search (DFS) to find the path from node
A to the goal node G. Assume that we explore the left-most branches first.

mathematica
Copy code
A
/ \
B C
/ \ / \
D E F G

Problem 2: Applying A Algorithm*

Given the following problem, apply the A* algorithm to find the shortest path from the start
node S to the goal node G. The heuristic values and costs are shown below.

Node Cost (g) Heuristic (h) Total Cost (f = g + h)

S 0 6 6
A 2 4 6
B 3 2 5
G 7 0 7
State transitions:

 S → A (cost = 2), S → B (cost = 3)

 A → G (cost = 5)
 B → G (cost = 4)

Problem 3: Solving an Optimization Problem Using Genetic Algorithm

Consider a population of 4 individuals, each representing a solution to the problem, encoded
as binary strings of length 6. The problem is to maximize the fitness function:

f(x)=sum of the binary digits in x.f(x) = \text{sum of the binary digits in }

x.f(x)=sum of the binary digits in x.

Initial population:

 Individual 1: 110010 (fitness = 3)

 Individual 2: 101101 (fitness = 4)
 Individual 3: 011101 (fitness = 4)
 Individual 4: 111000 (fitness = 3)

Use single-point crossover with a crossover rate of 0.8 and mutation rate of 0.1.

Problem 4: A Algorithm with Admissible Heuristics*

Consider the following graph with nodes S, A, B, and G, where the cost to move between
adjacent nodes is as follows:

 S → A (cost = 1)
 S → B (cost = 3)
 A → G (cost = 4)
 B → G (cost = 1)

The heuristic estimates (h) for each node are:

 h(S) = 4, h(A) = 2, h(B) = 1, h(G) = 0.

Apply the A* algorithm to find the shortest path from S to G.

Problem 5: Solving a Constraint Satisfaction Problem (CSP) Using Backtracking

Consider the following CSP where we have three variables X, Y, Z with domains:

 X: {1, 2, 3}
 Y: {1, 2, 3}
 Z: {1, 2, 3}
The constraints are:

1. X ≠ Y
2. Y ≠ Z
3. X ≠ Z

Use backtracking to find a solution.

Choose the correct alternative:

Q1. Which of the following is not a component of a knowledge-based agent?

A. Knowledge base

B. Inference engine

C. Heuristic function

D. Sensor

Q2. Select Option, In Mathematical Logic (Formal Logic), __________.

A. once a statement is true it will continue to be true

B. logical reasoning is mainly concerned with the interpretation of statements

C. All of above

Q3. In predicate logic, ∀x (P(x) → Q(x)) means:

A. For all x, if P(x) is true, then Q(x) is also true

B. There exists an x such that P(x) implies Q(x)

C. P(x) and Q(x) are both true for all x

D. None of the above

Q4. Select Option, A rational agent is one that:

A. Acts randomly

B. Always achieves the best outcome or best expected outcome

C. Has emotions

D. Always follows a fixed rule

Q5. Which of the following is true about Depth-First Search (DFS)?

A. DFS always finds the shortest path

B. DFS uses a queue

C. DFS uses a stack (explicit or recursion)

D. DFS is complete in all cases

Q6. Which of the following are tautologies?

A. [(P ⊃ R) ∨ (Q ⊃ R)] ⊃ [(P ∧ Q) ⊃ R]

B. [(P ⊃ R) ∧ (Q ⊃ R)] ⊃ [(P ∧ Q) ⊃ R]

C. All of the above

Q7. Select Option, A unifier is __________.

A. an operator that takes the union of two knowledge bases

B. a set of variable-value pairs that make two different formulas become identical

C. a rule of substitution that replaces two formulas with a single equivalent formula

D. None of above

Q8. In game playing, the minimax algorithm assumes that:

A. All players cooperate

B. Both players try to minimize the score

C. One player maximizes score while the other minimizes it

D. Random choices are made by the opponent

Q9. Which of the following is an example of heuristic information?

A. Distance from a node to goal estimated by straight-line

B. Exact cost from start to a node

C. Number of nodes in the graph

D. Time complexity of algorithm

Q10. Select Option, For points P(x₁,y₁) and Q(x₂,y₂), Manhattan Distance is __________.

A. the shortest distance from P to Q measured parallel to coordinate axis

B. the shortest distance from P to Q

C. either sea, rail or road distance from P to Q passing via Manhattan city

Q11. Which of the following are examples of first-order predicates?

A. P ∧ Q

B. Likes(John, IceCream)

C. (P ∨ Q) → R

D. ¬P

Q12. Select Option, In fuzzy logic, the truth value of a proposition is:

A. Either 0 or 1

B. Always 1

C. Any value between 0 and 1

D. Undefined

Q13. Select Option, The resolution method in propositional logic is:

A. A form of forward chaining

B. A type of inference rule using refutation

C. Based on Bayesian probability

D. A syntax-checking tool

Q14. Which AI paradigm is inspired by natural evolution?

A. Reinforcement Learning

B. Genetic Algorithms

C. Neural Networks

D. Rule-Based Systems

Q15. Select Option, The primary purpose of a heuristic function is to:

A. Evaluate the speed of a program

B. Determine the complexity of logic

C. Estimate the cost to reach the goal from a node

D. Minimize memory usage

Q16. Which of the following is a machine learning algorithm?

A. Depth-First Search

B. Minimax

C. Decision Tree

D. Resolution

Q17. Which of the following can be a clause in a CNF formula?

A. a ∨ b ∨ ¬c

B. a ∧ b ∧ ¬c

C. (a ∨ b) ∧ (¬b ∨ ¬c)

D. a ∨ b ∨ c

Q18. Which of the following AI agents first demonstrated that machines can beat the very best
humans at chess?

A. Blue Gene

B. Chess Machine

C. Deep Blue
D. Deep Thought

Q19. Select Option, Models developed using artificial neural networks are __________.

A. a representation of past experience

B. a representation of future outcome

C. made of biological neurons

Q20. Select Option, In AI, the percept is:

A. A machine’s memory

B. The agent’s output

C. What the agent perceives from the environment at a given instant

D. The program controlling the agent

Q21. In A* algorithm, f(n) = g(n) + h(n) where:

A. g(n) is heuristic cost, h(n) is actual cost

B. g(n) is total cost, h(n) is ignored

C. g(n) is cost from start to n, h(n) is estimated cost to goal

D. Both g(n) and h(n) are random estimates

Q22. Which of the following is not a type of environment in AI?

A. Fully Observable

B. Static

C. Natural

D. Deterministic

Q23. Select Option, A logic expression is valid if:

A. It is true in some interpretations

B. It is true in all interpretations

C. It is false in all interpretations

D. It is not expressible in logic

Q24. Select Option, Consider the TSP for five cities P,Q,R,S,T where the segments between cities are
bi-directional.

We are constructing a tour; we have selected PQ and PR. What is the next segment we can add to
the tour?

A. PS

B. PT

C. QT

D. QS

Q25. Select Option, In Propositional Logic, the expression ¬(P ∧ Q) is equivalent to:

A. ¬P ∨ ¬Q

B. ¬P ∧ ¬Q

C. P ∨ Q

D. P ∧ Q

Q26. Which of the following is a type of knowledge representation in AI?

A. Procedural knowledge

B. Semantic networks

C. Frames

D. All of the above

Q27. In knowledge representation, a semantic network is:

A. A decision tree

B. A set of condition-action rules

C. A graph of nodes and edges representing concepts and relationships

D. A neural network model

Q28. Which search algorithm uses a queue and explores nodes level by level?

A. Depth-First Search

B. Breadth-First Search

C. Hill Climbing

D. A* Search

---------------------------------------------------------