Nice — I’ll treat each item as a 10-mark exam answer: definition, how it works, complexity/

properties, an example, and strengths/weaknesses. I’ll keep each focused and exam-ready.

Breadth-First Search (BFS)

Definition & idea: BFS explores a state-space level by level from the start node, expanding
all nodes at depth d before any at d+1.
Algorithm: Use a FIFO queue. Enqueue start, then repeatedly dequeue a node, test goal, and
enqueue its unvisited successors.
Complexity & properties: Time and space are both O(b^d) where b is branching factor and
d is depth of the shallowest goal. BFS is complete (will find a solution if one exists) and
optimal when step costs are uniform.
Example: Shortest path on an unweighted graph (social network friend hops).
Strengths/weaknesses: Simple and guaranteed optimal for uniform costs; but memory heavy
(stores entire frontier), so impractical if b^d is huge.

Depth-First Search (DFS)

Definition & idea: DFS explores as deep as possible along a branch before backtracking.
Implemented recursively or with a stack.
Algorithm: Push start node; repeatedly pop, visit, and push successors (typically in reverse
order to preserve order).
Complexity & properties: Time O(b^m) where m is maximum depth; space O(bm) (linear in
depth). Not guaranteed to find shortest path; may not terminate on infinite paths unless cycle
checking used. DFS is memory-efficient.
Example: Solving mazes or exploring game trees to a fixed depth.
Strengths/weaknesses: Low memory, useful for deep solutions; but can get stuck in deep/
infinite branches and is not optimal.

Iterative Deepening Search (IDS / IDDFS)

Definition & idea: Repeated depth-limited DFS with increasing depth limits (0,1,2,…),
combining BFS’s completeness and DFS’s low memory.
Algorithm: For depth k = 0..∞, run DFS limited to depth k. Stop when goal found.
Complexity & properties: Time is O(b^d) (overhead is a small constant factor compared
with BFS). Space O(bd). Complete and optimal for uniform costs.
Example: Common search strategy in game playing when depth of solution unknown.
Strengths/weaknesses: Best of BFS and DFS tradeoffs for large branching factors; repeated
work causes modest overhead.

Greedy Best-First Search

Definition & idea: Informed search using a heuristic h(n) that estimates closeness to goal.
Always expand the node with smallest h(n) (most promising).
Algorithm: Maintain a priority queue ordered by h(n). Expand lowest h.
Complexity & properties: Time/space can be exponential depending on heuristic quality.
Not guaranteed complete in infinite spaces; not optimal (can follow misleading heuristics).
Example: Route-finding using straight-line distance to target as h.
Strengths/weaknesses: Fast when heuristic is good; can be very misguided and miss optimal
solutions.

A* Search
Definition & idea: Informed, best-first search using f(n)=g(n)+h(n) where g(n) is cost so
far and h(n) is estimated remaining cost.
Algorithm: Priority queue ordered by f(n). Pop lowest f, expand, update costs, maintain
closed set to avoid reprocessing.
Complexity & properties: If h is admissible (never overestimates) A* is optimal. If h is
consistent (monotone), no reopened nodes are needed. Worst-case time and space are
exponential but performance depends strongly on heuristic accuracy.
Example: Shortest path with travel times; h could be straight-line distance.
Strengths/weaknesses: Optimal and often efficient with strong heuristics; memory usage can
be prohibitive (stores frontier and explored).

Heuristics and Optimization (design &

properties)
Definition & idea: Heuristics are functions estimating cost to goal; used to guide search/
optimization. Optimization concerns finding maxima/minima of objective functions.
Types & design methods: Admissible/consistent heuristics, relaxed-problem heuristics (drop
constraints), pattern databases (precomputed exact costs for subproblems), landmark
heuristics. Tradeoffs: more informed heuristics reduce search but cost more to
compute/memory.
Properties: Heuristics trade accuracy vs cost. In search, an admissible heuristic guarantees
optimality with A*. In optimization, surrogate or approximate objectives can speed search.
Example: For sliding-tile puzzle, pattern databases give perfect heuristics for subsets of tiles.
Strengths/weaknesses: Good heuristics yield huge speedups; poor heuristics may mislead
search or be expensive to compute.

Hill Climbing
Definition & idea: Local search that iteratively moves to a neighboring state with better
objective value until no improvement exists. Variants include steepest-ascent (choose best
neighbor) and stochastic hill climbing.
Algorithm: Start with initial state; evaluate neighbors; move to better neighbor; repeat until
local maxima (plateau) or no improvement.
Complexity & properties: Very fast, low memory. Not complete (can get stuck in local
maxima, plateaus, or ridges). Performance depends on neighborhood definition and restart
strategy.
Example: Tuning weights in a simple model by local tweaks.
Strengths/weaknesses: Simple and effective on smooth landscapes; fails on multimodal
landscapes without restarts or randomness.
Simulated Annealing
Definition & idea: Probabilistic local search that allows uphill moves with probability
exp(ΔE / T) to escape local maxima; temperature T decreases over time (annealing
schedule).
Algorithm: At each step pick a neighbor; if better, accept; if worse, accept with probability
depending on T. Decrease T according to schedule.
Complexity & properties: Can converge to global optimum with appropriate (often
impractically slow) cooling schedules. Robust to local maxima and plateaus. Performance
sensitive to temperature schedule and neighbor selection.
Example: Traveling Salesman Problem variants; VLSI placement.
Strengths/weaknesses: Good at escaping local optima; needs careful tuning and can be slow.

Constraint Satisfaction Problems (CSPs)

Definition & idea: Problems defined by variables, domains, and constraints (relations among
variables). Goal: assignment of values satisfying all constraints.
Common techniques: Backtracking search, variable ordering heuristics (MRV — minimum
remaining values), value ordering (least-constraining value), constraint propagation (forward
checking, MAC/AC-3 arc consistency), and decomposition (tree clustering).
Complexity & properties: General CSPs are NP-complete. Practical performance heavily
improved by heuristics and inference. Binary CSPs and special structures (trees) can be
solved in polynomial time.
Example: Map coloring, Sudoku, scheduling.
Strengths/weaknesses: CSP framework modularizes many problems; performance depends
on constraint tightness and topology.

Game Playing: Min-Max

Definition & idea: Deterministic, perfect-information, two-player zero-sum games are
solved by minimax: maximizing utility for current player while assuming opponent
minimizes it.
Algorithm: Recursively evaluate game tree to terminal nodes; propagate values up: max for
player, min for opponent. With depth limits use evaluation functions at leaf nodes.
Complexity & properties: Time O(b^d), space O(bd) for depth-first minimax. Guarantees
optimal play given full tree. In practice depth limits and heuristic evaluation are used.
Example: Tic-Tac-Toe solved by minimax; chess uses it with pruning and heuristics.
Strengths/weaknesses: Conceptually simple and optimal; computationally expensive for
large games.

Alpha-Beta Pruning
Definition & idea: Optimization of minimax that prunes branches that cannot affect final
decision using two bounds α (best for maximizer) and β (best for minimizer).
Algorithm: During depth-first tree traversal maintain α,β; prune subtree when α ≥ β. With
good move ordering, reduces time significantly.
Complexity & properties: Best-case time O(b^(d/2)) (effective square-root reduction);
worst case O(b^d). Produces the same result as minimax but much faster with good ordering.
Example: Chess engines use α-β with iterative deepening and move ordering heuristics.
Strengths/weaknesses: Massive performance gains possible; effectiveness depends on move
ordering (best moves first yields best pruning).

Stochastic & Partially Observable Games

Definitions:

 Stochastic games: include chance nodes (random events) in the game tree (e.g., dice
rolls). Expectimax replaces minimax at chance nodes by expected value.
 Partially observable games: players have incomplete information about the game
state (e.g., poker). Agents maintain belief states (probability distributions) or use
sampling.
Algorithms & approaches:
 Use expectimax for stochastic, computing expected utilities at chance nodes.
 For partial observability use belief-state MDPs / POMDPs or information-set search:
treat nodes with identical observations as one information set (game-theoretic
approaches). Monte-Carlo methods and belief sampling (e.g., Monte Carlo Tree
Search with determinization or particle filters) are common.
Complexity & properties: Much harder than deterministic perfect-info games.
Optimal solutions often intractable; approximate/heuristic methods used.
Examples: Backgammon (stochastic), Poker (stochastic + partially observable).
Strengths/weaknesses: Models real games with chance and hidden info;
computationally heavy, requires probabilistic reasoning and strong approximations.

Got it — I’ll give you clear, exam-oriented 10-mark answers for each topic, but I’ll keep
them structured and concise so they’re easy to revise.
(If you want, next we can turn these into 1–2 page exam notes or Q&A practice.)

Knowledge Representation & Reasoning

1. Propositional Logic (PL)
Definition
Propositional Logic represents knowledge using propositions that are either true or false.

Syntax

 Propositional symbols: P, Q, R
 Logical connectives:
o ¬ (NOT), ∧ (AND), ∨ (OR), → (IMPLIES), ↔ (IFF)
 Sentences are built using formation rules.
Semantics

 Meaning defined by truth assignments

 Truth tables determine validity and satisfiability.

Inference

 Modus Ponens
 Modus Tollens
 Resolution
 Truth-table checking

Advantages

 Simple, decidable, efficient inference.

Limitations

 Cannot represent objects, relations, or quantifiers.

2. First Order Logic (FOL)

Definition
FOL extends propositional logic by introducing objects, predicates, variables, and
quantifiers.

Syntax

 Constants: a, John
 Variables: x, y
 Predicates: Human(x), Likes(x,y)
 Quantifiers:
o ∀ (for all)
o ∃ (exists)

Semantics

 Based on a domain of discourse and interpretations.

 Truth depends on relationships among objects.

Inference

 Universal / Existential instantiation

 Unification
 Resolution for FOL
Example
∀x (Human(x) → Mortal(x))

Advantages

 Very expressive, close to natural language.

Limitations

 Inference is computationally expensive and semi-decidable.

3. Syntax, Semantics, and Inference

Syntax
Defines the structure of valid sentences.

Semantics
Defines the meaning of sentences using models.

Inference
Deriving new sentences that are logically entailed by existing knowledge.

Important Properties

 Soundness: Only true conclusions are derived

 Completeness: All true conclusions can be derived

Role in AI
Ensures agents reason correctly and meaningfully.

4. Knowledge-Based Agents
Definition
Agents that store knowledge in a Knowledge Base (KB) and use reasoning to decide actions.

Components

 Knowledge Base
 Inference Engine
 Sensors & Actuators

Working

1. Perceive environment
2. Update KB
 3. Infer new facts
4. Select actions

Advantages

 Flexible, explainable behavior

 Can reason about unseen situations

5. Wumpus World
Description
A classic AI environment used to demonstrate logical reasoning under uncertainty.

Environment

 Grid world
 Hazards: Wumpus, pits
 Percepts: Breeze, Stench, Glitter

Agent Goals

 Find gold
 Avoid hazards
 Exit safely

Representation

 Uses propositional or first-order logic

 Inference to deduce safe/unsafe squares

Significance
Demonstrates knowledge-based reasoning, not reflex actions.

6. Logic Programming using Prolog

Definition
Prolog is a logic programming language based on facts, rules, and queries.

Basic Elements

 Facts: parent(john, mary).

 Rules: grandparent(X,Y):- parent(X,Z), parent(Z,Y).
 Queries: ?- grandparent(john, Y).

Execution Model
  Backward chaining
 Depth-first search
 Unification

Advantages

 Declarative, concise
 Built-in inference

Limitations

 Performance issues for large KBs

 Limited control over execution order

7. Forward and Backward Chaining

Forward Chaining

 Data-driven reasoning
 Starts from known facts
 Applies rules to infer new facts
 Used in expert systems

Backward Chaining

 Goal-driven reasoning
 Starts with a query
 Works backward to find supporting facts
 Used in Prolog

Comparison

Forward Backward

Fact-driven Goal-driven

Many inferences Focused search

8. Resolution
Definition
A single, powerful inference rule used for automated theorem proving.

Steps
 1. Convert sentences to Clause Normal Form (CNF)
2. Apply resolution rule
3. Derive empty clause (⊥) → contradiction

Key Feature

 Sound and complete for propositional logic

 Works with unification in FOL

Importance
Foundation of many automated reasoning systems.

9. Ontological Engineering and Reasoning

Ontology
A formal specification of concepts, relationships, and constraints in a domain.

Components

 Classes (Concepts)
 Properties (Relations)
 Instances (Individuals)
 Axioms (Rules)

Ontology Languages

 RDF
 OWL
 Description Logics

Reasoning Tasks

 Consistency checking
 Classification
 Subsumption

Applications

 Semantic Web
 Medical diagnosis
 Knowledge graphs

🔑 Exam Tip (Mnemonic)

“L-SIR-K-W-P-FBR-O”
Logic → Syntax → Inference → Reasoning → Knowledge agents → Wumpus → Prolog →
Forward/Backward → Resolution → Ontology