Artificial Intelligence (PEC-IT501B)

1. What is the main goal of AI?

To develop systems that can think, reason, learn, and act intelligently like humans.
2. Name any two AI techniques.
Search techniques and Knowledge representation.
3. What is a search problem?
A problem that requires finding a sequence of actions from an initial state to a goal state.
4. Give one example of a problem solved using AI search.
8-Puzzle problem.
5. What does problem formulation mean?
Defining a problem in terms of states, actions, initial state, and goal state.
6. Define problem space in AI.
The set of all possible states reachable from the initial state.
7. What is a problem-solving agent?
An agent that decides actions by searching for a sequence of steps to achieve a goal.
8. Define search strategy.
A method that determines which node to expand next during search.
9. What is a heuristic function (h(n))?
A function that estimates the cost from node n to the goal.
10. What is an admissible heuristic?
A heuristic that never overestimates the actual cost to reach the goal.
11. What does f(n) = g(n) + h(n) represent?
The evaluation function in A* search.
12. What is the utility of heuristic search?
It reduces search space and time by guiding the search intelligently.
13. Define Knowledge Base.
A collection of facts and rules stored for reasoning.
14. What is reasoning?
The process of deriving new knowledge from existing knowledge.
15. Mention any two types of knowledge.
Declarative knowledge and Procedural knowledge.
16. What is a schema in KR?
A structured framework for organizing knowledge.
17. What is an ontology?
A formal representation of concepts and relationships in a domain.
18. What is a proposition?
A statement that is either true or false.
19. What is inference?
The process of drawing conclusions from known facts.
20. Difference between knowledge and data?
Data is raw facts; knowledge is processed and meaningful information.
21. Define mapping in KR.
The correspondence between real-world entities and symbolic representation.
22. What is the frame problem?
The difficulty of specifying what does not change after an action.
23. What is non-monotonic reasoning?
Reasoning where conclusions can be withdrawn when new facts arise.
24. Give an example of knowledge representation.
Semantic Network.
25. What is a representation language?
A language used to encode knowledge for reasoning.
26. What is domain knowledge?
Knowledge specific to a particular application area.
27. What is default reasoning?
Reasoning based on assumptions in absence of complete information.
28. What is an instance in predicate logic?
A specific object of the domain.
29. Define a computable function.
A function that can be computed by an algorithm.
30. What is natural deduction?
A rule-based system for logical reasoning.
31. What is probabilistic reasoning?
Reasoning under uncertainty using probability theory.
32. Define conditional probability.
Probability of an event given that another event has occurred.
33. Define fuzzy set.
A set where elements have degrees of membership.
34. What is fuzzification?
Converting crisp values into fuzzy values.
35. What is defuzzification?
Converting fuzzy output into a crisp value.
36. What is uncertainty in AI?
Lack of complete or exact information.
37. Define belief in Dempster–Shafer theory.
A measure of confidence in a proposition.
38. What is a fuzzy rule?
An IF–THEN rule using fuzzy variables.
39. What is NLP?
A branch of AI that enables machines to understand human language.
40. Define syntax in NLP.
The grammatical structure of sentences.
41. What is discourse in NLP?
Analysis of relationships between sentences.
42. Define pragmatics.
Interpretation of language based on context and intention.
43. What is a corpus?
A large collection of text used for language analysis.
44. What is inductive learning?
Learning general rules from specific examples.
45. Define Explanation-Based Learning (EBL).
Learning by analyzing explanations of examples.
46. What is relevance information in learning?
Information that helps focus learning on important features.
47. Define a hypothesis in machine learning.
A proposed model or rule explaining data.
48. What is an expert system shell?
A tool providing inference mechanism without domain knowledge.
49. State one advantage of expert systems.
Provides consistent expert-level decisions.
50. What is a domain expert?
A person with specialized knowledge in a field.
51. Define mutation in genetic algorithms.
A random change in a chromosome to maintain diversity.
What do you mean by Contradiction and Contingency?
Contradiction:
• A contradiction is a logical statement that is false under all possible interpretations.
• It has no model in which the statement is true.
• Such a statement is logically inconsistent.
Contingency:
• A contingency is a logical statement that is true under some interpretations and
false under others.
• It is neither always true nor always false.
• Its truth value depends on the assignment of truth values to its variables.

Explain Semantic network with proper example.

Semantic Network:
• A Semantic Network is a graph-based knowledge representation technique used in
Artificial Intelligence.
• Knowledge is represented using nodes and links.
• Nodes represent objects, concepts, or instances.
• Links (arcs) represent relationships between the nodes.
• It is mainly used to represent hierarchical and associative knowledge.
Key Features:
• Represents knowledge in a structured and intuitive form
• Supports inheritance of properties
 • Easy to understand and modify
• Suitable for representing ISA (is-a) and HAS-A relationships
Common Relationships:
• ISA (is-a)
• HAS / HAS-A
• PART-OF
• INSTANCE-OF
Example:
• Consider the knowledge: “A canary is a bird. A bird can fly.”
o Node: Canary
o Node: Bird
o Node: Can fly
o Relationship:
▪ Canary ISA Bird
▪ Bird HAS Can fly
• By inheritance, Canary can also fly, even if it is not stated explicitly.
Advantages:
• Simple and visual representation
• Supports inference through inheritance
• Good for representing common-sense knowledge
Limitations:
• Not suitable for complex logical reasoning
• Ambiguity may arise in large networks

What is an agent? Describe various agent types.

Agent:
• An agent is an entity that perceives its environment through sensors and acts upon
that environment through actuators.
• The agent selects actions based on its percept sequence to achieve desired goals.
• An agent’s behavior is defined by an agent function that maps percepts to actions.
Types of Agents:
1. Simple Reflex Agent
o Acts only on the current percept.
o Uses condition–action rules.
o Does not consider past percepts.
o Suitable for fully observable environments.
2. Model-Based Reflex Agent
o Maintains an internal model of the world.
o Uses past percepts to handle partially observable environments.
o Updates internal state before choosing an action.
3. Goal-Based Agent
o Actions are chosen to achieve specific goals.
o Requires search and planning.
o More flexible than reflex agents.
4. Utility-Based Agent
o Uses a utility function to measure desirability of states.
o Chooses actions that maximize utility.
o Handles trade-offs between multiple goals.
5. Learning Agent
o Improves performance over time through experience.
o Consists of:
▪ Learning element
▪ Performance element
▪ Critic
▪ Problem generator
o Adapts to unknown environments.

Conclusion:
• Agent types differ based on knowledge, adaptability, and decision-making
capability.
• Advanced agents provide better performance in complex environments.

A problem-solving search can proceed either in the forward or the backward direction.
Justify.
Problem solving in Artificial Intelligence involves searching through a state space to find a
path from an initial state to a goal state. This search can be carried out in two directions:
1. Forward (Data-Driven) Search:
• The search starts from the initial state.
• Operators are applied to generate successor states.
• The process continues until a goal state is reached.
• Suitable when:
o Initial state is clearly defined.
o Possible actions from the current state are limited.
• Commonly used in uninformed search techniques like BFS and DFS.

2. Backward (Goal-Driven) Search:

• The search starts from the goal state.
• Operators are applied in reverse to reach the initial state.
• Subgoals are generated recursively.
• Suitable when:
o Goal state is well defined.
o Number of goal conditions is small.
• Often used in logical reasoning and theorem proving.

Conclusion:
• Forward search explores from known conditions toward the goal.
• Backward search reasons from the goal toward required conditions.
• The choice of direction depends on problem characteristics, branching factor, and
availability of goal information.
Distinguish between Declarative and Procedural Knowledge.
Declarative Knowledge vs Procedural Knowledge
Basis Declarative Knowledge Procedural Knowledge
Meaning Knowledge that describes facts and Knowledge that describes how
truths about the world to perform tasks
Focus What is known How it is done
Representation Facts, assertions, rules, predicates Algorithms, procedures,
methods
Expression Explicitly stated knowledge Implicit, embedded in actions
Modifiability Easy to update and modify Difficult to modify
Reasoning Supports logical inference and Supports execution and control
Support querying flow
Conclusion:
• Declarative knowledge emphasizes description of information.
• Procedural knowledge emphasizes execution of actions.
• Both are essential for effective problem solving in Artificial Intelligence.

What is a production system?

Production System:
• A production system is a rule-based problem-solving framework used in Artificial
Intelligence.
• Knowledge is represented in the form of production rules of the type IF condition
THEN action.
• It separates knowledge from control strategy.
Components of a Production System:
• Rule base: Set of production rules
• Working memory: Stores current facts and states
• Control strategy: Selects and applies appropriate rules
Key Characteristics:
• Modular and flexible
• Suitable for heuristic search and reasoning

What do you mean by consistency of a heuristic?

Consistency of a Heuristic:
 • A heuristic is said to be consistent (or monotonic) if it satisfies the triangle
inequality condition.
• For every node n and its successor n′, the heuristic value obeys:
h(n) ≤ c(n, n′) + h(n′)
where c(n, n′) is the cost of moving from n to n′.
Key Points:
• The estimated cost from the current node should not exceed the step cost plus the
heuristic of the successor.
• Consistency ensures that the estimated total cost f(n) = g(n) + h(n) never decreases
along a path.
Importance:
• Guarantees that A* search is optimal.
• Prevents re-expansion of nodes.
• A consistent heuristic is always admissible.

Compare Hill Climbing and Best First Search.

Hill Climbing vs Best First Search
Basis Hill Climbing Best First Search
Type of search Local search technique Informed (heuristic) search
technique
Search Moves only toward better Selects the best node globally from
direction neighboring states the frontier
Memory usage Very low (keeps only current state) High (stores all generated nodes in
OPEN list)
Heuristic use Uses heuristic to compare local
neighbors only
Uses heuristic to rank all frontier
nodes
Backtracking Not supported Supported
Optimality Not optimal Not guaranteed optimal (unless A*)
Completeness Not complete More complete than hill climbing
Problems Gets stuck in local maxima, plateaus, Can suffer from excessive memory
ridges usage
Conclusion:
• Hill climbing is fast and memory efficient but unreliable.
• Best first search is more systematic and flexible but memory intensive.

By using the predicate logic principles prove that "Marcus hated Caeser". Given below are
the list of statements.
Marcus was a man.
Marcus was Pompeian.
All Pompeians were Romans.
Caeser was a ruler.
All Romans were either loyal to Caesar or hated him.
Everyone is loyal to someone.
People only try to assassinate rulers they are not loyal to.
Marcus tried to assassinate Caeser.
Explain the answer thoroughly.
Given Statements (Knowledge Base):
1. Marcus was a man.
2. Marcus was a Pompeian.
3. All Pompeians were Romans.
4. Caesar was a ruler.
5. All Romans were either loyal to Caesar or hated him.
6. Everyone is loyal to someone.
7. People only try to assassinate rulers they are not loyal to.
8. Marcus tried to assassinate Caesar.
Step 1: Predicate Logic Representation
Let the predicates be defined as:
• Man(x): x is a man
 • Pompeian(x): x is a Pompeian
• Roman(x): x is a Roman
• Ruler(x): x is a ruler
• Loyal(x, y): x is loyal to y
• Hates(x, y): x hates y
• TriedToAssassinate(x, y): x tried to assassinate y
Now convert each statement into predicate logic:
1. Man(Marcus)
2. Pompeian(Marcus)
3. ∀x [Pompeian(x) → Roman(x)]
4. Ruler(Caesar)
5. ∀x [Roman(x) → (Loyal(x, Caesar) ∨ Hates(x, Caesar))]
6. ∀x ∃y Loyal(x, y)
7. ∀x ∀y [(TriedToAssassinate(x, y) ∧ Ruler(y)) → ¬Loyal(x, y)]
8. TriedToAssassinate(Marcus, Caesar)
Step 2: Logical Inference
Inference 1: Marcus is a Roman
From:
• Pompeian(Marcus)
• ∀x [Pompeian(x) → Roman(x)]
∴ Roman(Marcus)
Inference 2: Roman Rule Applied
From:
• Roman(Marcus)
• ∀x [Roman(x) → (Loyal(x, Caesar) ∨ Hates(x, Caesar))]
∴ Loyal(Marcus, Caesar) ∨ Hates(Marcus, Caesar)
Inference 3: Marcus is not loyal to Caesar
From:
• TriedToAssassinate(Marcus, Caesar)
• Ruler(Caesar)
• ∀x ∀y [(TriedToAssassinate(x, y) ∧ Ruler(y)) → ¬Loyal(x, y)]
∴ ¬Loyal(Marcus, Caesar)
Step 3: Resolution
We have:
• Loyal(Marcus, Caesar) ∨ Hates(Marcus, Caesar)
• ¬Loyal(Marcus, Caesar)
By disjunctive resolution, the only possible conclusion is:
∴ Hates(Marcus, Caesar)
Final Conclusion:
Using predicate logic and logical inference rules, it is proved that Marcus hated Caesar.
What is percept sequence?
Percept Sequence:
• A percept sequence is the complete history of percepts received by an agent from
the environment since the start of its operation.
• It represents everything the agent has observed so far and is used to decide future
actions.
What is agent system?
Agent System:
• An agent system consists of an intelligent agent along with its environment in which
it operates.
• It includes the agent’s sensors and actuators, enabling perception of the
environment and execution of actions.
Write down the advantages and disadvantages of Genetic Algorithm.
Advantages of Genetic Algorithm:
• Performs global search, reducing chances of getting trapped in local optima.
• Does not require derivative or gradient information.
 • Suitable for complex and large search spaces.
• Can handle multiple solutions simultaneously.
• Robust to noise and dynamic environments.
Disadvantages of Genetic Algorithm:
• Computationally expensive due to population-based search.
• Convergence to optimal solution is not guaranteed.
• Performance depends on proper parameter tuning (population size, mutation rate,
etc.).
• May converge slowly for simple problems.
• No clear stopping criterion in some cases.

Conclusion:
• Genetic Algorithms are powerful optimization tools but require careful design and
parameter control.
Discuss Combinatorial Explosion.
Combinatorial Explosion:
• Combinatorial explosion refers to the rapid and exponential growth of the number
of possible states or solutions in a problem as the problem size increases.
• It is a major challenge in AI problem solving and search techniques.
Cause:
• Large branching factor in the search tree.
• Increase in problem dimensions, variables, or constraints.
• Each additional choice multiplies the total number of combinations.
Effect on Search:
• Search space becomes extremely large.
• Requires excessive time and memory.
• Makes exhaustive search computationally infeasible.
Impact on AI Systems:
• Reduces efficiency of uninformed search methods.
• Affects optimality and completeness in practical time.
• Necessitates use of heuristics and informed search.
Control Measures:
• Use of heuristic search techniques (A*, Greedy search).
• Pruning methods like Alpha-Beta pruning.
• Applying problem decomposition and abstraction.
Conclusion:
• Combinatorial explosion limits brute-force problem solving.
• Intelligent search strategies are essential to manage it effectively.

Why does BFS give optimal solution?

Reason for Optimality of BFS:
• Breadth First Search expands nodes level by level, starting from the initial state.
• It always explores all nodes at a given depth before moving to the next depth.
• When all step costs are equal (unit cost), the first time BFS reaches the goal state, it
has found the shortest path.
• Hence, the solution found has the minimum number of steps, making it optimal.
Conclusion:
• BFS guarantees optimal solutions only when path costs are uniform.
• Under this condition, BFS is both complete and optimal.

What are the three major problems of hill-climbing technique?

Major Problems of Hill-Climbing:
1. Local Maximum
o The algorithm gets stuck at a state that is better than its neighbors but not
the global optimum.
o No uphill move is possible, so the search stops prematurely.
2. Plateau
o A flat region of the search space where all neighboring states have the same
heuristic value.
o The algorithm has no guidance on which direction to move and may loop or
terminate.
3. Ridge
 o A region where the optimal path requires a sequence of sideways or
downward moves.
o Hill climbing cannot follow the ridge properly due to its greedy nature.
Conclusion:
• These problems arise due to the local and greedy nature of hill-climbing search.

You are given two jugs, a 4-gallon one and a 3-gallon one. Neither have any measuring
markers on it. There is a pump that can be used to fill the jugs with water. How can you
get exactly 2 gallons of water into the 4-gallon jug? Give the state-space diagram, describe
the production rules and give a possible solution.
Problem Definition
• Two jugs: 4-gallon jug (J4) and 3-gallon jug (J3)
• Initial state: (0, 0)
• Goal state: (2, x), where x can be 0–3
• Allowed operations: Fill, Empty, Pour
• Objective: Get exactly 2 gallons in the 4-gallon jug

State Representation
• A state is represented as (x, y)
where:
o x = amount of water in 4-gallon jug
o y = amount of water in 3-gallon jug
• Constraints:
0 ≤ x ≤ 4, 0 ≤ y ≤ 3
Production Rules
Let the current state be (x, y):
1. Fill 4-gallon jug:
(x, y) → (4, y)
2. Fill 3-gallon jug:
(x, y) → (x, 3)
3. Empty 4-gallon jug:
(x, y) → (0, y)
4. Empty 3-gallon jug:
(x, y) → (x, 0)
5. Pour 3-gallon into 4-gallon jug:
o If x + y ≤ 4 → (x + y, 0)
o Else → (4, x + y − 4)
6. Pour 4-gallon into 3-gallon jug:
o If x + y ≤ 3 → (0, x + y)
o Else → (x + y − 3, 3)

State-Space Diagram (Description)

• Nodes represent states (x, y)
• Edges represent application of production rules
• Initial node: (0, 0)
• Goal node: (2, 0) or (2, y)
• Transitions occur through filling, emptying, or pouring operations

Possible Solution Path

Starting from initial state (0, 0):
1. Fill 3-gallon jug → (0, 3)
2. Pour 3-gallon into 4-gallon jug → (3, 0)
3. Fill 3-gallon jug → (3, 3)
4. Pour 3-gallon into 4-gallon jug → (4, 2)
5. Empty 4-gallon jug → (0, 2)
6. Pour 3-gallon into 4-gallon jug → (2, 0)
Goal Achievement
• The 4-gallon jug now contains exactly 2 gallons of water
• Goal state successfully reached using valid operators

Conclusion
• The water jug problem is a classic state-space search problem
• It demonstrates problem formulation, production rules, and systematic search
• The goal state is reachable without any measuring devices using logical operations
What is a tautology? Explain with an example.
Tautology:
• A tautology is a logical statement that is true under all possible interpretations of
its variables.
• Its truth value remains true regardless of the truth values of individual propositions.
• Tautologies are always valid and never false.
Example:
• The logical expression:
(P ∨ ¬P)
• This statement is true whether P is true or false.
• Hence, it is a tautology.
Conclusion:
• Tautologies represent universally true statements in propositional and predicate
logic.
Write the predicate logic representations for the following sentences :
(i) If it is bird, it can fly.
(ii) Every father is parent.
(iii) Every man has beaten the thief.
(iv) Every person in the party loves every child.
Predicate Logic Representations
Let the predicates be defined as required for each statement.
(i) If it is a bird, it can fly.
Let:
Bird(x): x is a bird
CanFly(x): x can fly
Predicate Logic:
∀x [Bird(x) → CanFly(x)]
(ii) Every father is a parent.
Let:
Father(x): x is a father
Parent(x): x is a parent
Predicate Logic:
∀x [Father(x) → Parent(x)]
(iii) Every man has beaten the thief.
Let:
Man(x): x is a man
Thief(y): y is a thief
Beaten(x, y): x has beaten y
Predicate Logic:
∀x ∀y [(Man(x) ∧ Thief(y)) → Beaten(x, y)]
(iv) Every person in the party loves every child.
Let:
Person(x): x is a person
InParty(x): x is in the party
Child(y): y is a child
Loves(x, y): x loves y
Predicate Logic:
∀x ∀y [(Person(x) ∧ InParty(x) ∧ Child(y)) → Loves(x, y)]
Conclusion:
The given English statements are correctly expressed using quantifiers, predicates, and
logical implication as required in predicate logic.
What is horn clause? Show that p→q is a horn clause.
Horn Clause:
• A Horn clause is a clause (disjunction of literals) that contains at most one positive
literal.
 • It may contain:
o Exactly one positive literal (definite clause)
o No positive literals (goal clause)
• Horn clauses are widely used in logic programming and AI inference due to efficient
reasoning.
General Form:
• (¬p₁ ∨ ¬p₂ ∨ … ∨ q)
This is logically equivalent to:
• (p₁ ∧ p₂ ∧ …) → q

Showing that 𝒑 → 𝒒is a Horn Clause

Step 1: Convert implication to clause form
Implication rule:
p → q ≡ ¬p ∨ q
Step 2: Analyze the clause
Clause: ¬p ∨ q
• Negative literal: ¬p
• Positive literal: q
• Number of positive literals = one

Conclusion:
• Since the clause ¬p ∨ q contains at most one positive literal,
• Therefore, p → q is a Horn clause.

Write a Prolog program to find out the Factorial of a number.

Prolog Program for Factorial
Definition:
• Factorial of a number n is defined as:
factorial(n) = n × factorial(n−1)
• Base case: factorial(0) = 1

Prolog Code:
factorial(0, 1).
factorial(N, F) :-
N > 0,
N1 is N - 1,
factorial(N1, F1),
F is N * F1.
Explanation:
• factorial(0, 1).
→ Base case: factorial of 0 is 1.
• factorial(N, F)
→ Recursive rule to compute factorial.
• N > 0 ensures valid recursion.
• N1 is N - 1 reduces the problem size.
• F is N * F1 computes the factorial.

Conclusion:
• The program uses recursion and arithmetic evaluation.
• It correctly computes the factorial of a given number using Prolog.

Write a program in PROLOG of LISP to find GCD of N number.

PROLOG Program to Find GCD of N Numbers
Logic Used:
• GCD of two numbers is computed using Euclid’s algorithm.
• GCD of N numbers is obtained by recursively computing GCD pairwise.

Prolog Code:
gcd(X, 0, X).
gcd(X, Y, G) :-
Y > 0,
 R is X mod Y,
gcd(Y, R, G).
gcd_list([X], X).
gcd_list([X, Y | T], G) :-
gcd(X, Y, G1),
gcd_list([G1 | T], G).
Explanation:
• gcd(X, 0, X)
→ Base case of Euclid’s algorithm.
• gcd(X, Y, G)
→ Recursively computes GCD of two numbers.
• gcd_list([X], X)
→ Base case for a single element list.
• gcd_list([X, Y | T], G)
→ Computes GCD of first two elements, then with remaining numbers.
Conclusion:
• The program correctly finds the GCD of N numbers.
• It uses recursion and modular arithmetic, suitable for AI logic programming.

Discuss about environments for agent.

Agent Environment
• The environment is the external world in which an intelligent agent operates.
• It provides percepts to the agent and receives actions from the agent.
• The nature of the environment strongly affects agent design and performance.

Types of Environments (Characteristics):

1. Fully Observable vs Partially Observable
o Fully observable: Agent can perceive the complete state of the environment.
o Partially observable: Agent has limited or noisy percepts.
2. Deterministic vs Stochastic
o Deterministic: Next state is completely determined by current state and
action.
o Stochastic: Actions may have uncertain outcomes.
3. Episodic vs Sequential
o Episodic: Each action is independent of previous actions.
o Sequential: Current actions affect future states.
4. Static vs Dynamic
o Static: Environment does not change while the agent is deliberating.
o Dynamic: Environment changes during agent’s decision process.
5. Discrete vs Continuous
o Discrete: Finite number of states, percepts, and actions.
o Continuous: Infinite or continuous state and action space.
6. Single-Agent vs Multi-Agent
o Single-agent: Only one agent operates in the environment.
o Multi-agent: Multiple agents interact, cooperatively or competitively.

Conclusion:
• Agent environments are classified based on observability, uncertainty, time, and
interaction.
• Understanding environment types is essential for selecting appropriate agent
architectures.
What is blind-search technique? Explain with examples.
Blind Search Technique:
• Blind search, also called uninformed search, is a search technique that does not use
any heuristic or additional domain knowledge.
• The search is carried out only using the problem definition, such as:
o Initial state
o Goal test
o Operators
• It explores the search space systematically without guidance.
Characteristics of Blind Search:
• No estimation of distance to goal
• Relies purely on state expansion
• Simple to implement
• May suffer from large search space and inefficiency

Examples of Blind Search Techniques:

1. Breadth First Search (BFS):
• Explores nodes level by level.
• Uses a queue (FIFO).
• Complete and optimal for unit step cost problems.
• Example: Finding the shortest path in an unweighted graph.
2. Depth First Search (DFS):
• Explores nodes depth-wise before backtracking.
• Uses a stack (LIFO).
• Memory efficient but not optimal.
• Example: Maze traversal.
3. Depth Limited Search (DLS):
• DFS with a fixed depth limit.
• Prevents infinite depth exploration.
• Example: Searching game trees up to a fixed depth.

Conclusion:
• Blind search techniques explore the problem space without guidance.
• They are suitable for small or simple problems.
• For complex problems, they are inefficient due to combinatorial explosion.

Prove that (((P→Q)→P)→P) is a tautology.

Proof using Logical Equivalences
Given expression:
((𝑃 → 𝑄) → 𝑃) → 𝑃
Step 1: Eliminate implication
Recall:
A → B ≡ ¬A ∨ B
So,
1. 𝑃 → 𝑄 ≡ ¬𝑃 ∨ 𝑄
Substitute:
((¬𝑃 ∨ 𝑄) → 𝑃) → 𝑃
Step 2: Eliminate implication again
(¬𝑃 ∨ 𝑄) → 𝑃 ≡ ¬(¬𝑃 ∨ 𝑄) ∨ 𝑃
So expression becomes:
[¬(¬𝑃 ∨ 𝑄) ∨ 𝑃] → 𝑃
Step 3: Apply De Morgan’s Law
¬(¬P ∨ Q) ≡ P ∧ ¬Q
So,
[(𝑃 ∧ ¬𝑄) ∨ 𝑃] → 𝑃
Step 4: Apply Absorption Law
(𝑃 ∧ ¬𝑄) ∨ 𝑃 ≡ 𝑃
Thus, expression reduces to:
𝑃→𝑃
Step 5: Final simplification
𝑃 → 𝑃 ≡ ¬𝑃 ∨ 𝑃 ≡ True
Conclusion
Since the given expression simplifies to a statement that is always true,
✔ ((𝑃 → 𝑄) → 𝑃) → 𝑃is a tautology.
What are Modus Ponens and Modus Tollens?
Modus Ponens
• Modus Ponens is a valid rule of inference in propositional and predicate logic.
• It derives a conclusion from a conditional statement and its antecedent.
Form:
If P → Q
and P is true
∴ Q is true
Modus Tollens
• Modus Tollens is a valid rule of inference used to infer the negation of the
antecedent.
• It reasons backward from the negation of the consequent.
Form:
If P → Q
and ¬Q is true
∴ ¬P is true
Conclusion
• Modus Ponens affirms the antecedent to derive the consequent.
• Modus Tollens denies the consequent to infer the negation of the antecedent.

What do you mean by Natural Language Processing (NLP)?

Natural Language Processing (NLP):
• Natural Language Processing is a branch of Artificial Intelligence concerned with
enabling computers to understand, interpret, and generate human language.
• It acts as an interface between human language and machine processing.
• NLP deals with both spoken and written language.
Key Objectives:
• To enable human–computer interaction using natural language
• To analyze syntax and semantics of language
• To derive meaningful information from text
Conclusion:
• NLP combines linguistics, computer science, and AI techniques to process natural
language effectively.
What is parsing in NLP?
Parsing in NLP:
• Parsing is the process of analyzing the grammatical structure of a sentence
according to the rules of a formal grammar.
• It determines how words in a sentence are related to each other syntactically.
• The output of parsing is a parse tree or syntax tree that represents sentence
structure.
Purpose of Parsing:
• To check syntactic correctness of sentences
• To identify phrase structure and dependencies
• To support semantic analysis in NLP
Conclusion:
• Parsing is a crucial step in NLP for understanding sentence structure and meaning.

What are the types of parsing?

Types of Parsing in NLP:
1. Top-Down Parsing
o Parsing starts from the start symbol of the grammar.
o It tries to generate the sentence by expanding grammar rules.
o Works from root to leaves of the parse tree.
o May suffer from backtracking.
2. Bottom-Up Parsing
o Parsing starts from the input words.
o Words are combined to form phrases until the start symbol is reached.
o Works from leaves to root of the parse tree.
o More efficient for many grammars.
Conclusion:
 • Top-down parsing is goal-directed, while bottom-up parsing is data-driven.
• Both are fundamental parsing strategies used in NLP.
Draw the parsed tree of the sentence "The white dog crossed the road".
Parsed (Syntax) Tree
Sentence: The white dog crossed the road
S
/ \
NP VP
/ \ / \
Det N' V NP
| /\ | / \
The Adj N crossed Det N
| | | |
white dog the road
Explanation (Brief):
• S (Sentence) consists of a Noun Phrase (NP) and a Verb Phrase (VP).
• NP (Subject): “The white dog”
o Det → The
o Adj → white
o N → dog
• VP: “crossed the road”
o V → crossed
o NP (Object):
▪ Det → the
▪ N → road

Conclusion:
• The parse tree shows the syntactic structure of the sentence.
• It represents correct phrase grouping and grammatical relationships as required in
NLP parsing.
Is BFS identical to uniform cost search? Justify your answer.
No, BFS is not identical to Uniform Cost Search, but they behave identically under specific
conditions.
Breadth First Search (BFS):
• Expands nodes in order of increasing depth.
• Uses a FIFO queue.
• Assumes equal (unit) step costs.
• Guarantees optimal solution only when all step costs are equal.

Uniform Cost Search (UCS):

• Expands nodes in order of increasing path cost (g(n)).
• Uses a priority queue.
• Works with variable step costs.
• Always finds the least-cost optimal solution, if costs are non-negative.

Justification:
• When all step costs are equal, path cost is proportional to depth.
• In such cases, UCS expands nodes in the same order as BFS.
• Therefore, BFS behaves like UCS only under unit-cost conditions.

Conclusion:
• BFS and UCS are not identical algorithms.
• They become equivalent only when all actions have equal cost.
• UCS is more general and powerful than BFS.

Show that if a heuristic is consistent then f(n) is monotonically non-decreasing along any
path.
Heuristic Consistency
• A heuristic ℎ(𝑛)is consistent (monotonic) if for every node 𝑛and its successor 𝑛′ :
ℎ(𝑛) ≤ 𝑐(𝑛, 𝑛′ ) + ℎ(𝑛′ )
where 𝑐(𝑛, 𝑛′ )is the step cost from 𝑛to 𝑛′ .
Definition of Evaluation Function
• In heuristic search (A*), the evaluation function is:
𝑓(𝑛) = 𝑔(𝑛) + ℎ(𝑛)
where:
• 𝑔(𝑛): cost from start node to node 𝑛
• ℎ(𝑛): estimated cost from 𝑛to goal
Proof of Monotonicity
Consider a node 𝑛and its successor 𝑛′ .
Step 1: Path cost relation
𝑔(𝑛′ ) = 𝑔(𝑛) + 𝑐(𝑛, 𝑛′ )

Step 2: Apply heuristic consistency

ℎ(𝑛) ≤ 𝑐(𝑛, 𝑛′ ) + ℎ(𝑛′ )
Rearranging:
ℎ(𝑛) − ℎ(𝑛′ ) ≤ 𝑐(𝑛, 𝑛′ )

Step 3: Compare 𝒇(𝒏)and 𝒇(𝒏′ )

𝑓(𝑛′ ) = 𝑔(𝑛′ ) +′ ℎ(𝑛′ ) ′
= 𝑔(𝑛) + 𝑐(𝑛, 𝑛 ) + ℎ(𝑛 )
Using consistency condition:
𝑔(𝑛) + ℎ(𝑛) ≤′ 𝑔(𝑛) + 𝑐(𝑛, 𝑛′ ) + ℎ(𝑛′ )
⇒ 𝑓(𝑛) ≤ 𝑓(𝑛 )

Result
• 𝑓(𝑛′ ) ≥ 𝑓(𝑛)for every successor 𝑛′ of 𝑛.
• Hence, 𝑓(𝑛)never decreases along any path.
Conclusion
• If a heuristic is consistent, the evaluation function 𝑓(𝑛)is monotonically non-
decreasing along any path.
• This property ensures:
o No node needs to be re-expanded
o A* search remains optimal and efficient

Describe the fuzzy set operations like : union, intersection and complement.
Fuzzy Set Operations
Let A and B be two fuzzy sets defined on universe X, with membership functions
µA(x) and µB(x), where 0 ≤ µ ≤ 1.
1. Fuzzy Union
• The union of two fuzzy sets represents the maximum degree of membership.
• An element belongs to the union if it belongs to either set to the highest extent.
Definition:
• µA∪B(x) = max[µA(x), µB(x)]
Interpretation:
• Captures the logical OR operation in fuzzy logic.

2. Fuzzy Intersection
• The intersection of two fuzzy sets represents the minimum degree of membership.
• An element belongs to the intersection if it belongs to both sets simultaneously.
Definition:
• µA∩B(x) = min[µA(x), µB(x)]
Interpretation:
• Captures the logical AND operation in fuzzy logic.

3. Fuzzy Complement
 • The complement of a fuzzy set represents the degree to which an element does not
belong to the set.
Definition:
• µA′(x) = 1 − µA(x)
Interpretation:
• Represents the fuzzy version of logical NOT.

Conclusion
• Fuzzy set operations generalize classical set operations.
• They allow partial membership, making them suitable for reasoning under
uncertainty.
• Union, intersection, and complement form the basis of fuzzy logic inference.

What is clause?
Clause:
• A clause is a disjunction (OR) of one or more literals.
• A literal is either a proposition or its negation.
• Clauses are usually written in disjunctive form and are widely used in propositional
and predicate logic, especially in resolution.
Example:
• (P ∨ ¬Q ∨ R) is a clause.
Conclusion:
• A clause represents a basic logical expression used for inference and reasoning in
Artificial Intelligence.
Describe Goal based agent system.
Goal-Based Agent System
Definition:
• A goal-based agent is an intelligent agent that selects actions based on explicit
goals.
• The agent evaluates possible future states and chooses actions that lead toward
achieving its goals.
Working Principle:
• The agent maintains:
o A description of the current state
o A set of goal states
• It uses search and planning techniques to determine the sequence of actions
required to reach the goal.
Characteristics:
• Decisions are future-oriented.
• More flexible than reflex-based agents.
• Can compare different possible action sequences.
• Requires goal information to guide behavior.

Advantages:
• Capable of handling complex problem-solving tasks.
• Suitable for dynamic environments where planning is required.
• Allows evaluation of alternative strategies.

Limitations:
• Computationally more expensive.
• Performance depends on search efficiency.

Conclusion:
• Goal-based agents act by reasoning about desired outcomes.
• They form the foundation for planning and problem-solving systems in Artificial
Intelligence.
What do you mean by a table driven agent? What is the problem of this agent?
Table-Driven Agent
Definition:
 • A table-driven agent is an agent that stores a table mapping every possible percept
sequence to a corresponding action.
• The agent selects an action by looking up the current percept sequence in the table.
• The table explicitly represents the agent function.
Working:
• Input: Complete percept sequence
• Processing: Table lookup
• Output: Corresponding action

Problems of Table-Driven Agent:

1. Combinatorial Explosion
o Number of percept sequences grows exponentially.
o Table size becomes impractically large.
2. High Memory Requirement
o Requires enormous memory to store all possible mappings.
3. Lack of Flexibility
o Cannot generalize from experience.
o Fails in previously unseen situations.
4. No Learning Capability
o Table must be predefined.
o Agent cannot improve or adapt over time.
5. Impractical for Real Environments
o Suitable only for very small and simple environments.

Conclusion:
• Table-driven agents are conceptually simple but impractical.
• They highlight the need for model-based, goal-based, and learning agents in AI
systems.

Is uniform cost search a special case of Best First Search? Justify your answer.
Yes, Uniform Cost Search (UCS) is a special case of Best First Search.
Justification
Best First Search (BFS – heuristic)
• Best First Search selects the node with the lowest evaluation function f(n) from the
OPEN list.
• The evaluation function is generally defined as:
f(n) = h(n)
where h(n) is a heuristic estimate.
Uniform Cost Search (UCS)
• Uniform Cost Search selects the node with the minimum path cost g(n).
• It does not use any heuristic information.
• The evaluation function for UCS is:
f(n) = g(n)
Relationship Between UCS and Best First Search
• Best First Search is a general framework where nodes are expanded based on an
evaluation function.
• When the evaluation function is chosen as f(n) = g(n),
Best First Search behaves exactly like Uniform Cost Search.
Conclusion
• Uniform Cost Search fits within the Best First Search framework.
• Hence, Uniform Cost Search is a special case of Best First Search where no heuristic
information is used.
Describe Local Beam Search.
Local Beam Search
Definition:
• Local Beam Search is a local search algorithm that maintains k states simultaneously
instead of a single state.
• It explores the search space by expanding the best k successors at each step.
Working Principle:
• Start with k randomly generated initial states.
• Generate all successors of these k states.
• From all successors, select the best k states according to the evaluation function.
• Repeat the process until a goal state is found or no improvement is possible.

Key Characteristics:
• Uses heuristic evaluation to select promising states.
• Shares information among parallel search paths.
• More robust than simple hill-climbing.

Advantages:
• Reduces chances of getting stuck in local maxima.
• Explores multiple regions of the search space simultaneously.
• Faster convergence compared to single-path local search.

Limitations:
• May still converge prematurely if states become similar.
• Performance depends on the value of k.
• No guarantee of optimal solution.

Conclusion:
• Local Beam Search improves local search by maintaining multiple candidate states.
• It is effective for large search spaces where systematic search is impractical.

Three missionaries and three cannibals are standing at the left bank of a river. There is a
boat having a capacity of taking two people and it can be driven by a missionary or a
cannibal. If the number of missionaries is less than the number of cannibals at any bank,
then cannibal will eat missionary. How is it possible for all the missionaries and cannibals
to cross the river so that no missionary is getting eaten? Describe the state space of the
problem. Describe production rules for solving the problem. Show one solution of the
problem.
Problem Definition
• Initial state: 3 missionaries (M) and 3 cannibals (C) on the left bank
• Goal state: All missionaries and cannibals on the right bank
• Boat capacity: Maximum 2 persons
• Constraint:
o On any bank, if M > 0 and M < C, missionaries are eaten (invalid state)
• Boat can be operated by either a missionary or a cannibal

State Space Representation

A state is represented as:
(ML, CL, B)
Where:
• ML = Number of missionaries on left bank (0–3)
• CL = Number of cannibals on left bank (0–3)
• B = Boat position
o B = L → Boat on left bank
o B = R → Boat on right bank
Initial State:
(3, 3, L)
Goal State:
(0, 0, R)
Valid State Condition:
• (ML = 0 or ML ≥ CL) and
• (MR = 0 or MR ≥ CR), where
MR = 3 − ML, CR = 3 − CL
Production Rules
The boat can carry the following combinations:
1. One missionary crosses
 o (ML, CL, L) → (ML−1, CL, R)
2. Two missionaries cross
o (ML, CL, L) → (ML−2, CL, R)
3. One cannibal crosses
o (ML, CL, L) → (ML, CL−1, R)
4. Two cannibals cross
o (ML, CL, L) → (ML, CL−2, R)
5. One missionary and one cannibal cross
o (ML, CL, L) → (ML−1, CL−1, R)
Reverse rules apply when the boat is on the right bank.
Only those moves are allowed that do not violate the safety condition on either bank.
State Space Description
• Nodes represent valid states (ML, CL, B)
• Edges represent legal boat crossings
• Invalid states (where missionaries are outnumbered) are excluded
• Search proceeds from initial state to goal state using valid transitions

One Possible Solution Path

Step State (ML, CL, B) Action
0 (3, 3, L) Initial state
1 (3, 1, R) Two cannibals cross
2 (3, 2, L) One cannibal returns
3 (3, 0, R) Two cannibals cross
4 (3, 1, L) One cannibal returns
5 (1, 1, R) Two missionaries cross
6 (2, 2, L) One missionary, one cannibal return
7 (0, 2, R) Two missionaries cross
8 (0, 3, L) One cannibal returns
9 (0, 1, R) Two cannibals cross
10 (0, 2, L) One cannibal returns
11 (0, 0, R) Two cannibals cross
Goal state reached safely.
Conclusion
• The Missionaries and Cannibals problem is a classic state-space search problem.
• Proper state representation and constraint checking ensure safety.
• Using valid production rules, a solution path exists where no missionary is eaten.
• This problem demonstrates systematic problem formulation and search in AI.

Prove that 𝑷 ∨ ¬𝑷is a tautology.

Proof
Method 1: Using Logical Law
• According to the Law of Excluded Middle, for any proposition 𝑃:
o Either 𝑃is true or its negation ¬𝑃is true.
• Hence, the expression 𝑃 ∨ ¬𝑃is always true.

Method 2: Using Truth Table

P ¬P P ∨ ¬P
TF T
F T T
• The result is true in all possible cases.

Conclusion
• Since 𝑃 ∨ ¬𝑃is true for every truth value of 𝑃,
• Therefore, 𝑃 ∨ ¬𝑃is a tautology.

Represent the following sentences using Predicate logic or using FOPL or find the wffs of
the following sentences and draw the conclusion as required :
(i) X is an Indian, (ii) Y is an Indian, (iii) X is a leader, (iv) Every Indian is a man, (v) Everyone
is loyal to someone, (vi) Every man is either loyal to a leader or hate a leader, (vii) Man
tries to assassinate a leader if he is not loyal to him, (viii) Y assassinated X.
Now conclude that Y hated X.
Step 1: Predicate Symbols
Let the predicates be defined as:
• Indian(x): x is an Indian
• Man(x): x is a man
• Leader(x): x is a leader
• Loyal(x, y): x is loyal to y
• Hates(x, y): x hates y
• Assassinated(x, y): x assassinated y
Constants:
• X, Y

Step 2: Predicate Logic Representation

1. Indian(X)
2. Indian(Y)
3. Leader(X)
4. ∀x [Indian(x) → Man(x)]
5. ∀x ∃y Loyal(x, y)
6. ∀x [Man(x) → (Loyal(x, X) ∨ Hates(x, X))]
7. ∀x ∀y [(Man(x) ∧ Leader(y) ∧ ¬Loyal(x, y)) → Assassinated(x, y)]
8. Assassinated(Y, X)
Step 3: Logical Inference
Inference 1: Y is a Man
From:
• Indian(Y)
• ∀x [Indian(x) → Man(x)]
∴ Man(Y)
Inference 2: Apply assassination rule
Given:
• Man(Y)
• Leader(X)
• Assassinated(Y, X)
From rule (vii):
A man assassinates a leader only if he is not loyal to him
∴ ¬Loyal(Y, X)
Inference 3: Apply man–leader rule
From:
• Man(Y)
• ∀x [Man(x) → (Loyal(x, X) ∨ Hates(x, X))]
∴ Loyal(Y, X) ∨ Hates(Y, X)
Inference 4: Resolution
We have:
• Loyal(Y, X) ∨ Hates(Y, X)
• ¬Loyal(Y, X)
By disjunctive resolution:
∴ Hates(Y, X)
Final Conclusion
✔ Using predicate logic representation and valid inference rules, it is proved that Y hated X.
Conclusion Drawn:
Y hated X.
Write Iterative Deepening Algorithm with example.
Iterative Deepening Search (IDS)
Definition:
 • Iterative Deepening Search is a search strategy that combines the advantages of
Breadth First Search and Depth First Search.
• It performs Depth-Limited Search repeatedly, increasing the depth limit by one at
each iteration until the goal is found.
Algorithm (Iterative Deepening Search)
Iterative-Deepening-Search(problem):
for depth = 0 to ∞ do
result ← Depth-Limited-Search(problem, depth)
if result ≠ cutoff then
return result
Depth-Limited-Search(node, limit):
if node is goal then return success
if limit = 0 then return cutoff
else
for each successor of node do
result ← Depth-Limited-Search(successor, limit − 1)
if result = success then return success
return failure
Working Principle:
• Starts with depth limit = 0.
• Performs DFS up to the current depth limit.
• Increases depth limit gradually until the goal node is reached.
• Nodes at shallow depths are expanded multiple times.

Example:
Consider a search tree:
A
/ \
B C
/\ \
D E F
• Goal node: E
Iterations:
• Depth 0 → A
• Depth 1 → A, B, C
• Depth 2 → A, B, D, E (Goal found)
Properties:
• Complete: Yes
• Optimal: Yes (for unit step cost)
• Space Complexity: O(bd)
• Time Complexity: O(b^d)

Conclusion:
• Iterative Deepening Search avoids excessive memory usage of BFS.
• It guarantees optimality like BFS while using space like DFS.
• Suitable for problems with unknown depth of solution.

What do you mean by Constraint Satisfaction Problem?

Constraint Satisfaction Problem (CSP)
Definition:
• A Constraint Satisfaction Problem is a problem in which a solution is defined as an
assignment of values to variables that satisfies all given constraints.
• CSPs are widely used in Artificial Intelligence for systematic problem solving.

Components of CSP:
1. Variables
o Finite set of problem variables.
2. Domains
o Each variable has a finite set of possible values.
3. Constraints
o Rules that restrict the values that variables can take, either individually or
jointly.
Goal:
• To find a complete and consistent assignment of values to all variables such that no
constraint is violated.
Conclusion:
• CSP provides a general framework for representing and solving combinatorial
problems in AI.
• Efficient solution requires search and constraint propagation techniques.

Write a Program in Prolog to compute the GCD of two numbers.

Prolog Program to Compute GCD
gcd(X, 0, X).
gcd(X, Y, G) :-
Y > 0,
R is X mod Y,
gcd(Y, R, G).
Explanation:
• gcd(X, 0, X)
→ Base case of Euclid’s algorithm.
• gcd(X, Y, G)
→ Recursively computes GCD using remainder.
• R is X mod Y
→ Computes remainder.
• gcd(Y, R, G)
→ Continues recursion until remainder becomes zero.
Conclusion:
• The program correctly implements Euclid’s algorithm.
• It efficiently computes the GCD of two numbers using Prolog.

What is Skolemisation?
Skolemisation
Definition:
• Skolemisation is a process used in predicate logic to eliminate existential quantifiers
by replacing them with Skolem constants or Skolem functions.
• It is mainly used during conversion of formulas into clause form for resolution-based
inference.
Key Idea:
• An existentially quantified variable is replaced by:
o A Skolem constant if it is not within the scope of any universal quantifier.
o A Skolem function if it depends on universally quantified variables.

Purpose:
• Simplifies logical expressions.
• Makes formulas suitable for automated theorem proving.
• Preserves satisfiability of the original formula.

Conclusion:
• Skolemisation removes existential quantifiers without changing the logical
consistency.
• It is an essential step in resolution and inference mechanisms in AI.

Explain the steps of Natural Language Processing.

Steps of Natural Language Processing (NLP)
Natural Language Processing involves a sequence of steps to convert human language into a
form that a computer can understand and process.
1. Lexical Analysis
• Deals with word-level processing.
• Involves tokenization, removal of punctuation, and identification of words.
• Converts a sentence into a sequence of tokens.
2. Syntactic Analysis (Parsing)
• Analyzes the grammatical structure of sentences.
• Determines relationships between words using grammar rules.
• Produces a parse tree or syntax tree.

3. Semantic Analysis
• Determines the meaning of the sentence.
• Resolves ambiguity and assigns meanings to words and phrases.
• Maps syntactic structures to semantic representations.

4. Discourse Integration
• Considers the context of previous sentences.
• Ensures consistency of meaning across multiple sentences.
• Handles references like pronouns and anaphora.

5. Pragmatic Analysis
• Interprets language based on real-world knowledge and context.
• Determines the speaker’s intended meaning.
• Goes beyond literal meaning of sentences.

Conclusion
• NLP is a multi-level process involving syntax, semantics, and context.
• Each step builds upon the previous one to achieve accurate language
understanding.
• These steps enable effective human–computer interaction.

Generate the parse tree for the sentence "The boy went to School".
Parse Tree (Syntax Tree)
Sentence: The boy went to school
S
/ \
NP VP
/ \ / \
Det N V PP
| | | / \
The boy went P NP
| |
to school
Explanation (Brief):
• S (Sentence) consists of a Noun Phrase (NP) and a Verb Phrase (VP).
• NP (Subject):
o Det → The
o N → boy
• VP:
o V → went
o PP (Prepositional Phrase):
▪ P → to
▪ NP → school

Conclusion:
• The parse tree correctly represents the syntactic structure of the sentence.
• It shows proper phrase grouping and grammatical relationships, as required in NLP
parsing.
Explain AO* algorithm with a suitable example.
AO* Algorithm
Definition:
• AO* is an informed heuristic search algorithm used for searching in AND–OR
graphs.
• It finds an optimal solution graph rather than a single solution path.
• It is an extension of the A* algorithm to problems involving decomposition into
subproblems.
AND–OR Graph Concept
• OR node: Any one of the successor nodes can solve the problem.
• AND node: All successor nodes must be solved together.
• A solution is a subgraph satisfying all AND requirements with minimum cost.

Evaluation Function
• Each node has a heuristic estimate h(n).
• AO* computes the cost of a node recursively:
o OR node cost = minimum cost of its children
o AND node cost = sum of costs of all required children

Working Steps of AO*

1. Start from the initial node.
2. Expand the most promising node based on heuristic cost.
3. Update costs by backtracking from leaf nodes to the root.
4. Mark the best partial solution graph.
5. Repeat expansion and cost revision until:
o A complete solution graph is found, or
o No better solution exists.

Key Properties
• Uses heuristic guidance.
• Performs backtracking cost revision.
• Guarantees optimal solution if heuristic is admissible.
• Suitable for problem decomposition tasks.

Example (Textual)
Consider a problem where goal G can be achieved by:
• OR choice:
o G → A (cost 3)
o G → B (cost 4)
• AND decomposition:
o A → (C AND D)
▪ C cost = 2
▪ D cost = 1
Cost Calculation:
• Cost(A) = 3 + (2 + 1) = 6
• Cost(B) = 4
AO* selects B as the optimal solution since it has lower total cost.
Advantages
• Efficient for AND–OR problems.
• Avoids exploring unnecessary paths.
• Finds optimal solution graphs.

Limitations
• Requires accurate heuristic estimates.
• More complex than A*.
• High memory usage for large graphs.

Conclusion
• AO* is a powerful heuristic search algorithm for AND–OR graphs.
• It systematically finds the least-cost solution graph.
• Widely used in planning, problem decomposition, and reasoning tasks.

Write short notes on the following :

a) Conceptual Graph.
b) Alpha-Beta pruning in min-max search.
c) A* search.
d) The steps for transforming into Clause Form.
e) Expert Systems.
(a) Conceptual Graph
• A Conceptual Graph is a graph-based knowledge representation technique.
• It consists of concept nodes (objects, entities) and relation nodes (relationships).
• It represents knowledge in a visual and semantic form.
 • Closely related to predicate logic and supports inference.
(b) Alpha–Beta Pruning in Min–Max Search
• Alpha–Beta pruning is an optimization technique for the Minimax algorithm.
• It eliminates branches that cannot influence the final decision.
• Alpha: best value for maximizer so far
• Beta: best value for minimizer so far
• Reduces search space without affecting optimality.

(c) A Search*
• A* is an informed heuristic search algorithm.
• Uses evaluation function:
f(n) = g(n) + h(n)
• g(n): cost from start to node n
• h(n): heuristic estimate to goal
• Complete and optimal if heuristic is admissible.

(d) Steps for Transforming into Clause Form

1. Eliminate implication and biconditional.
2. Move negation inward using De Morgan’s laws.
3. Standardize variables.
4. Remove existential quantifiers using Skolemisation.
5. Remove universal quantifiers.
6. Convert to Conjunctive Normal Form (CNF).
7. Separate conjunctions into clauses.
(e) Expert Systems
• An expert system is an AI system that emulates the decision-making ability of a
human expert.
• Uses domain knowledge and inference rules.
• Main components:
o Knowledge base
o Inference engine
o User interface
• Applied in diagnosis, planning, and decision support.

Explain the working principle of Simulated Annealing Algorithm.

Simulated Annealing Algorithm
Definition:
• Simulated Annealing is a probabilistic local search algorithm used for optimization
problems.
• It is inspired by the annealing process in metallurgy, where controlled cooling leads
to a low-energy stable state.
• The algorithm allows occasional downhill (worse) moves to escape local optima.

Working Principle:
1. Initial State and Temperature
o Start with an initial solution.
o Set a high initial temperature (T).
2. Neighbour Selection
o Generate a random neighbouring solution of the current state.
3. Evaluation
o Compute the change in cost (ΔE) between current and new state.
4. Acceptance Criterion
o If ΔE < 0 (better solution), accept the new state.
o If ΔE > 0 (worse solution), accept it with probability:
P = e^(−ΔE / T)
5. Temperature Reduction
o Gradually decrease the temperature according to a cooling schedule.
6. Termination
o Stop when temperature becomes very low or no significant improvement
occurs.
Key Characteristics:
• Initially explores widely due to high temperature.
• Gradually becomes greedy as temperature decreases.
 • Can escape local maxima and plateaus.
Advantages:
• Avoids getting trapped in local optima.
• Suitable for large and complex search spaces.

Conclusion:
• Simulated Annealing balances exploration and exploitation.
• Its probabilistic acceptance of worse moves makes it more powerful than hill
climbing.
• Widely used in optimization and local search problems.

Describe different components of AI.

Components of Artificial Intelligence
Artificial Intelligence systems are built using several core components that enable intelligent
behavior.
1. Knowledge Representation
• Concerned with how knowledge about the world is represented and stored.
• Uses techniques like:
o Predicate logic
o Semantic networks
o Frames
o Rules
• Enables reasoning and inference.

2. Reasoning and Inference

• Allows the AI system to derive new knowledge from existing facts.
• Includes:
o Logical reasoning
o Deductive and inductive inference
o Handling uncertainty (probabilistic and fuzzy reasoning)

3. Search and Problem Solving

• Used to find solutions by exploring state spaces.
• Includes:
o Uninformed search (BFS, DFS)
o Informed search (A*, Greedy)
o Local search techniques
• Essential for planning and decision making.

4. Learning
• Enables systems to improve performance with experience.
• Includes:
o Inductive learning
o Decision tree learning
o Neural network learning
o Genetic learning

5. Perception
• Allows AI systems to interpret sensory input.
• Includes processing of:
o Visual data
o Speech
o Text (NLP)

6. Action / Actuation
• Enables AI systems to take actions in the environment.
• Includes:
o Planning
o Control
o Interaction with environment through actuators

Conclusion
• AI is a combination of knowledge, reasoning, learning, perception, and action.
• Proper integration of these components enables intelligent system behavior.
Describe Depth Limited Search.
Depth Limited Search (DLS)
Definition:
• Depth Limited Search is a modified form of Depth First Search (DFS) in which a
predefined depth limit (L) is imposed on the search.
• The search does not expand nodes beyond this specified depth.

Working Principle:
• Begins from the initial node.
• Explores nodes depth-wise like DFS.
• When the current depth reaches the given limit, the search stops expanding further.
• Prevents infinite descent in search spaces with loops or infinite depth.

Characteristics:
• Uses stack-based recursion.
• Introduces a cutoff when depth limit is reached.
• Returns one of three outcomes:
o Success (goal found)
o Failure (no solution within limit)
o Cutoff (limit reached before finding solution)

Advantages:
• Avoids infinite paths present in DFS.
• Requires less memory compared to BFS.
• Simple to implement.

Limitations:
• Not complete if solution depth exceeds the limit.
• Not optimal.
• Choosing an appropriate depth limit is difficult.

Conclusion:
• Depth Limited Search is useful when a maximum depth of solution is known.
• It forms the basis of Iterative Deepening Search, combining DFS efficiency with BFS
completeness.
Describe Neural Network Based Learning.
Neural Network Based Learning
Definition:
• Neural Network Based Learning is a learning approach in Artificial Intelligence that is
inspired by the structure and functioning of the human brain.
• It consists of interconnected processing units called neurons, organized in layers.

Structure of a Neural Network:

• Input Layer: Receives input features.
• Hidden Layer(s): Perform intermediate computation and feature extraction.
• Output Layer: Produces final result or classification.

Working Principle:
1. Input values are fed to the network.
2. Each neuron computes a weighted sum of inputs.
3. An activation function is applied to produce output.
4. Output is compared with desired output to compute error.
5. Weights are adjusted using a learning rule (e.g., error correction).
6. The process is repeated until acceptable accuracy is achieved.
Learning Characteristics:
• Learns from examples (training data).
• Capable of generalization.
• Supports parallel processing.
• Handles noisy and incomplete data effectively.

Advantages:
• Can learn complex, non-linear relationships.
 • Robust to noise.
• Adaptive in nature.
Limitations:
• Requires large training data.
• Learning process may be slow.
• Difficult to interpret internal knowledge.

Conclusion:
• Neural Network Based Learning is a powerful AI learning technique.
• It is widely used for pattern recognition, classification, and prediction tasks.
• It forms a core part of learning mechanisms in Artificial Intelligence.

Describe DFS. Does DFS always ensures completeness and optimality? Justify.
Depth First Search (DFS)
Definition:
• Depth First Search is an uninformed search strategy that explores a search tree by
expanding the deepest node first.
• It proceeds along a path until no further expansion is possible, then backtracks.

Working Principle:
• Starts from the initial node.
• Selects one successor and explores it fully before exploring other successors.
• Uses a stack (LIFO) or recursion to manage nodes.

Properties of DFS
1. Completeness
• DFS is not always complete.
• If the search space has infinite depth or loops, DFS may get stuck exploring an
infinite path and never find the solution.
• DFS is complete only if the search space is finite and contains no cycles.
2. Optimality
• DFS is not optimal.
• It does not guarantee the shortest or least-cost path.
• A solution found at a deeper level may be returned before a shallower optimal
solution.
Advantages:
• Low memory requirement.
• Simple to implement.
• Useful when solution is expected to be deep.

Limitations:
• May fail to find a solution in infinite spaces.
• Does not guarantee optimal solutions.

Conclusion:
• DFS is a memory-efficient search technique.
• It does not always ensure completeness or optimality.
• Suitable for problems with finite depth and limited branching.

Describe minimax procedure.

Minimax Procedure
Definition:
• Minimax is an adversarial search algorithm used in game playing.
• It is applied in two-player, zero-sum games where one player’s gain is the other’s
loss.
• One player tries to maximize the score (MAX), while the opponent tries to minimize
it (MIN).
Basic Assumptions:
• Both players play optimally.
• Game has a finite number of states.
• Complete knowledge of game rules and outcomes.
Working Principle:
1. Construct a game tree from the current state.
2. Assign utility values to terminal (leaf) nodes.
3. At MAX nodes, select the maximum value among children.
4. At MIN nodes, select the minimum value among children.
5. Propagate values upward to the root.
6. The root value determines the optimal move for MAX.
Key Characteristics:
• Alternates between MAX and MIN levels.
• Guarantees optimal decision assuming rational opponent.
• Searches the entire game tree up to a given depth.

Limitations:
• High time complexity due to exponential growth.
• Inefficient for large game trees without pruning.

Conclusion:
• Minimax provides a systematic decision-making strategy in adversarial
environments.
• It forms the foundation for advanced techniques like Alpha–Beta pruning.

Describe alpha-beta pruning procedure.

Alpha–Beta Pruning Procedure
Definition:
• Alpha–Beta pruning is an optimization technique for the Minimax algorithm.
• It reduces the number of nodes evaluated by pruning branches that cannot affect
the final decision.
• It produces the same optimal result as Minimax but with fewer node expansions.

Key Concepts:
• Alpha (α): Best (highest) value found so far for the MAX player.
• Beta (β): Best (lowest) value found so far for the MIN player.

Working Procedure:
1. Initialize:
o α = −∞ (for MAX)
o β = +∞ (for MIN)
2. Traverse the game tree depth-first.
3. At MAX node:
o Update α = max(α, value of child)
o If α ≥ β, prune remaining children (β-cutoff).
4. At MIN node:
o Update β = min(β, value of child)
o If β ≤ α, prune remaining children (α-cutoff).
5. Continue until terminal nodes or depth limit is reached.
Advantages:
• Significantly reduces search space.
• Improves time efficiency.
• Allows deeper search in the same time.

Limitations:
• Effectiveness depends on node ordering.
• Worst-case performance same as Minimax.

Conclusion:
• Alpha–Beta pruning enhances Minimax by eliminating irrelevant branches.
• It is essential for practical game-playing AI systems.

Describe state space search.

State Space Search
Definition:
• State space search is a problem-solving method in Artificial Intelligence where a
problem is represented as a set of states and the transitions between them.
 • The solution is obtained by searching for a path from the initial state to a goal state.
Components of State Space Search:
1. State
o A representation of a configuration of the problem.
2. Initial State
o The starting point of the search.
3. Goal State
o The desired state that satisfies the problem objective.
4. Operators (Actions)
o Define legal transitions between states.
5. State Space
o The set of all possible states reachable from the initial state.

Search Process:
• A search algorithm explores the state space by:
o Generating successor states
o Testing for goal state
o Expanding states based on a chosen strategy

Search Strategies:
• Uninformed search: BFS, DFS, DLS
• Informed search: A*, Greedy search
• Local search: Hill climbing, Simulated annealing

Conclusion:
• State space search provides a general framework for AI problem solving.
• Efficient search strategy selection is crucial to manage combinatorial explosion.

What are the advantages of BFS over DFS and vice-versa?

Advantages of BFS over DFS
1. Completeness
o BFS is complete if the branching factor is finite.
o It is guaranteed to find a solution if one exists.
2. Optimality
o BFS always finds the shortest path (minimum number of steps) when step
costs are equal.
o DFS does not guarantee optimal solutions.
3. Systematic Exploration
o Explores nodes level by level, avoiding deep irrelevant paths.

Advantages of DFS over BFS

1. Memory Efficiency
o DFS requires much less memory than BFS.
o BFS stores all nodes at a level, causing high memory usage.
2. Faster for Deep Solutions
o DFS can reach a deep goal quickly without exploring all shallow nodes.
3. Simple Implementation
o DFS is easier to implement using recursion or stack.

Conclusion
• BFS is preferred when optimality and completeness are required.
• DFS is preferred when memory is limited or solutions are expected to be deep.
• Choice depends on problem constraints and search space characteristics.

Does Uniform Cost Search ensure completeness and optimality? Justify.

Uniform Cost Search (UCS)
Definition:
• Uniform Cost Search is an uninformed search algorithm that expands the node with
the lowest path cost g(n).
• It uses a priority queue ordered by cumulative cost.

Completeness of UCS
• UCS is complete, provided that:
o All step costs are positive (non-zero).
 o The branching factor is finite.
• It will eventually expand the least-cost path to the goal.
Optimality of UCS
• UCS is optimal.
• It always finds the least-cost solution because:
o Nodes are expanded in order of increasing path cost.
o The first time a goal node is selected for expansion, it has the minimum cost.

Justification
• UCS does not stop at the first goal encountered.
• It continues until the goal with the lowest path cost is found.
• Hence, no cheaper solution can be missed.

Conclusion
• Uniform Cost Search guarantees both completeness and optimality under standard
conditions.
• It is suitable for problems with variable step costs.

Describe the issues in Knowledge Representation.

Issues in Knowledge Representation
Knowledge Representation (KR) deals with how knowledge is represented, organized, and
used by an AI system. The main issues are as follows:
1. Representational Adequacy
• The KR scheme must be able to represent all required knowledge of the problem
domain.
• It should support facts, relationships, rules, and constraints.

2. Inferential Adequacy
• The representation should allow the system to derive new knowledge from existing
knowledge.
• It must support effective reasoning and inference mechanisms.

3. Inferential Efficiency
• The system should be able to draw conclusions efficiently.
• Knowledge should be organized to reduce unnecessary search and computation.

4. Acquisitional Efficiency
• It should be easy to add, modify, or update knowledge.
• The KR system must support knowledge acquisition without extensive
reprogramming.
5. Handling Uncertainty and Incompleteness
• Real-world knowledge is often incomplete or uncertain.
• KR should support uncertainty handling using probability, fuzzy logic, or belief
measures.
6. Expressiveness vs Simplicity
• A balance is required between expressive power and computational simplicity.
• Highly expressive systems may lead to inefficient reasoning.

Conclusion
• Knowledge Representation issues focus on what to represent, how to represent,
and how efficiently to reason.
• Proper handling of these issues is essential for building effective intelligent systems.

Does BFS ensure completeness and optimality? Justify.

Breadth First Search (BFS)
Definition:
• Breadth First Search is an uninformed search algorithm that explores the search
space level by level, expanding all nodes at a given depth before moving to the next
level.
Completeness of BFS
 • BFS is complete.
• If the branching factor is finite and a solution exists, BFS is guaranteed to find it.
• This is because BFS systematically explores all nodes at increasing depths.
Optimality of BFS
• BFS is optimal only when all step costs are equal (unit cost).
• Since BFS finds the shallowest goal first, it returns the solution with the minimum
number of steps.
• If step costs vary, BFS may return a non-optimal solution.

Justification
• BFS expands nodes strictly in order of depth.
• With uniform cost per action, depth corresponds directly to path cost.
• Hence, the first solution found is the least-cost solution under unit-cost conditions.

Conclusion
• BFS ensures completeness.
• BFS ensures optimality only for problems with equal step costs.
• For variable costs, Uniform Cost Search is preferred.

What are the characteristics of Heuristic Knowledge?

Characteristics of Heuristic Knowledge
Heuristic knowledge refers to experience-based knowledge used to guide search and
problem solving in Artificial Intelligence.
1. Experience-Based
• Derived from past experience or expert knowledge.
• Not obtained through formal or exhaustive reasoning.

2. Approximate in Nature
• Provides estimates or educated guesses rather than exact solutions.
• Does not guarantee correctness in all cases.

3. Problem-Specific
• Highly dependent on the problem domain.
• Effective in one domain but may not transfer well to another.

4. Reduces Search Space

• Guides the search toward promising states.
• Helps avoid unnecessary exploration of irrelevant paths.

5. Improves Efficiency
• Speeds up problem solving by reducing time and computation.
• Makes complex problems tractable.

6. Not Guaranteed to be Optimal

• May lead to sub-optimal solutions.
• Used for efficiency rather than guaranteed optimality.

Conclusion
• Heuristic knowledge trades optimality for efficiency.
• It is essential for solving large and complex AI problems where exhaustive search is
impractical.
List the quantifiers in first order logic.
Quantifiers in First Order Logic:
1. Universal Quantifier (∀)
o Denotes “for all”.
o Used to state that a predicate holds for all elements in the domain.
2. Existential Quantifier (∃)
o Denotes “there exists”.
o Used to state that a predicate holds for at least one element in the domain.
Conclusion:
First Order Logic uses two basic quantifiers: Universal (∀) and Existential (∃) to express
generality and existence.
Define Flat Local Maximum.
Flat Local Maximum:
• A flat local maximum is a plateau region in the search space where a large number
of neighboring states have the same heuristic value.
• Although no neighboring state is better, the state is not the global optimum.
• It causes local search algorithms like hill climbing to stall or terminate prematurely.

List the four ways of Knowledge Representation.

Four Ways of Knowledge Representation:
1. Logical Representation
2. Semantic Networks
3. Frames
4. Production Rules
Conclusion:
These four methods provide different mechanisms to represent and reason about
knowledge in Artificial Intelligence.
What are the kinds of knowledge that needs to be represented in AI systems?
Kinds of Knowledge in AI Systems
AI systems require different types of knowledge to reason, learn, and act intelligently.
1. Declarative Knowledge
• Knowledge about facts and statements.
• Describes what is true about the world.
• Example: Objects, properties, and relationships.

2. Procedural Knowledge
• Knowledge about how to perform tasks.
• Represented as procedures, algorithms, or rules.
• Guides the system’s actions and problem-solving steps.

3. Meta-Knowledge
• Knowledge about other knowledge.
• Used to control reasoning and decision-making.
• Helps in selecting appropriate inference strategies.

4. Heuristic Knowledge
• Experience-based and approximate knowledge.
• Used to guide search and reduce problem-solving effort.
• Improves efficiency but may not guarantee optimal solutions.

5. Structural Knowledge
• Knowledge about the organization and relationships among concepts.
• Represented using semantic networks or frames.
• Helps in understanding concept hierarchies.

Conclusion
• AI systems require multiple kinds of knowledge for effective intelligence.
• Proper representation of these knowledge types is essential for reasoning, learning,
and problem solving.
Explain PEAS Representation Model with an example.
PEAS Representation Model
Definition:
• PEAS is a framework used to specify the task environment of an intelligent agent.
• It stands for Performance measure, Environment, Actuators, Sensors.
• It helps in designing rational agents by clearly defining what the agent should
achieve and how it interacts with the environment.
Components of PEAS:
1. Performance Measure (P)
o Criteria used to evaluate the agent’s success.
 o Defines how well the agent is performing.
2. Environment (E)
o The external world in which the agent operates.
o May be fully/partially observable, static/dynamic, etc.
3. Actuators (A)
o Means by which the agent acts upon the environment.
o Used to execute actions.
4. Sensors (S)
o Means by which the agent perceives the environment.
o Provide percepts to the agent.

Example: Vacuum Cleaner Agent

PEAS Component Description
Performance Measure Cleanliness of rooms, minimum time and energy
Environment Two rooms (A and B) with dirt
Actuators Move left, move right, suck dirt
Sensors Dirt sensor, location sensor
Conclusion
• PEAS provides a systematic way to define agent tasks.
• It is essential for analyzing environments and designing appropriate agent
architectures.
• Widely used in intelligent agent design in AI.

What are the differences between the A* algorithm and the Greedy Best-First Search
algorithm?
Differences between A* Search and Greedy Best-First Search
Basis A* Algorithm Greedy Best-First Search
Evaluation f(n) = g(n) + h(n) f(n) = h(n)
function
Use of path cost Considers actual cost g(n) from start Ignores path cost
Heuristic role Used along with path cost Only heuristic is used
Optimality Optimal if heuristic is admissible Not optimal
Completeness Complete (finite branching, admissible h) Not always complete
Search behavior Balances cost so far and estimated cost Moves greedily toward
goal
Performance More systematic, may expand more Faster but less reliable
nodes
Conclusion
• A* search guarantees optimal and complete solutions under admissible heuristics.
• Greedy Best-First Search is faster but unreliable, as it may lead to sub-optimal
solutions.
• A* is preferred when solution quality matters, while Greedy search is used for
speed.
Explain Utility Based Agents with suitable diagram.
Utility-Based Agents
Definition:
• A utility-based agent is an intelligent agent that selects actions based on a utility
function.
• The utility function measures the degree of satisfaction or usefulness of a state.

Working Principle:
• The agent evaluates the expected utility of each possible action.
• It chooses the action that maximizes utility, not just goal achievement.
• Useful when multiple goals or trade-offs exist.
Components:
• Utility Function: Assigns a numerical value to each state.
• Model of Environment: Predicts outcomes of actions.
• Decision Mechanism: Selects action with maximum expected utility.

Characteristics:
• Handles conflicting goals effectively.
• Can deal with uncertainty and risk.
• More flexible than goal-based agents.

Advantages:
• Supports rational decision-making.
• Allows comparison among different outcomes.
• Performs well in complex and dynamic environments.

Limitations:
• Designing an accurate utility function is difficult.
• Computationally expensive.

Conclusion:
• Utility-based agents choose actions that maximize overall performance.
• They represent a powerful agent model for real-world decision-making in AI.

Define Tic-Tac-Toe problem. Explain with an example.

Tic-Tac-Toe Problem
Definition:
• The Tic-Tac-Toe problem is a classical AI problem used to illustrate game playing
and adversarial search.
• It is a two-player, zero-sum, deterministic, turn-taking game.
• One player uses symbol X and the other uses O.
• Players alternately place their symbols on a 3×3 grid.

Problem Formulation in AI Terms:

• Initial State:
Empty 3×3 board.
• Players:
Two players (X and O).
• Actions:
Place a symbol in any empty cell.
• State Space:
All possible configurations of the board.
 • Goal Test:
A player wins if three identical symbols appear:
o In a row, or
o In a column, or
o Diagonally.
• Utility Function:
+1 → Win
0 → Draw
−1 → Loss
Example:
Current board state:
X|O|X
O|X|O
_|_|_
• Player X places X in the bottom-right cell.
• X completes a diagonal.
• X wins the game.

Characteristics:
• Fully observable
• Deterministic
• Finite state space
• Suitable for Minimax and Alpha–Beta pruning

Conclusion:
• Tic-Tac-Toe is a simple yet powerful example for explaining state space
representation, utility, and adversarial search.
• It is widely used to demonstrate AI decision-making strategies.

Explain Bidirectional Search Algorithm with an example.

Bidirectional Search Algorithm
Definition:
• Bidirectional Search is an uninformed search technique that performs two
simultaneous searches:
o One forward from the initial state
o One backward from the goal state
• The search terminates when the two searches meet at a common state.

Working Principle:
1. Start one search from the initial node.
2. Start another search from the goal node.
3. Expand nodes alternately in both directions.
4. Stop when a node generated by one search appears in the other.
5. Construct the solution path by joining the two partial paths.
Key Characteristics:
• Uses two frontiers (OPEN lists).
• Requires the ability to generate predecessor states.
• Most effective when branching factor is high and solution depth is large.

Example:
Consider a simple state space:
Initial State: A
Goal State: G
Connections:
A→B→C→D→G
Forward Search:
A→B→C
Backward Search:
G→D→C
• Both searches meet at node C.
• Final solution path:
A→B→C→D→G
Advantages:
 • Reduces time complexity from O(b^d) to O(b^(d/2)).
• Faster than unidirectional search for large problems.
Limitations:
• Requires extra memory.
• Not applicable if goal state is not explicitly known.
• Difficult when reverse operators are hard to define.

Conclusion:
• Bidirectional search improves efficiency by searching from both ends.
• It is effective for problems with well-defined initial and goal states.

Discuss about features of environment.

Features (Characteristics) of an Environment
In Artificial Intelligence, the environment is the external world in which an agent operates.
The behavior and design of an agent depend on the nature of its environment. The main
features are:
1. Fully Observable vs Partially Observable
• Fully Observable: The agent can perceive the complete state of the environment at
any time.
• Partially Observable: The agent has limited or noisy information about the
environment.
2. Deterministic vs Stochastic
• Deterministic: The next state is completely determined by the current state and
action.
• Stochastic: Outcomes of actions are uncertain and probabilistic.

3. Episodic vs Sequential
• Episodic: Each action is independent of previous actions.
• Sequential: Current actions affect future states and decisions.

4. Static vs Dynamic
• Static: The environment does not change while the agent is deciding an action.
• Dynamic: The environment may change during the agent’s decision process.

5. Discrete vs Continuous
• Discrete: Finite number of states, actions, and percepts.
• Continuous: Infinite or continuous range of states and actions.

6. Single-Agent vs Multi-Agent
• Single-Agent: Only one agent operates in the environment.
• Multi-Agent: Multiple agents interact, either cooperatively or competitively.

Conclusion
• Environment features determine the complexity of agent design.
• Understanding these characteristics is essential for choosing appropriate agent
architectures and strategies.
State the main features of Hill-Climbing Algorithm.
Main Features of Hill-Climbing Algorithm
1. Local Search Technique
o Operates on a single current state.
o Does not maintain a search tree.
2. Heuristic-Based
o Uses a heuristic evaluation function to measure state quality.
o Chooses the best neighboring state.
3. Greedy Approach
o Always moves toward higher-value (better) states.
o Makes locally optimal decisions.
4. Low Memory Requirement
o Stores only the current state and its neighbors.
o Very memory efficient.
5. No Backtracking
 o Once a move is made, previous states are not reconsidered.
6. Fast Execution
o Suitable for large search spaces where exhaustive search is infeasible.

Conclusion
• Hill-climbing is simple and efficient but not guaranteed to find the global optimum.
• It may get stuck in local maxima, plateaus, or ridges.

Compare Simple Hill-Climbing Algorithm with Steepest-Ascent Hill-Climbing.

Comparison between Simple Hill-Climbing and Steepest-Ascent Hill-Climbing
Basis Simple Hill-Climbing Steepest-Ascent Hill-Climbing
Selection of Selects the first better neighbor Selects the best neighbor among
successor found all
Neighbor evaluation Evaluates neighbors one by one Evaluates all possible neighbors
Decision strategy Greedy and immediate Greedy but more informed
Computation cost Low computational cost Higher computational cost
Quality of solution May lead to sub-optimal
improvement
Higher chance of better
improvement
Speed Faster execution Slower due to full evaluation
Risk of local maxima High Still exists, but relatively lower
Conclusion
• Simple hill-climbing is faster and cheaper but less reliable.
• Steepest-ascent hill-climbing provides better decision quality at the cost of
increased computation.
• Both are local search techniques and do not guarantee global optimality.

Give some application areas of AI in healthcare sector.

Application Areas of AI in Healthcare
1. Medical Diagnosis
o AI systems assist doctors in diagnosing diseases based on symptoms, medical
history, and test results.
o Expert systems are used for decision support.
2. Medical Imaging
o AI helps in analyzing X-rays, CT scans, and MRI images.
o Improves detection of tumors, fractures, and abnormalities.
3. Expert Systems in Healthcare
o Knowledge-based systems provide recommendations for treatment and drug
selection.
o Used in clinical decision-making.
4. Patient Monitoring
o AI systems continuously monitor patient data such as heart rate and blood
pressure.
o Useful in intensive care units and remote healthcare.
5. Disease Prediction and Risk Analysis
o AI models predict the likelihood of diseases based on patient data.
o Helps in early detection and preventive care.
6. Healthcare Management
o AI supports hospital management, appointment scheduling, and resource
allocation.
o Improves efficiency of healthcare services.

Conclusion
• AI enhances accuracy, efficiency, and decision-making in healthcare.
• It plays a vital role in diagnosis, treatment support, and patient care.

What is Artificial Intelligence?

Artificial Intelligence (AI):
• Artificial Intelligence is a branch of computer science concerned with creating
systems that can perform tasks requiring human intelligence.
 • These tasks include reasoning, learning, problem solving, perception, and decision
making.
Conclusion:
Artificial Intelligence aims to develop intelligent machines capable of acting and thinking
rationally.
Define Turing Test.
Turing Test:
• The Turing Test is a test proposed by Alan Turing to determine whether a machine
can exhibit intelligent behavior indistinguishable from that of a human.
• A machine is said to pass the test if a human evaluator cannot reliably distinguish
between the machine and a human based on their responses.
Conclusion:
The Turing Test evaluates a machine’s ability to simulate human intelligence through
conversation.
What are the types of AI?
Types of Artificial Intelligence
Artificial Intelligence can be classified based on capability as follows:
1. Narrow AI (Weak AI)
o Designed to perform a specific task.
o Operates within a limited domain.
o Does not possess general intelligence.
2. General AI (Strong AI)
o Capable of performing any intellectual task that a human can do.
o Possesses reasoning, learning, and problem-solving abilities across domains.
o Currently theoretical.
3. Super AI
o Surpasses human intelligence in all aspects.
o Includes creativity, decision-making, and emotional intelligence.
o Hypothetical and not yet realized.

Conclusion
• Present AI systems mainly fall under Narrow AI.
• General and Super AI represent future possibilities in AI research.

Discuss the problems of AI.

Problems of Artificial Intelligence
Artificial Intelligence faces several challenges that limit its effectiveness and practical
implementation.
1. Knowledge Acquisition Problem
• Acquiring accurate and complete knowledge from experts is difficult.
• Human knowledge is often tacit, incomplete, or inconsistent.

2. Knowledge Representation Issues

• Representing real-world knowledge in a machine-understandable form is complex.
• Difficult to handle uncertainty, ambiguity, and incomplete information.

3. Combinatorial Explosion
• Search space grows exponentially with problem size.
• Makes exhaustive search computationally infeasible.

4. Lack of Common Sense

• AI systems lack common-sense reasoning that humans naturally possess.
• Difficult to model everyday knowledge and intuition.

5. Computational Complexity
• Many AI algorithms require high processing time and memory.
• Real-time decision making becomes difficult.

6. Learning Limitations
• Learning algorithms may require large amounts of data.
• Risk of overfitting or poor generalization.
Conclusion
• AI problems arise due to knowledge complexity, computational limits, and
uncertainty.
• Overcoming these challenges is essential for building robust and intelligent systems.

Explain Production System.

Production System
Definition:
• A production system is a rule-based problem-solving framework used in Artificial
Intelligence.
• Knowledge is represented in the form of production rules of the type:
IF condition THEN action.
• It separates knowledge representation from control strategy.

Components of a Production System

1. Rule Base (Production Rules)
o A set of condition–action rules.
o Specifies what action to take when certain conditions are satisfied.
2. Working Memory
o Stores the current facts and state information of the problem.
o Updated after applying rules.
3. Inference Engine (Control Strategy)
o Selects and applies appropriate rules.
o Resolves conflicts when multiple rules are applicable.

Working Principle
• Match rules against working memory.
• Select one rule using a control strategy.
• Execute the action part of the rule.
• Update working memory.
• Repeat until goal state is reached or no rule is applicable.

Characteristics
• Modular and flexible.
• Supports heuristic reasoning.
• Suitable for search and problem-solving tasks.

Conclusion
• Production systems provide a systematic approach to problem solving in AI.
• They are widely used in expert systems and rule-based reasoning.

Differentiate between goal-based and utility-based agents.

Difference between Goal-Based and Utility-Based Agents
Basis Goal-Based Agent Utility-Based Agent
Decision criterion Achieves a specific goal Maximizes utility value
Evaluation of states States
goal
are either goal or non- States are assigned numerical
utility values
Handling of trade- Cannot compare multiple goal- Can compare and choose best
offs achieving states among alternatives
Dealing with Limited capability Handles uncertainty and risk
uncertainty effectively
Flexibility Less flexible More flexible and rational
Performance Goal satisfaction Degree of satisfaction (utility)
measure
Conclusion
• Goal-based agents focus only on reaching a goal state.
• Utility-based agents select actions that maximize overall benefit.
• Utility-based agents are more suitable for complex and uncertain environments.

How does alpha-beta pruning improve minimax?

Improvement of Minimax by Alpha–Beta Pruning
• Alpha–Beta pruning eliminates branches in the game tree that cannot influence the
final decision.
• It avoids evaluating nodes that will never be chosen by rational players.
• The algorithm keeps track of:
o Alpha (α): best value for MAX found so far
o Beta (β): best value for MIN found so far
• When α ≥ β, further exploration of that branch is pruned.

Benefits:
• Significantly reduces the number of node evaluations.
• Allows the algorithm to search deeper within the same time.
• Produces the same optimal result as Minimax.

Conclusion
• Alpha–Beta pruning improves Minimax by increasing efficiency without affecting
correctness.
• It is essential for practical game-playing AI systems.

Solve 8-puzzle using DFS/BFS.

8-Puzzle Problem
Definition:
• The 8-puzzle consists of 8 numbered tiles and one blank space arranged in a 3×3
grid.
• The objective is to reach the goal state from an initial state by sliding tiles into the
blank space.
• Allowed moves: Up, Down, Left, Right (if possible).

State Representation
• A state is represented as a 3×3 matrix.
• The blank tile is denoted by 0.
Initial State (Example):
123
406
758
Goal State:
123
456
780
Operators (Moves)
• Move blank Up
• Move blank Down
• Move blank Left
• Move blank Right

Solving 8-Puzzle using Breadth First Search (BFS)

BFS Principle
• BFS explores the state space level by level.
• Uses a FIFO queue.
• Guarantees optimal solution (minimum number of moves).

BFS Algorithm (Outline)

1. Insert initial state into OPEN list (queue).
2. If state is goal → stop.
3. Generate all valid successor states.
4. Insert unexplored states into queue.
5. Repeat until goal is found.
BFS Solution Path (One Possible Solution)
Initial:
123
406
758
Move blank Down:
123
456
708
Move blank Right:
123
456
780
Goal state reached
Solving using Depth First Search (DFS)
DFS Principle
• Explores one branch fully before backtracking.
• Uses a stack (LIFO).
• Not optimal and may get stuck in deep paths.

DFS Characteristics
• Less memory usage than BFS
• No guarantee of shortest solution
• Complete only for finite state space

Comparison (Brief)
Criteria BFS DFS
Completeness Yes Not always
Optimality Yes No
Memory High Low
Solution quality Best May be poor
Conclusion
• The 8-puzzle is a state space search problem.
• BFS guarantees an optimal solution.
• DFS is memory efficient but unreliable.
• BFS is preferred for solving the 8-puzzle in AI.

Explain the semantic nets, frames and scripts.

1. Semantic Networks
Definition:
• A semantic network is a graph-based knowledge representation method.
• Knowledge is represented using nodes and links.
Components:
• Nodes: Represent objects, concepts, or instances.
• Links: Represent relationships between nodes (ISA, HAS, PART-OF).
Features:
• Supports inheritance of properties.
• Easy to visualize and understand.
• Suitable for representing hierarchical knowledge.
Limitation:
• Difficult to handle complex logic and exceptions.

2. Frames
Definition:
• Frames are structured data representations for stereotyped situations.
• They represent knowledge as a collection of slots and values.
Components:
• Frame: Represents an object or concept.
• Slots: Attributes or properties.
• Slot values: Specific values or default values.
Features:
• Supports default reasoning.
• Allows inheritance between frames.
• Efficient for representing objects with attributes.
Limitation:
• Less suitable for representing dynamic events.

3. Scripts
Definition:
• A script is a knowledge representation technique used to describe a sequence of
events in a familiar situation.
• It captures procedural and temporal knowledge.
Components:
• Roles: Participants in the event.
• Scenes: Sequence of actions.
• Props: Objects involved.
• Entry and exit conditions.
Features:
• Useful for understanding natural language stories.
• Reduces ambiguity by providing expected event sequences.
Limitation:
• Not flexible for unusual or unexpected situations.

Conclusion
• Semantic Networks represent conceptual relationships.
• Frames represent structured object knowledge.
• Scripts represent event-based procedural knowledge.
• All three are important knowledge representation techniques in Artificial
Intelligence.
Explain resolution in FOPL.
Resolution in FOPL
Definition:
• Resolution is a sound and complete inference rule used in First Order Predicate
Logic for automated theorem proving.
• It proves a statement by refutation, i.e., by showing that the negation of the
statement leads to a contradiction.
Basic Idea:
• Convert all given knowledge and the negation of the goal into clause form.
• Apply the resolution rule repeatedly to derive an empty clause (⊥).
• Derivation of the empty clause proves the original statement.

Resolution Rule (FOPL):

• From two clauses containing complementary literals, infer a new clause.
Example (after unification):
• (P(x) ∨ Q(x))
• (¬P(a))
• Resolvent: Q(a)

Steps Involved in Resolution in FOPL:

1. Convert formulas into Clause Form
o Eliminate implications
o Move negations inward
o Standardize variables
o Skolemize existential quantifiers
o Convert to Conjunctive Normal Form (CNF)
2. Negate the Goal
o Add the negated goal to the knowledge base.
3. Unification
o Apply substitutions to make literals identical.
4. Apply Resolution Rule
o Resolve complementary literals to generate new clauses.
5. Derive Empty Clause
o If empty clause is derived, contradiction is reached.

Properties:
• Uses unification (unlike propositional resolution).
• Refutation-based method.
• Guarantees correctness in logical inference.

Conclusion
• Resolution is a fundamental reasoning mechanism in FOPL.
• It forms the basis of automated reasoning and logic programming.
 • Widely used in theorem provers and AI inference systems.
Write short note on Bayesian networks.
Bayesian Networks
Definition:
• A Bayesian Network is a probabilistic graphical model used to represent uncertainty
in knowledge.
• It represents random variables and their conditional dependencies using a directed
acyclic graph (DAG).
Components:
• Nodes: Represent random variables.
• Directed edges: Represent conditional dependencies between variables.
• Conditional Probability Table (CPT): Quantifies the effect of parent nodes on a
variable.
Features:
• Supports reasoning under uncertainty.
• Allows probabilistic inference.
• Compact representation of joint probability distributions.

Applications:
• Diagnosis systems
• Decision support
• Prediction and reasoning under uncertainty

Conclusion:
• Bayesian Networks provide a powerful framework for probabilistic reasoning.
• They are widely used in AI systems where uncertain or incomplete information
exists
Write short note on Fuzzy Logic.
Fuzzy Logic
Definition:
• Fuzzy Logic is a reasoning technique used in Artificial Intelligence to handle
imprecise, vague, and uncertain information.
• Unlike classical logic, it allows partial truth values ranging between 0 and 1.

Key Concepts:
• Fuzzy Set: Elements have degrees of membership.
• Membership Function: Assigns a value between 0 and 1 indicating degree of truth.
• Linguistic Variables: Variables described using natural language terms like high,
medium, low.
Features:
• Mimics human reasoning.
• Handles uncertainty effectively.
• Flexible and tolerant to imprecision.

Applications:
• Control systems
• Decision-making systems
• Pattern recognition

Conclusion:
• Fuzzy Logic provides a practical approach for reasoning in real-world uncertain
environments.
• It is an important tool in AI-based decision systems.

Explain decision tree with example.

Decision Tree
Definition:
• A decision tree is a supervised learning technique used for classification and
decision making.
 • It represents knowledge in the form of a tree structure, where decisions are made
by testing attributes.
Structure of a Decision Tree:
• Root Node: Represents the starting decision or attribute.
• Internal Nodes: Represent tests on attributes.
• Branches: Represent outcomes of tests.
• Leaf Nodes: Represent final decisions or class labels.

Working Principle:
1. Select the best attribute based on a measure like information gain.
2. Split the dataset according to attribute values.
3. Repeat the process recursively for each subset.
4. Stop when all instances belong to the same class or no attribute remains.
Example:
Problem: Decide whether to Play Game based on weather.
• Root attribute: Weather
• Possible values: Sunny, Rainy
Decision Tree (textual):
• If Weather = Sunny → Do not play
• If Weather = Rainy → Play

Advantages:
• Simple and easy to understand.
• No complex mathematical computation.
• Efficient for decision-making.

Limitations:
• Can become complex for large datasets.
• Prone to overfitting.

Conclusion:
• Decision trees provide a clear and structured method for inductive learning.
• They are widely used in AI for classification and rule extraction.

What is an expert system? Name some shells.

Expert System
Definition:
• An expert system is an Artificial Intelligence system that emulates the decision-
making ability of a human expert in a specific domain.
• It uses domain knowledge and inference rules to solve complex problems.

Expert System Shells

An expert system shell is a software environment that provides the inference mechanism
without domain knowledge.
Examples of Expert System Shells:
1. EMYCIN
2. CLIPS
3. OPS5
4. KAPPA
5. ART
Conclusion
• Expert systems provide expert-level solutions using stored knowledge.
• Shells simplify development by separating knowledge base from inference engine.

Explain the key characteristics and scope of Artificial Intelligence, with examples from
real-world applications. What are different platforms for Artificial Intelligence (AI)
development?
Key Characteristics of AI
• Ability to reason and make decisions
• Capability to learn from experience
• Problem-solving using search and heuristics
• Handling uncertainty and incomplete information
 • Interaction with environment through perception and action
Scope of AI (Applications)
• Expert systems (medical diagnosis)
• Game playing (chess, tic-tac-toe)
• Natural Language Processing
• Robotics and automation
• Decision support systems
AI Development Platforms
• Python
• Prolog
• LISP
• Java
• MATLAB
Conclusion:
AI enables machines to perform intelligent tasks across diverse domains using suitable
programming platforms.
Describe the Tic-Tac-Toe problem as a state space search problem. Include initial state,
operators, goal state, and search tree.
Tic-Tac-Toe as a State Space Search Problem
• Initial State:
Empty 3×3 board.
• State Representation:
Each configuration of the board with X and O.
• Operators:
Placing X or O in any empty cell.
• Goal State:
Three identical symbols in a row, column, or diagonal.
• Search Tree:
Nodes represent board states, edges represent legal moves.
Conclusion:
Tic-Tac-Toe demonstrates adversarial search and state space exploration in AI.
How problems can be solved using AI? Advantages and disadvantages of AI.
Problem Solving in AI
• Problems are solved using:
o State space representation
o Search techniques (BFS, DFS, A*)
o Heuristics for efficiency
o Reasoning and inference
Advantages of AI
• High accuracy and consistency
• Faster decision making
• Handles complex problems
• Reduces human effort
Disadvantages of AI
• High development cost
• Lack of common sense
• Dependence on quality data
• Ethical and employment concerns
Conclusion:
AI solves problems efficiently but has limitations related to cost and adaptability.
Write short note on AI model.
AI Models
AI models describe how intelligence is simulated in machines.
Major AI Models:
• Acting humanly (Turing Test model)
• Thinking humanly (cognitive model)
• Thinking rationally (logic-based model)
• Acting rationally (rational agent model)
Conclusion:
AI models provide different perspectives for designing intelligent systems.
Define an intelligent agent. Explain the structure of intelligent agents with examples.
Types of environment related to intelligent agent.
Intelligent Agent
An intelligent agent is an entity that perceives through sensors and acts through actuators
to achieve goals.
Structure of Intelligent Agent
• Sensors → Percepts
• Agent function → Decision making
• Actuators → Actions
Example:
Vacuum cleaner agent.
Types of Environment
• Fully / Partially observable
• Deterministic / Stochastic
• Static / Dynamic
• Discrete / Continuous
Conclusion:
Agent structure and environment characteristics determine intelligent behavior.
What is history and foundation of Artificial Intelligence?
History of Artificial Intelligence
• The concept of Artificial Intelligence originated in the 1950s.
• In 1950, Alan Turing proposed the idea of machine intelligence and introduced the
Turing Test.
• The term Artificial Intelligence was formally coined by John McCarthy in 1956 at the
Dartmouth Conference, which is considered the birth of AI as a field.
• Early AI focused on problem solving, game playing, and symbolic reasoning.
• Development progressed through phases such as early optimism, AI winter (slow
progress), and renewed growth with better algorithms and computing power.
Foundations of Artificial Intelligence
AI is built on ideas and techniques from multiple disciplines:
1. Philosophy
o Logic, reasoning, and the concept of intelligence.
2. Mathematics
o Formal logic, probability, statistics, and algorithms.
3. Computer Science
o Data structures, algorithms, programming languages.
4. Psychology
o Human learning, cognition, and problem-solving behavior.
5. Neuroscience
o Understanding brain structure and neural processing.
6. Linguistics
o Language structure and meaning (basis of NLP).

Conclusion
• The history of AI shows a gradual evolution from theoretical ideas to practical
systems.
• Its foundations lie in logic, computation, cognition, and learning, making AI an
interdisciplinary field essential for building intelligent systems.
What are the advantages and disadvantages of AI?
Advantages of Artificial Intelligence
1. High Accuracy
o Reduces human errors in decision making.
2. Fast Decision Making
o Processes large amounts of data quickly.
3. Automation
o Performs repetitive and routine tasks efficiently.
4. 24×7 Availability
o Works continuously without fatigue.
5. Handles Complex Problems
o Useful in solving large and complicated problems.
Disadvantages of Artificial Intelligence
1. High Development Cost
o Requires expensive hardware and software.
2. Lack of Creativity and Emotions
o Cannot think beyond programmed rules.
3. Job Displacement
o Automation may reduce human employment.
4. Dependence on Data
o Performance depends heavily on quality of data.
5. Lack of Common Sense
o Cannot make judgments like humans in unexpected situations.

Conclusion
• AI provides efficiency and accuracy but has limitations related to cost, adaptability,
and human factors.
• Balanced use of AI is essential for effective and ethical deployment.

What are the pitfalls of hill-climbing algorithm?

Pitfalls of Hill-Climbing Algorithm
Hill-climbing is a greedy local search technique and suffers from several inherent limitations:
1. Local Maximum
o The algorithm may get stuck at a state that is better than all its neighbors but
is not the global optimum.
2. Plateau
o A flat region of the search space where neighboring states have the same
heuristic value.
o The algorithm has no direction for improvement and may terminate.
3. Ridge
o A situation where the optimal path requires a series of sideways or
downward moves.
o Hill climbing fails because it considers only immediate improvement.
4. No Backtracking
o Once a move is made, the algorithm cannot return to previous states.
5. Not Guaranteed Optimal
o The algorithm does not guarantee finding the best possible solution.

Conclusion
• Hill-climbing is fast and memory efficient but unreliable.
• Its greedy nature makes it unsuitable for problems with complex search landscapes.

Did Depth Limited Search always show the completeness property? Explain.
Depth Limited Search (DLS) and Completeness
Depth Limited Search (DLS):
• DLS is a variant of Depth First Search in which a fixed depth limit (L) is imposed.
• Nodes beyond this limit are not expanded.

Completeness Property
Answer:
No, Depth Limited Search does not always ensure completeness.
Explanation:
• DLS is complete only if the depth limit L is greater than or equal to the depth of the
shallowest goal node.
• If the actual solution lies beyond the chosen depth limit, DLS will fail to find the
solution, even if one exists.
• In such cases, the algorithm terminates with a cutoff, not success.

Conditions Affecting Completeness:

• ✔ Complete if:
o Search space is finite
o Solution depth ≤ depth limit
• Not complete if:
o Solution depth > depth limit
o Depth limit is chosen incorrectly
Conclusion:
• Depth Limited Search does not always guarantee completeness.
• Completeness depends on the correct selection of depth limit.
• This limitation is overcome by Iterative Deepening Search, which gradually increases
the depth limit.
Define α-cutoff and β-cutoff of a game tree.
α-cutoff (Alpha Cutoff)
• An α-cutoff occurs at a MIN node in a game tree.
• It happens when the value of the MIN node becomes less than or equal to the
current α value of its ancestor MAX node.
• In this case, further exploration of that branch is stopped, as MAX will never choose
this path.
Condition:
β ≤ α (at MIN node)
β-cutoff (Beta Cutoff)
• A β-cutoff occurs at a MAX node in a game tree.
• It happens when the value of the MAX node becomes greater than or equal to the
current β value of its ancestor MIN node.
• Further exploration is pruned, since MIN will avoid this branch.
Condition:
α ≥ β (at MAX node)
Conclusion
• α-cutoff and β-cutoff are pruning conditions used in Alpha–Beta pruning.
• They reduce the number of node evaluations without affecting the optimal Minimax
decision.
Explain the phenomenon “Stuck at local optimum” in Hill Climbing. How can it be resolved
using Simulated Annealing?
Stuck at Local Optimum in Hill Climbing
Hill Climbing:
• Hill climbing is a local search algorithm that moves to the best neighboring state
based on a heuristic value.
Local Optimum:
• A local optimum is a state that is better than all its immediate neighbors but not the
global optimum.
• In such a state, no neighboring move improves the heuristic value.
Problem:
• Hill climbing terminates prematurely at a local optimum.
• It cannot move to worse states, so it fails to reach the global optimum.

Resolution using Simulated Annealing

Simulated Annealing Approach:
• Simulated Annealing allows probabilistic acceptance of worse moves.
• A worse move is accepted with probability:
P = e^(−ΔE / T)
How it Helps:
• At high temperature, worse moves are accepted frequently.
• This allows the algorithm to escape local optima.
• As temperature decreases, the algorithm behaves more like hill climbing.

Conclusion
• Hill climbing fails due to greedy behavior.
• Simulated Annealing overcomes this by controlled randomness.
• Hence, Simulated Annealing effectively resolves the local optimum problem in hill
climbing.
Justify the statement: DFS can be viewed as a special case of Depth-Limited Search.
Justification
Depth First Search (DFS):
• DFS expands the deepest unexpanded node first.
• It continues along a path until a goal is found or no further expansion is possible.
 • DFS has no predefined depth limit.
Depth-Limited Search (DLS):
• DLS is a modified DFS in which a fixed depth limit (L) is imposed.
• Nodes beyond depth L are not expanded.

Relationship Between DFS and DLS

• If the depth limit L is set to infinity (or a very large value) in DLS:
o There is no restriction on depth expansion.
o The behavior of DLS becomes identical to DFS.
• Thus, DFS can be considered as Depth-Limited Search with infinite depth limit.

Conclusion
• DFS is a special case of Depth-Limited Search where the depth limit is unbounded.
• Hence, the statement is justified.

What is the difference between Greedy Best-First Search and A* Search?

Difference between Greedy Best-First Search and A* Search
Basis Greedy Best-First Search A* Search
Evaluation function f(n) = h(n) f(n) = g(n) + h(n)
Use of path cost Ignores path cost g(n) Considers path cost g(n)
Search strategy Expands node closest to goal Balances cost so far and estimated cost
Optimality Not optimal Optimal with admissible heuristic
Completeness Not always complete Complete under finite conditions
Performance Faster but unreliable Slower but reliable
Conclusion
• Greedy Best-First Search focuses only on goal proximity.
• A* Search ensures optimal and complete solutions.
• A* is preferred when solution quality is critical.

Under what condition is Breadth-First Search (BFS) optimal?

• Breadth-First Search is optimal when all step costs are equal (unit cost).
• Under this condition, the shallowest goal node corresponds to the least-cost
solution, which BFS always finds first.
Conclusion:
BFS is optimal only in uniform-cost (equal step cost) environments.
Show that any monotonic heuristic is admissible.
Definitions
Admissible Heuristic:
• A heuristic ℎ(𝑛)is admissible if it never overestimates the actual minimum cost
ℎ∗ (𝑛)to reach the goal.
• Formally:
ℎ(𝑛) ≤ ℎ∗ (𝑛)for all nodes 𝑛.
Monotonic (Consistent) Heuristic:
• A heuristic is monotonic if for every node 𝑛and its successor 𝑛′ with step cost
𝑐(𝑛, 𝑛′ ):
ℎ(𝑛) ≤ 𝑐(𝑛, 𝑛′ ) + ℎ(𝑛′ ).
• Also, ℎ(𝑔𝑜𝑎𝑙) = 0.

Proof
1. Consider any path from a node 𝑛to a goal node:
𝑛 = 𝑛0 → 𝑛1 → 𝑛2 → ⋯ → 𝑛𝑘 = 𝑔𝑜𝑎𝑙
2. Applying the monotonic condition repeatedly:
ℎ(𝑛0 ) ≤ 𝑐(𝑛0 , 𝑛1 ) + ℎ(𝑛1 )
ℎ(𝑛1 ) ≤ 𝑐(𝑛1 , 𝑛2 ) + ℎ(𝑛2 )
⋮
ℎ(𝑛𝑘−1 ) ≤ 𝑐(𝑛𝑘−1 , 𝑛𝑘 ) + ℎ(𝑛𝑘 )
 3. Adding all inequalities:
ℎ(𝑛0 ) ≤ 𝑐(𝑛0 , 𝑛1 ) + 𝑐(𝑛1 , 𝑛2 ) + ⋯ + 𝑐(𝑛𝑘−1 , 𝑛𝑘 ) + ℎ(𝑔𝑜𝑎𝑙)
4. Since ℎ(𝑔𝑜𝑎𝑙) = 0:
ℎ(𝑛0 ) ≤ actual path cost from 𝑛0 to goal
5. The actual minimum path cost is ℎ∗ (𝑛0∗), hence:
ℎ(𝑛0 ) ≤ ℎ (𝑛0 )

Conclusion
• A monotonic heuristic never overestimates the true cost to the goal.
• Therefore, every monotonic heuristic is admissible.

Discuss on Bidirectional Search Technique.

Bidirectional Search Technique
Definition:
• Bidirectional Search is an uninformed search technique that performs two
simultaneous searches:
o One forward from the initial state
o One backward from the goal state
• The search stops when both searches meet at a common state.

Working Principle:
1. Initialize two search frontiers:
o Forward frontier from the start node
o Backward frontier from the goal node
2. Expand nodes alternately (or level by level) from both directions.
3. Check for intersection of the two frontiers.
4. Once an intersection is found, combine the paths to obtain the solution.
Characteristics:
• Requires explicit goal state.
• Needs ability to generate reverse operators.
• Usually implemented using BFS in both directions.

Advantages:
• Reduces time complexity from 𝑂(𝑏 𝑑 )to 𝑂(𝑏 𝑑/2 ).
• Faster than unidirectional search for large search depths.

Limitations:
• Requires high memory to store two frontiers.
• Not suitable when goal state is unknown.
• Difficult to apply when reverse moves are not defined.

Conclusion:
• Bidirectional Search improves efficiency by searching from both ends.
• It is effective for problems with well-defined initial and goal states.
• Used in path-finding and state-space problems in AI.

Define Heuristic Search.

Heuristic Search:
• Heuristic search is a search technique in Artificial Intelligence that uses heuristic
functions (h(n)) to guide the search toward the goal more efficiently.
• It reduces the search space by selecting nodes that appear most promising based on
heuristic knowledge.
Conclusion:
Heuristic search improves efficiency by using problem-specific knowledge to guide
exploration.
With an example show a simplified Frame System
Frame System
Definition:
• A frame system is a knowledge representation technique used to represent
stereotyped objects or situations.
• Knowledge is organized in the form of frames, which consist of slots and slot values.

Structure of a Frame
• Frame name: Represents an object or concept
• Slots: Attributes or properties
• Slot values: Specific or default values
• Inheritance: Frames can inherit properties from parent frames

Simplified Frame System – Example

Frame: PERSON
• Name : —
• Age : —
• Gender : —
Frame: STUDENT (ISA PERSON)
• Roll_No : —
• Course : —
• Institution : —
Frame: STUDENT_RAM (INSTANCE OF STUDENT)
• Name : Ram
• Age : 20
• Gender : Male
• Roll_No : 101
• Course : [Link]
• Institution : MAKAUT

Explanation
• STUDENT frame inherits general properties from PERSON.
• STUDENT_RAM is an instance that fills specific slot values.
• Default and inherited values reduce redundancy.

Conclusion
• Frame systems provide a structured and efficient way to represent knowledge.
• They support inheritance, default reasoning, and easy modification, making them
suitable for AI applications.
What is the difference between semantic net and frame?
Difference between Semantic Network and Frame
Basis Semantic Network Frame
Basic structure Graph-based representation Structured record-based
representation
Representation Nodes and links Frames with slots and values
form
Focus Relationships among concepts Attributes of objects or concepts
Inheritance Through ISA links Through frame hierarchy
Expressiveness Less detailed attribute Rich attribute representation
handling
Ease of modification Difficult to handle exceptions Supports default values and overrides
Conclusion
• Semantic networks emphasize relationships between concepts.
• Frames emphasize structured object descriptions.
• Both are important knowledge representation techniques, but frames are more
powerful for detailed representation.
What are the different approaches to knowledge representation?
Approaches to Knowledge Representation
Knowledge Representation (KR) refers to the methods used to encode knowledge so that an
AI system can reason and make decisions. The main approaches are:
1. Logical Representation
• Knowledge is represented using formal logic (propositional logic and predicate
logic).
• Supports precise reasoning and inference.
• Example: Facts and rules expressed using logical formulas.

2. Semantic Network
• Knowledge is represented as a graph of nodes and links.
• Nodes represent concepts and links represent relationships.
• Supports inheritance through ISA relationships.

3. Frame-Based Representation
• Knowledge is organized into frames consisting of slots and values.
• Suitable for representing structured objects.
• Supports default values and inheritance.

4. Production Rule Representation

• Knowledge is represented in the form of IF–THEN rules.
• Widely used in expert systems.
• Simple and modular.

5. Ontological Representation
• Knowledge is represented using concept hierarchies and relationships.
• Defines domain vocabulary formally.
• Useful for knowledge sharing and reuse.

Conclusion
• Different KR approaches are suited for different problem domains.
• A proper choice of representation improves reasoning efficiency and system
performance.
State the difference between Inheritable Knowledge and Inferential Knowledge.
Difference between Inheritable Knowledge and Inferential Knowledge
Basis Inheritable Knowledge Inferential Knowledge
Meaning Knowledge that can be passed from Knowledge that is derived from
parent to child concepts existing facts using reasoning
Source Obtained through hierarchical Obtained through inference rules
relationships and logic
Representation Commonly used in semantic
networks and frames
Used in logic-based systems and
rule-based systems
Mechanism Based on ISA or AKO relationships Based on deduction, induction, or
resolution
Nature Static and predefined Dynamic and derived during
reasoning
Example A student inherits properties of a Concluding “Socrates is mortal”
person from rules
Conclusion
• Inheritable knowledge reduces redundancy by sharing properties.
• Inferential knowledge enables AI systems to generate new knowledge.
• Both are essential for effective knowledge representation and reasoning in AI.

State the basic principle of Resolution method for both Proposition & Predicates.
Basic Principle of Resolution Method
1. Resolution in Propositional Logic
Principle:
• Resolution is a rule of inference based on refutation (proof by contradiction).
• To prove a proposition:
o Negate the statement to be proved.
 o Convert all formulas into clause form (CNF).
o Repeatedly apply the resolution rule.
o If an empty clause (⊥) is derived, the original statement is proved.
Resolution Rule (Propositional):
• From
(P ∨ Q) and (¬P ∨ R)
infer
(Q ∨ R)
2. Resolution in Predicate Logic (FOPL)
Principle:
• Predicate resolution extends propositional resolution by including variables and
predicates.
• It uses unification to make literals identical before resolution.
• Proof is again based on refutation.
Steps Involved:
• Convert all statements into clause form.
• Apply Skolemisation to eliminate existential quantifiers.
• Use unification to match predicates.
• Apply resolution to derive new clauses.
• Derivation of empty clause proves the goal.
Resolution Rule (Predicate):
• From
(P(x) ∨ Q(x)) and (¬P(a))
infer
Q(a) (after unification)
Conclusion
• Resolution is a sound and complete inference technique.
• In propositional logic, it works on literals directly.
• In predicate logic, it uses unification and substitution.
• It forms the basis of automated theorem proving in AI.

What is Dempster Shafer Theory?

Dempster–Shafer Theory
Definition:
• Dempster–Shafer Theory is a mathematical theory of evidence used to handle
uncertainty and incomplete information in Artificial Intelligence.
• It generalizes probability theory by allowing belief to be assigned to sets of
possibilities, not just single events.
Key Concepts:
• Frame of Discernment (Θ): Set of all possible hypotheses.
• Basic Probability Assignment (BPA): Assigns belief mass to subsets of Θ.
• Belief (Bel): Minimum degree of support for a proposition.
• Plausibility (Pl): Maximum possible support for a proposition.

Evidence Combination:
• Uses Dempster’s Rule of Combination to combine evidence from multiple
independent sources.
Conclusion:
• Dempster–Shafer Theory provides a flexible framework for reasoning under
uncertainty.
• It is useful when precise probabilities are difficult to obtain.

Differentiate between fuzzy set and crisp set.

Difference between Fuzzy Set and Crisp Set
Basis Crisp Set Fuzzy Set
Membership Element either belongs or does Element belongs with a degree of
not belong membership
Membership 0 or 1 only Any value between 0 and 1
value
Basis Crisp Set Fuzzy Set
Boundary Sharp and well-defined Gradual and vague
Logic used Classical (Boolean) logic Fuzzy logic
Handling Cannot handle vagueness Effectively handles vagueness
uncertainty
Conclusion
• Crisp sets are suitable for precise and well-defined domains.
• Fuzzy sets are suitable for real-world problems with uncertainty and imprecision.

Explain different fuzzy operations with examples.

Fuzzy Set Operations
Fuzzy operations are extensions of classical set operations, where elements have degrees of
membership in the range [0, 1].
Let:
• Fuzzy set A and B
• Membership functions: μA(x), μB(x)

1. Fuzzy Union (OR)

Definition:
• The membership value of an element in the union is the maximum of its
membership values.
Formula:
• μA∪B(x) = max [ μA(x), μB(x) ]
Example:
• μA(x) = 0.6
• μB(x) = 0.8
• μA∪B(x) = max(0.6, 0.8) = 0.8

2. Fuzzy Intersection (AND)

Definition:
• The membership value of an element in the intersection is the minimum of its
membership values.
Formula:
• μA∩B(x) = min [ μA(x), μB(x) ]
Example:
• μA(x) = 0.6
• μB(x) = 0.8
• μA∩B(x) = min(0.6, 0.8) = 0.6

3. Fuzzy Complement (NOT)

Definition:
• The membership value of an element in the complement is 1 minus its membership
value.
Formula:
• μ¬A(x) = 1 − μA(x)
Example:
• μA(x) = 0.7
• μ¬A(x) = 1 − 0.7 = 0.3

Conclusion
• Fuzzy operations allow partial truth handling.
• They are fundamental for fuzzy inference and decision-making systems.
• Union, intersection, and complement extend classical logic to uncertain
environments.
What do you mean by conflict resolution strategy?
Conflict Resolution Strategy
Definition:
• A conflict resolution strategy is a method used in a production system to select one
rule for execution when multiple rules are applicable at the same time.
• It resolves conflicts among competing rules in the conflict set.
Purpose:
• To decide which rule should fire next.
• To control the order of rule execution.
• To improve efficiency and correctness of problem solving.

Common Conflict Resolution Strategies:

• Priority: Rules with higher priority are selected first.
• Specificity: More specific rules are preferred over general ones.
• Recency: Rules using recently added facts are selected.
• Rule ordering: Rules are applied in a predefined order.

Conclusion:
• Conflict resolution strategy is essential for effective control in rule-based AI systems.
• It ensures deterministic and efficient reasoning.

What do you mean by Skolem Constant and Skolem Function?

Skolem Constant
Definition:
• A Skolem constant is a special constant introduced to eliminate an existentially
quantified variable when it is not dependent on any universal variable.
• It represents an unknown but fixed object.
Example:
∃x Human(x)
After Skolemisation:
Human(a)
(where a is a Skolem constant)
Skolem Function
Definition:
• A Skolem function is introduced to eliminate an existentially quantified variable
that depends on one or more universal variables.
• The function arguments are the universally quantified variables.
Example:
∀x ∃y Loves(x, y)
After Skolemisation:
Loves(x, f(x))
(where f(x) is a Skolem function)
Conclusion
• Skolem constants and functions are used in Skolemisation to remove existential
quantifiers.
• They preserve satisfiability and are essential for converting formulas into clause
form for resolution.
Explain Inductive Learning.
Inductive Learning
Definition:
• Inductive learning is a learning method in Artificial Intelligence in which general rules
or concepts are derived from specific examples.
• It follows a bottom-up approach, moving from observations to generalization.

Working Principle:
1. The system is given a set of training examples.
2. Each example consists of input data and corresponding output.
3. The learner identifies patterns and regularities in the data.
4. A general hypothesis or rule is formed.
5. The learned rule is used to predict outcomes for new unseen examples.
Characteristics:
• Learns from experience.
• Improves performance over time.
• Supports generalization.
• Does not require prior domain theory.

Advantages:
 • Useful when explicit knowledge is unavailable.
• Adaptable to new data.
• Simple and effective for many AI applications.
Limitations:
• May generate incorrect generalizations.
• Quality depends on training data.

Conclusion:
• Inductive learning is a fundamental AI learning technique.
• It enables systems to learn automatically from examples and is widely used in
classification and prediction tasks.
Explain Dependency Parsing in NLP.
Dependency Parsing in Natural Language Processing
Definition:
• Dependency parsing is a syntactic analysis technique in NLP that represents the
grammatical structure of a sentence by establishing dependency relationships
between words.
• Each relationship connects a head (governor) word with a dependent word.

Basic Concept:
• The sentence structure is represented as a dependency tree.
• Nodes represent words.
• Edges represent grammatical dependencies such as subject, object, modifier, etc.
• One word (usually the main verb) acts as the root.

Example:
Sentence: “The boy eats food”
• eats → root
• boy → subject of eats
• food → object of eats
• The → modifier of boy

Features of Dependency Parsing:

• Focuses on word-to-word relations, not phrase structure.
• Suitable for free-word-order languages.
• Produces compact and meaningful syntactic representation.

Applications:
• Machine translation
• Information extraction
• Question answering
• Text understanding

Conclusion:
• Dependency parsing provides a clear representation of syntactic dependencies in a
sentence.
• It is a key technique for deep language understanding in NLP.

State the advantages of partial parsers over parsers that provide in-depth syntatic
information.
Advantages of Partial Parsers
Partial parsers (also called shallow parsers or chunkers) analyze only important syntactic
units rather than full parse trees.
1. Faster Processing
• Partial parsers require less computation time.
• Suitable for large text corpora and real-time applications.

2. Robustness
• They can work even when sentences are grammatically incorrect or incomplete.
• Less sensitive to parsing failures.

3. Lower Complexity
 • Avoids detailed syntactic structures.
• Easier to implement and maintain than full parsers.
4. Practical for NLP Applications
• Effective for tasks like:
o Information extraction
o Named entity recognition
o Text classification

5. Reduced Resource Requirement

• Requires less memory and linguistic knowledge compared to deep parsers.

Conclusion
• Partial parsers trade detailed syntactic accuracy for speed, robustness, and
efficiency.
• They are preferred in many practical NLP systems where full parsing is unnecessary.

What are some ways we can preprocess text input?

Text Preprocessing Techniques in NLP
Text preprocessing is the process of cleaning and transforming raw text into a suitable form
for further analysis.
1. Tokenization
• Splitting text into tokens such as words or sentences.
• Example:
“AI is powerful” → [AI, is, powerful]
2. Case Normalization
• Converting all text to lowercase to avoid duplication.
• Example:
“AI” and “ai” treated as same.
3. Stop Word Removal
• Removing commonly used words with little meaning.
• Example: is, the, and, of

4. Stemming
• Reducing words to their root form.
• Example:
playing, played → play
5. Lemmatization
• Converting words to their dictionary base form.
• More accurate than stemming.
• Example:
better → good
6. Removal of Punctuation and Special Characters
• Eliminating symbols like commas, periods, hashtags, etc.

Conclusion
• Text preprocessing improves accuracy, efficiency, and performance of NLP systems.
• It is an essential step before parsing, learning, or semantic analysis.

Explain the cycle of Genetic Algoritghm.

Cycle of Genetic Algorithm (GA)
A Genetic Algorithm works by simulating the process of natural evolution to find optimal or
near-optimal solutions.
1. Initialization
• Generate an initial population of chromosomes randomly.
• Each chromosome represents a candidate solution.

2. Fitness Evaluation
• Evaluate each chromosome using a fitness function.
 • Fitness indicates how good a solution is with respect to the problem.
3. Selection
• Select parent chromosomes based on fitness value.
• Fitter individuals have a higher chance of selection.
• Common methods: roulette wheel selection, tournament selection.

4. Crossover (Recombination)
• Exchange genetic material between selected parents.
• Produces new offspring with combined characteristics.
• Helps explore new regions of the search space.

5. Mutation
• Randomly alter genes in offspring with low probability.
• Maintains genetic diversity and avoids premature convergence.

6. Replacement
• Form a new population by replacing old chromosomes with offspring.
• The cycle repeats until a termination condition is met.

Termination Condition
• Maximum number of generations reached, or
• Desired fitness level achieved.

Conclusion
• The GA cycle iteratively improves solutions through selection, crossover, and
mutation.
• It is effective for solving complex optimization and search problems.

Discuss different types of crossover techniques.

Crossover Techniques in Genetic Algorithms
Crossover is a genetic operator used to combine genetic material of two parent
chromosomes to produce new offspring.
1. Single-Point Crossover
• A single crossover point is selected.
• Portions of parents after the point are exchanged.
Example:
Parent1: 110|010
Parent2: 001|111
Offspring: 110111, 001010
2. Two-Point Crossover
• Two crossover points are selected.
• The segment between the points is exchanged.
Advantage:
• Produces more variation than single-point crossover.

3. Multi-Point Crossover
• More than two crossover points are used.
• Alternate segments are swapped between parents.

4. Uniform Crossover
• Each gene is independently chosen from either parent.
• Uses a fixed probability or mask.
Advantage:
• High diversity in offspring.

5. Arithmetic Crossover
• Used for real-valued chromosomes.
• Offspring are generated using weighted averages of parents.

Conclusion
• Different crossover techniques balance exploration and exploitation.
• Choice of crossover method affects convergence speed and solution quality.
 • Crossover is essential for generating new and improved solutions in Genetic
Algorithms.
What is expert system? Why is it required?
Expert System
Definition:
• An expert system is an Artificial Intelligence system that emulates the decision-
making ability of a human expert in a specific domain.
• It uses domain knowledge and inference rules to solve complex problems.

Components (Brief):
• Knowledge Base: Stores facts and rules.
• Inference Engine: Applies rules to derive conclusions.
• User Interface: Allows interaction with users.

Why Expert Systems are Required

1. Scarcity of Human Experts
• Human experts may not always be available.
• Expert systems provide expert-level advice anytime.
2. Consistency in Decision Making
• Produces uniform and reliable decisions, unlike humans who may vary.
3. Handling Complex Problems
• Can process large amounts of knowledge quickly.
• Useful in diagnosis, planning, and decision support.
4. Cost and Time Efficiency
• Reduces cost of consulting experts.
• Provides quick solutions.
5. Knowledge Preservation
• Captures and preserves expert knowledge for future use.

Conclusion
• Expert systems are required to replicate expert knowledge, ensure consistency, and
support decision making.
• They play a crucial role in domains where expertise is critical and scarce.

What is expert system shell?

Expert System Shell:
• An expert system shell is a software framework that provides the inference engine,
control strategy, and user interface for building expert systems.
• It does not contain domain-specific knowledge; the knowledge base must be added
separately.
Conclusion:
An expert system shell simplifies expert system development by separating knowledge from
reasoning mechanism.
What do you mean by knowledge acquisition?
Knowledge Acquisition
Definition:
• Knowledge acquisition is the process of gathering, extracting, and organizing
knowledge from various sources for use in an AI system or expert system.
Sources of Knowledge:
• Human experts
• Books and documents
• Databases
• Observations and experience

Importance:
• Essential for building an accurate knowledge base.
• Directly affects the performance and reliability of expert systems.

Conclusion:
• Knowledge acquisition converts human expertise into a machine-usable form.
• It is a critical step in the development of knowledge-based AI systems.
Discuss the problem characteristics in Artificial Intelligence.
Problem Characteristics in AI
Problem characteristics describe the nature of a problem and help in choosing an
appropriate solution method.
1. Decomposability
o Whether the problem can be divided into independent sub-problems.
2. Deterministic vs Non-deterministic
o Deterministic problems have predictable outcomes.
o Non-deterministic problems involve uncertainty.
3. Static vs Dynamic
o Static problems do not change during problem solving.
o Dynamic problems change with time.
4. Discrete vs Continuous
o Discrete problems have finite states and actions.
o Continuous problems have infinite possibilities.
5. Single-agent vs Multi-agent
o Problems may involve one agent or multiple interacting agents.
Conclusion:
Understanding problem characteristics helps in selecting suitable search and reasoning
techniques.
Explain the search program design issues.
Search Program Design Issues
Search program design issues arise while constructing an efficient search algorithm.
1. State Representation
o How states are defined and stored affects performance.
2. Search Space Size
o Large state spaces cause combinatorial explosion.
3. Choice of Search Strategy
o BFS, DFS, A*, etc., depending on optimality and resources.
4. Handling Repeated States
o Avoid revisiting states to reduce redundancy.
5. Termination Condition
o Ensuring search stops at goal or failure appropriately.
Conclusion:
Proper handling of design issues ensures efficient and correct problem solving.
What is memory-bounded heuristic search?
Memory-Bounded Heuristic Search
Definition:
• Memory-bounded heuristic search refers to search algorithms that use heuristic
guidance while limiting memory usage.
Key Features:
• Uses heuristic information like A*.
• Operates under fixed memory constraints.
• Discards less promising nodes when memory is full.
Examples:
• Iterative Deepening A* (IDA*)
• Recursive Best-First Search (RBFS)
Advantages:
• Suitable for large search spaces.
• Prevents memory overflow.
Conclusion:
Memory-bounded heuristic search balances optimality, efficiency, and memory usage.
Explain functions and predicates in Predicate Logic.
Functions and Predicates in Predicate Logic
Predicate:
• Represents a property or relation among objects.
• Returns true or false.
Example:
Man(x), Loves(x, y)
Function:
 • Represents a mapping from objects to objects.
• Returns a value, not a truth value.
Example:
Father(x), Age(x)
Difference:
• Predicate → truth value
• Function → object/value
Conclusion:
Functions and predicates enhance the expressive power of predicate logic.
List and explain the forms of learning in Artificial Intelligence.
Forms of Learning in AI
1. Inductive Learning
o Learns general rules from examples.
2. Explanation-Based Learning (EBL)
o Learns by analyzing explanations of examples.
3. Learning using Relevance Information
o Focuses on relevant attributes only.
4. Neural Network Learning
o Learns by adjusting weights in neural networks.
5. Genetic Learning
o Uses evolutionary principles like mutation and crossover.
Conclusion:
Different learning forms enable AI systems to adapt and improve performance.
1. Uniform Cost Search (UCS) Algorithm
Algorithm: Uniform Cost Search
1. Insert the initial node into the priority queue with cost 0.
2. Repeat until queue is empty:
o Remove the node with lowest path cost.
3. If the removed node is the goal state, return solution.
4. Expand the node and generate successors.
5. For each successor:
o Calculate cumulative path cost.
o Insert into priority queue if not explored or lower cost found.
6. If queue becomes empty, return failure.
2. Production System Control Strategy Algorithm
Algorithm: Production System Execution
1. Initialize working memory with initial facts.
2. Match production rules whose conditions are satisfied.
3. Place matched rules into conflict set.
4. Apply conflict resolution strategy to select a rule.
5. Fire the selected rule.
6. Update working memory.
7. Repeat steps 2–6 until goal is achieved or no rule is applicable.
3. Search Space Reduction Algorithm
Algorithm: Search Space Reduction
1. Represent the problem in state space form.
2. Identify redundant or repeated states.
3. Apply constraints or heuristics to prune states.
4. Avoid revisiting explored states.
5. Expand only promising states.
6. Continue until goal is found or no states remain.
4. Iterative Deepening A* (IDA*) Algorithm
Algorithm: IDA*
1. Set initial threshold = h(start).
2. Perform depth-first search using f(n)=g(n)+h(n).
3. If f(n) > threshold, prune the node.
4. If goal is found, return solution.
5. Set new threshold to minimum f(n) that exceeded previous threshold.
6. Repeat steps 2–5 until solution is found.
5. Recursive Best-First Search (RBFS) Algorithm
Algorithm: RBFS
1. Start from initial node with f(n)=g(n)+h(n).
2. Expand the best node recursively.
3. Keep track of alternative best f-value.
4. If best node’s f-value exceeds limit, backtrack.
5. Update f-values during backtracking.
6. Continue until goal is reached or failure occurs.
6. Backtracking Algorithm for CSP
Algorithm: Backtracking CSP
1. Assign a value to an unassigned variable.
2. Check consistency with constraints.
3. If consistent, proceed to next variable.
4. If inconsistent, remove assignment (backtrack).
5. Repeat until all variables are assigned.
6. If no assignment possible, return failure.
7. Forward Checking Algorithm
Algorithm: Forward Checking
1. Assign value to a variable.
2. Remove inconsistent values from future variables’ domains.
3. If any domain becomes empty, backtrack.
4. Continue assigning remaining variables.
5. Stop when all variables are assigned consistently.
8. Constraint Propagation (AC-3 Algorithm)
Algorithm: AC-3
1. Place all arcs into a queue.
2. While queue is not empty:
o Remove an arc (Xi, Xj).
3. Revise domain of Xi.
4. If domain of Xi changes:
o Add all neighboring arcs back to queue.
5. Continue until queue is empty or domain becomes empty.
9. Game Tree Construction Algorithm
Algorithm: Game Tree Construction
1. Represent initial game state as root.
2. Generate all legal moves for current player.
3. Create child nodes for each move.
4. Alternate players at each level.
5. Continue expansion until terminal states are reached.
6. Assign utility values to terminal nodes.
10. AO* Algorithm
Algorithm: AO*
1. Start with initial node as an AND-OR graph.
2. Expand the most promising node.
3. Compute cost of AND and OR nodes.
4. Update heuristic estimates.
5. Mark the best partial solution graph.
6. Repeat until goal node is solved.
11. Decision Tree Learning Algorithm
Algorithm: Decision Tree Construction
1. Select the best attribute using information gain.
2. Create a decision node for the attribute.
3. Split dataset based on attribute values.
4. Recursively repeat for each subset.
5. Stop when all examples belong to one class or attributes exhausted.
12. Neural Network Learning Algorithm
Algorithm: Neural Network Training
1. Initialize weights randomly.
2. Input training data into network.
3. Compute output using forward propagation.
4. Calculate error between actual and expected output.
5. Update weights using error correction.
 6. Repeat until error is minimized.
13. Inference Engine Algorithm (Forward / Backward Chaining)
Algorithm: Forward Chaining
1. Start with known facts.
2. Match rules whose premises are satisfied.
3. Fire rule and add conclusion to facts.
4. Repeat until goal is reached or no rule applies.
Algorithm: Backward Chaining
1. Start with goal.
2. Find rules that can conclude the goal.
3. Check if premises are true.
4. Recursively prove premises.
5. Continue until goal is proved or fails.