Artificial Intelligence

& Expert
Complete Systems
Guide — Theory + Math + Examples

Intro to AI • Intelligent Agents • Search (BFS/DFS/A*) • Knowledge Representation

Expert Systems • Planning • Machine Learning • Neural Networks
NLP • Fuzzy Logic • Genetic Algorithm • Master Reference

Full answers to every Exam / Viva / Interview question

Designed for: CSE Fresher • Lecturer Written Exam • Viva • Interview
 Table of Contents
Chapter 1 — Introduction to Artificial Intelligence
What is AI?
History & Milestones
Turing Test
Types of AI
AI Applications
Intelligent vs Non-intelligent Systems
Chapter 2 — Intelligent Agents
What is an Agent?
PEAS Framework
Types of Agents
Environment Types
Rationality
Chapter 3 — Search Algorithms
Problem Formulation
Uninformed Search: BFS (traced), DFS (traced), UCS
Informed Search: Greedy, A* (with h values, full trace)
Heuristics & Admissibility
Hill Climbing, Simulated Annealing
Chapter 4 — Knowledge Representation
Propositional Logic
Predicate Logic (FOL)
Inference Rules (Modus Ponens, Resolution)
Semantic Networks
Frames
Ontologies
Chapter 5 — Expert Systems
Architecture of Expert System
Knowledge Base
Inference Engine (Forward & Backward Chaining)
Explanation Facility
Knowledge Acquisition
Advantages & Limitations
MYCIN, DENDRAL examples
Chapter 6 — Planning & Problem Solving
State Space Representation
8-Puzzle Problem
Water Jug Problem
STRIPS Planning
Means-Ends Analysis
Chapter 7 — Machine Learning
ML Types: Supervised, Unsupervised, Reinforcement
Decision Tree (ID3 Algorithm, Entropy, Info Gain — full calculation)
K-Nearest Neighbor
Naive Bayes
Overfitting & Regularization
Evaluation Metrics
Chapter 8 — Neural Networks & Deep Learning
Biological vs Artificial Neuron
Perceptron Model & Learning Rule (calculation)
Multilayer Perceptron & Backpropagation
Activation Functions
CNN, RNN basics
Deep Learning overview
Chapter 9 — Natural Language Processing
NLP Tasks & Pipeline
Tokenization, POS Tagging, Parsing
N-gram Language Models
Named Entity Recognition
Word Embeddings (Word2Vec)
Sentiment Analysis
Chapter 10 — Fuzzy Logic & Genetic Algorithm
Crisp vs Fuzzy Sets
Membership Functions (examples)
Fuzzy Operations
Defuzzification
Genetic Algorithm: Chromosome, Crossover, Mutation (traced example)
Chapter 11 — Master Reference
All search algorithms comparison
ML algorithms comparison
Key formulas
Quick concept table
 CHAPTER 1

Introduction to Artificial Intelligence

What is AI, history, and goals

1.1 What is Artificial Intelligence?

Artificial Intelligence (AI) is the science and engineering of making machines that can perform tasks that would
normally require human intelligence — such as reasoning, learning, problem-solving, understanding natural
language, and perceiving the environment.

AI can be defined from four perspectives:

Perspective Definition Focus

Thinking Humanly Systems that think like humans Cognitive modeling approach

Acting Humanly Systems that act like humans Turing Test approach

Thinking Rationally Systems that think logically/rationally Laws of thought approach

Systems that act to achieve best Rational agent approach (modern

Acting Rationally outcomes AI)

1.2 History & Milestones

Year Milestone

1943 McCulloch & Pitts — first mathematical model of a neuron

1950 Alan Turing proposes the Turing Test

1956 Dartmouth Conference — term "Artificial Intelligence" coined (John McCarthy)

1957 Perceptron invented by Rosenblatt

1965 DENDRAL — first expert system developed

1972 PROLOG programming language for logic

1980s Expert Systems boom; Knowledge Engineering era

1997 Deep Blue (IBM) beats world chess champion Garry Kasparov

2011 IBM Watson wins Jeopardy!

2012 Deep Learning breakthrough — AlexNet wins ImageNet

2016 AlphaGo beats world Go champion

2022 ChatGPT — Large Language Models go mainstream

1.3 The Turing Test

Proposed by Alan Turing in 1950 in his paper "Computing Machinery and Intelligence." A human interrogator
communicates (via text) with a human and a machine. If the interrogator cannot reliably tell which is the
machine, the machine is said to have passed the Turing Test — demonstrating intelligent behavior
indistinguishable from a human.

Capabilities needed to pass: Natural Language Processing (to communicate), Knowledge Representation (to
store information), Automated Reasoning (to answer questions), Machine Learning (to adapt and generalize).
The Total Turing Test also includes Computer Vision and Robotics.

Criticism: passing the Turing Test does not mean the machine truly "understands" — it may just simulate. John
Searle's "Chinese Room" argument illustrates this: a person following rules to manipulate Chinese symbols
produces correct output without understanding Chinese.

1.4 Types of AI
Classification Types Description

AI designed for one specific task. Current AI. Examples:

By Capability Narrow AI (Weak AI) chess engine, face recognition, Siri.

AI with human-level intelligence across all tasks. Does

By Capability General AI (Strong AI) not exist yet.

AI surpassing human intelligence in all domains.

By Capability Super AI Theoretical/future.

No memory, reacts to current input only. Example: Deep

By Functionality Reactive Machines Blue.

Uses past data to make decisions. Example: self-driving

By Functionality Limited Memory cars.

By Functionality Theory of Mind Understands human emotions/beliefs. Research stage.

By Functionality Self-Aware AI Has consciousness. Does not exist.

Exam / Viva / Interview — Questions & Answers

■ Q: What is Artificial Intelligence? Give four definitions.

Ans:

AI is the science of making machines perform tasks requiring human intelligence. Four definitions: (1) Thinking Humanly
— systems that model human cognitive processes. (2) Acting Humanly — systems that behave like humans (Turing
Test). (3) Thinking Rationally — systems that reason using logical rules. (4) Acting Rationally — systems (rational
agents) that take actions to achieve best expected outcomes. Modern AI focuses on rational agents.

■ Q: What is the Turing Test? What are its limitations?

Ans:

Turing Test (1950): human interrogator chats via text with a human and a machine. If interrogator cannot distinguish
machine from human, machine is "intelligent." Tests: NLP, knowledge representation, reasoning, learning. Limitations:
(1) Chinese Room argument — machine may produce correct output without understanding. (2) Tests behavior not
intelligence. (3) Humans can fail their own test. (4) Narrow — text only. Despite limitations, it remains a landmark
concept in AI.

■ Q: What is the difference between Narrow AI and General AI?

Ans:
Narrow AI (Weak AI): designed for one specific task — cannot generalize beyond its domain. All current AI systems are
narrow AI. Examples: chess engine, image classifier, speech recognizer. General AI (Strong AI): human-level
intelligence across all domains — can reason, learn, and solve problems as broadly as humans. Does not exist yet.
Super AI: would surpass human intelligence. All AGI and Super AI remain theoretical.
 CHAPTER 2

Intelligent Agents
PEAS, Types of Agents, Environments

2.1 What is an Agent?

An agent is anything that perceives its environment through sensors and acts upon that environment through
actuators. A rational agent selects actions that maximize its expected performance measure, given its current
percepts and built-in knowledge.

• Percept: Input the agent receives from the environment at any given instant.
• Percept Sequence: Complete history of everything the agent has perceived.
• Agent Function: Maps percept sequence to action: f: P* -> A
• Agent Program: Concrete implementation of the agent function.

2.2 PEAS Framework

PEAS describes the task environment of an agent: Performance measure, Environment, Actuators, Sensors.

Performance
Agent Measure Environment Actuators Sensors

Safety, speed,
destination reached, Roads, traffic, Steering, accelerator, Cameras, GPS, lidar,
Self-driving car fuel efficiency pedestrians, signs brake, horn speedometer

Diagnoses, test
Medical diagnosis Accuracy, patient Patient data, test orders, treatment Symptom input, test
AI health, cost results, symptoms recommendations results, history

Chess board, Move selection on

Chess program Win/lose/draw opponent moves board Current board position

Web search Relevant results, Websites, user

engine speed queries Returned web pages User query text

2.3 Types of Agents (by Complexity)

Agent Type Decision Based On Example Limitation

Thermostat,
Current percept only simple robot Cannot handle partial
Simple Reflex (condition-action rules) vacuum observability

Current percept + internal Car with obstacle

Model-Based Reflex state model memory Model may be inaccurate

Current state + goal state Route planning No preference among

Goal-Based (search/planning) GPS goal-achieving paths

Self-driving car
Maximize utility function balancing Requires good utility
Utility-Based (not just reach goal) safety+speed function design
 AlphaGo,
Learns from experience to recommendation Requires training data and
Learning Agent improve performance systems time

2.4 Environment Types

Property Types Description & Example

Fully / Partially Fully: chess (see entire board). Partially: poker (hidden
Observability observable cards).

Single: crossword puzzle. Multi: chess (two agents),

Agents Single / Multi-agent traffic.

Deterministic / Deterministic: chess (next state fully determined).

Determinism Stochastic Stochastic: weather.

Episodic: image classification (each image independent).

Episodicity Episodic / Sequential Sequential: chess.

Static: crossword (board unchanged). Dynamic:

Dynamics Static / Dynamic self-driving car (changes while thinking).

Discrete: chess (finite moves). Continuous: robot arm

Continuity Discrete / Continuous (infinite positions).

Exam / Viva / Interview — Questions & Answers

■ Q: What is a rational agent? Explain PEAS with an example.

Ans:

A rational agent perceives its environment via sensors and acts via actuators to maximize its performance measure.
Rational = takes action with best expected outcome given percepts and knowledge. PEAS for self-driving car:
Performance = safety, speed, destination; Environment = roads, traffic, weather, pedestrians; Actuators = steering,
accelerator, brake; Sensors = cameras, GPS, lidar, radar.

■ Q: Compare the five types of agents.

Ans:

Simple Reflex: acts on current percept only (thermostat — if temp < set, heat on). Model-Based: maintains internal world
model (car tracking other vehicles). Goal-Based: searches for action sequences reaching goal (route planner).
Utility-Based: maximizes utility function balancing multiple goals (self-driving car balancing speed vs safety). Learning
Agent: improves from experience — has learning element, critic, performance element, and problem generator. Each
type is more capable but also more complex.
 CHAPTER 3

Search Algorithms
BFS, DFS, UCS, A* — Fully Traced

3.1 Problem Formulation

• Initial State: Starting state of the problem
• Actions: Possible actions available in each state
• Transition Model: Result(s, a) = next state after action a in state s
• Goal Test: Is the current state the goal?
• Path Cost: Numeric cost of each path
• Solution: Sequence of actions from initial to goal state

3.2 Uninformed (Blind) Search

Complete
Algorithm Data Structure ? Optimal? Time Space

Yes (unit
BFS Queue (FIFO) Yes cost) O(b^d) O(b^d)

DFS Stack (LIFO) No (infinite) No O(b^m) O(bm)

DLS
(Depth-Limited) Stack with limit No No O(b^l) O(bl)

Yes (unit
IDDFS Stack (repeated) Yes cost) O(b^d) O(bd)

Priority Queue (by

UCS cost) Yes Yes O(b^(C*/e)) O(b^(C*/e))

Note: b=branching factor, d=depth of shallowest goal, m=max depth, l=depth limit, C*=optimal cost, e=min edge cost

BFS — Breadth First Search (Traced)

Graph: A connects to B,C. B connects to D,E. C connects to F.

Goal: Find F. Start: A

Initial: Queue=[A], Visited={}

Step 1: Dequeue A. Visited={A}. Expand A -> enqueue B,C

Queue=[B,C]

Step 2: Dequeue B. Visited={A,B}. Expand B -> enqueue D,E

Queue=[C,D,E]
 Step 3: Dequeue C. Visited={A,B,C}. Expand C -> enqueue F

Queue=[D,E,F]

Step 4: Dequeue D. Visited={A,B,C,D}. D is not goal. No unvisited children.

Queue=[E,F]

Step 5: Dequeue E. Visited={A,B,C,D,E}. Not goal.

Queue=[F]

Step 6: Dequeue F. GOAL FOUND! Path: A->C->F

BFS guarantees shortest path (in terms of number of edges).

DFS — Depth First Search (Traced)

Same graph: A->B,C. B->D,E. C->F. Goal: F. Start: A

Initial: Stack=[A], Visited={}

Step 1: Pop A. Visited={A}. Push C,B (push right to left for left-first)

Stack=[C,B]

Step 2: Pop B. Visited={A,B}. Push E,D

Stack=[C,E,D]

Step 3: Pop D. Visited={A,B,D}. D has no children, not goal.

Stack=[C,E]

Step 4: Pop E. Visited={A,B,D,E}. Not goal.

Stack=[C]

Step 5: Pop C. Visited={A,B,D,E,C}. Push F.

Stack=[F]

Step 6: Pop F. GOAL FOUND! Path: A->C->F

DFS uses less memory O(bm) but may find non-optimal path.

May not terminate on infinite/cyclic graphs without visited check.

3.3 Informed (Heuristic) Search
Informed search uses problem-specific knowledge (heuristics) to guide search toward the goal more efficiently.
h(n) = estimated cost from node n to goal.

• Admissible heuristic: h(n) never overestimates actual cost. h(n) <= h*(n). Guarantees A* optimality.
• Consistent (monotone) heuristic: h(n) <= c(n,a,n') + h(n'). Triangle inequality. Consistent -> admissible.

A* Search — Full Traced Example

Problem: Find shortest path from S to G

Graph (node: edges with costs):

S -> A(1), S -> B(4)

A -> C(2), A -> B(1)

B -> C(1), B -> G(5)

C -> G(2)

Heuristic values h(n) (estimated distance to G):

h(S)=6, h(A)=4, h(B)=2, h(C)=1, h(G)=0

f(n) = g(n) + h(n) [g=actual cost so far, h=heuristic estimate]

Open list (priority queue by f), Closed list = {}

Step 1: Start with S. g(S)=0, h(S)=6, f(S)=6

Open: [(S, f=6)], Closed: {}

Step 2: Expand S (lowest f=6). Add to Closed.

Explore A: g(A)=0+1=1, h(A)=4, f(A)=5

Explore B: g(B)=0+4=4, h(B)=2, f(B)=6

Open: [(A,f=5),(B,f=6)], Closed: {S}

Step 3: Expand A (lowest f=5). Add to Closed.

Explore C: g(C)=1+2=3, h(C)=1, f(C)=4

Explore B via A: g(B)=1+1=2, f(B)=2+2=4 -> UPDATE B (was 6)

Open: [(B,f=4),(C,f=4)], Closed: {S,A}

Step 4: Expand B (f=4, tie-break). g(B)=2. Add to Closed.

 Explore C via B: g(C)=2+1=3, f=4 (same, no update)

Explore G: g(G)=2+5=7, h(G)=0, f(G)=7

Open: [(C,f=4),(G,f=7)], Closed: {S,A,B}

Step 5: Expand C (f=4). g(C)=3. Add to Closed.

Explore G via C: g(G)=3+2=5, f=5 -> UPDATE G (was 7)

Open: [(G,f=5)], Closed: {S,A,B,C}

Step 6: Expand G (f=5). GOAL FOUND!

Optimal path: S->A->B->C->G, Cost=5

h was admissible -> A* found optimal solution!

3.4 Local Search

Algorithm Strategy Complete? Optimal? Use Case

Hill Climbing Always move to best neighbor No (local optima) No Optimization problems

Accept worse moves with Yes (with slow Yes

Simulated Annealing decreasing probability cooling) (theoretically) Avoids local optima

Population-based evolutionary
Genetic Algorithm search No No Complex optimization

Exam / Viva / Interview — Questions & Answers

■ Q: What is the difference between BFS and DFS? When would you use each?

Ans:

BFS: explores level by level using a queue. Complete (always finds solution if one exists). Optimal for unit-cost edges.
Memory intensive O(b^d). Use when: solution is shallow, optimality needed. DFS: explores deep paths using a stack.
Not complete (may loop). Not optimal. Memory efficient O(bm). Use when: memory is limited, solution may be deep,
completeness not critical.

■ Q: What is A* search? What makes it optimal?

Ans:

A* search uses f(n) = g(n) + h(n) where g(n) = actual cost from start and h(n) = heuristic estimate to goal. Always
expands node with lowest f(n). Optimal and complete if heuristic is admissible (never overestimates). Admissibility
means h(n) <= h*(n) (true cost). A* is optimal among all informed search algorithms that use the same heuristic.

■ Q: What is an admissible heuristic? Give an example.

Ans:

Admissible heuristic: h(n) never overestimates the actual cost to reach the goal. h(n) <= h*(n) for all n. Example: For
8-puzzle problem, Manhattan distance (sum of distances each tile must move to its goal position) is admissible — it
never overestimates moves needed. Straight-line distance to goal in map routing is admissible — actual road distance is
always >= straight-line distance.
 CHAPTER 4

Knowledge Representation
Logic, Semantic Nets, Frames

4.1 What is Knowledge Representation?

Knowledge Representation (KR) is how AI systems store and organize knowledge about the world so that the
system can use it for reasoning, learning, and problem-solving. Good KR must be: representationally adequate
(can represent all needed knowledge), inferentially adequate (can derive new knowledge), efficient, and
compact.

4.2 Propositional Logic

Propositional logic deals with propositions (statements that are true or false) combined with logical connectives.

Connective Symbol Meaning Truth

NOT ¬ (tilde) Negation ¬P is true when P is false

AND ∧ Conjunction P∧Q true only when both true

OR ∨ Disjunction P∨Q true when at least one true

IMPLIES → Implication P→Q false only when P=T, Q=F

BICONDITIONAL ↔ Equivalence P↔Q true when both same value

4.3 First-Order Logic (Predicate Logic / FOL)

FOL extends propositional logic with predicates, terms, variables, and quantifiers — allowing more expressive
representation of the world.

Components:

Constants: specific objects (John, BUET, 3)

Variables: placeholders (x, y, z)

Predicates: properties/relations (Loves(x,y), IsStudent(x))

Functions: mappings (FatherOf(John), AgeOf(Mary))

Quantifiers:

Universal: forall x, P(x) -- "for all x, P(x) is true"

Existential: exists x, P(x) -- "there exists an x such that P(x)"

Examples:

"Every student likes some course"

 forall x, Student(x) -> exists y, Course(y) AND Likes(x,y)

"Rahim is a student at BUET"

Student(Rahim) AND AtUniversity(Rahim, BUET)

Inference Rules:

Modus Ponens: P, P->Q |- Q ("if P is true and P implies Q, then Q")

Modus Tollens: ¬Q, P->Q |- ¬P

Resolution: (P∨Q), (¬P∨R) |- (Q∨R)

4.4 Semantic Networks

A semantic network is a graph-based representation where nodes represent concepts/objects and edges
represent relationships between them. Supports inheritance through IS-A and HAS-A links.

Example: Animal knowledge base

Animal

|-- IS-A --> Mammal

| |-- IS-A --> Dog

| | |-- HAS-A --> Tail

| |-- IS-A --> Cat

|-- HAS-A --> Legs

|-- CAN --> Move

Inheritance: Dog inherits "HAS-A Legs" and "CAN Move" from Animal

through IS-A chain -- no need to restate for every subtype.

Properties:

Nodes = objects, concepts, events

Arcs = relationships (IS-A, HAS-A, CAN, INSTANCE-OF)

Supports default inheritance with exception handling

4.5 Frames
A frame is a data structure that represents a stereotyped situation. Each frame has slots (attributes) with values
(fillers). Frames support inheritance and default values — useful for representing complex objects and
situations.
 Frame: STUDENT

Name: [string]

Age: [integer, default: 20]

University: [University-frame, default: BUET]

Courses: [list of Course-frames]

GPA: [float, range: 0.0-4.0]

Frame: GRADUATE-STUDENT IS-A: STUDENT

Thesis: [string]

Advisor: [Faculty-frame]

(inherits all slots from STUDENT)

Advantages: Organized representation, default values, inheritance

Disadvantage: Rigid structure may not handle unexpected situations

Exam / Viva / Interview — Questions & Answers

■ Q: What is knowledge representation? Why is it important in AI?

Ans:

KR is how an AI system stores and organizes facts, rules, and relationships about the world. Important because: (1)
Enables reasoning — deriving new facts from existing knowledge. (2) Enables communication — share knowledge
between agents. (3) Enables learning — structure for incorporating new information. Good KR must be
representationally adequate, inferentially adequate, and efficient. Types: propositional logic, FOL, semantic networks,
frames, production rules.

■ Q: What is the difference between propositional logic and first-order logic?

Ans:

Propositional logic: deals with whole propositions (P, Q) combined with connectives (AND, OR, NOT, IMPLIES). Cannot
represent objects, properties, or relationships within propositions. Simple but limited. First-Order Logic (FOL/Predicate
logic): adds predicates (properties), constants (objects), variables, functions, and quantifiers (forall, exists). Much more
expressive — can say "All students at BUET pass the exam" as forall x, Student(x) AND At(x,BUET) -> Passes(x,exam).
FOL is the standard KR language for AI.

■ Q: What is a semantic network? What are its advantages?

Ans:

Semantic network: graph where nodes = objects/concepts and arcs = labeled relationships (IS-A, HAS-A, CAN).
Advantages: intuitive visual representation, supports inheritance (Dog inherits Animal properties through IS-A chain),
efficient for taxonomic knowledge, natural for associative memory. Disadvantages: difficult to represent quantifiers (all,
some), negation, and disjunction. No standard semantics. Best for hierarchical knowledge like biological taxonomies,
organizational charts.
 CHAPTER 5

Expert Systems
Architecture, Inference Engine, Examples

5.1 What is an Expert System?

An Expert System (ES) is an AI program that emulates the decision-making ability of a human expert in a
specific domain. It captures expert knowledge in a knowledge base and uses an inference engine to reason and
provide advice, diagnoses, or decisions.

Key characteristics: domain-specific, knowledge-intensive, can explain reasoning, handles uncertainty,

interactive with user, performs at expert level in its domain.

5.2 Architecture of an Expert System

Components:

1. KNOWLEDGE BASE

Contains domain knowledge in two forms:

a) Factual Knowledge: facts about the domain

Example: "Fever > 38.5C is high fever"

b) Heuristic Knowledge: rules of thumb from experts

Example: IF temperature > 38.5 AND cough = yes

THEN diagnosis = possible_flu

2. INFERENCE ENGINE

Applies reasoning to knowledge base to derive conclusions

Two strategies: Forward Chaining, Backward Chaining

3. WORKING MEMORY (Fact Base)

Stores current facts/assertions about the specific problem

Updated as inference proceeds

4. EXPLANATION FACILITY

Explains HOW a conclusion was reached (which rules fired)

Explains WHY a question is being asked

 Critical for user trust and verification

5. KNOWLEDGE ACQUISITION FACILITY

Interface for knowledge engineers to add/modify rules

6. USER INTERFACE

How the user interacts with the system (questions, answers)

5.3 Inference Engine — Forward vs Backward Chaining

Forward Chaining (Data-Driven)
Start from known facts, apply rules to derive new facts, continue until goal is reached or no more rules apply.
Works forward from data to conclusion.

Rules:

R1: IF fever AND cough THEN flu_possible

R2: IF flu_possible AND body_ache THEN flu_confirmed

R3: IF flu_confirmed THEN prescribe_antiviral

Known facts: fever=yes, cough=yes, body_ache=yes

Step 1: R1 fires (fever AND cough are known) -> assert flu_possible

Step 2: R2 fires (flu_possible AND body_ache known) -> assert flu_confirmed

Step 3: R3 fires (flu_confirmed known) -> prescribe_antiviral

Conclusion: Prescribe antiviral medication.

Used in: diagnostic systems, monitoring, planning

Backward Chaining (Goal-Driven)

Start from the goal, work backwards to find supporting facts. Ask: "What facts do I need to prove this goal?"
Efficient when goal is known. Used in PROLOG.

Goal: Prove "prescribe_antiviral"

Step 1: To prove prescribe_antiviral, need flu_confirmed (R3)

Step 2: To prove flu_confirmed, need flu_possible AND body_ache (R2)

body_ache -> ask user: "Do you have body ache?" -> YES
 Step 3: To prove flu_possible, need fever AND cough (R1)

fever -> ask user: "Do you have fever?" -> YES

cough -> ask user: "Do you have cough?" -> YES

Step 4: flu_possible proven! -> flu_confirmed proven! -> prescribe_antiviral!

Key: Only asked relevant questions, not all possible facts.

Used in: diagnostic systems (doctor narrows possibilities)

5.4 Famous Expert Systems

Expert System Domain Developer Key Feature

Certainty factors for

Medical diagnosis uncertainty, backward
MYCIN (bacterial infections) Stanford, 1970s chaining

Chemical structure
DENDRAL analysis Stanford, 1965 First expert system

Computer system Forward chaining, saved

XCON (R1) configuration DEC/CMU, 1978 $40M/year

Mineral deposit SRI International,

PROSPECTOR exploration 1970s Probabilistic reasoning

Still used today for

CLIPS General ES shell NASA, 1980s rule-based systems

5.5 Advantages & Limitations of Expert Systems

Advantages Limitations

Knowledge acquisition bottleneck (hard to extract

Available 24/7, never fatigued expert knowledge)

Consistent — same input gives same output Cannot learn or update automatically

Can explain reasoning (unlike neural nets) Narrow domain — breaks outside expertise

Handles complex problems in domain Cannot handle unexpected situations gracefully

Preserves rare expert knowledge Expensive and time-consuming to build

Can combine multiple experts' knowledge No common sense reasoning

Exam / Viva / Interview — Questions & Answers

■ Q: What is an expert system? Describe its architecture.

Ans:
 Expert system: AI program that captures human expert knowledge to solve domain-specific problems. Architecture: (1)
Knowledge Base — facts + IF-THEN rules. (2) Inference Engine — applies rules via forward/backward chaining. (3)
Working Memory — current problem facts. (4) Explanation Facility — explains how/why conclusions reached. (5)
Knowledge Acquisition Facility — interface to add/edit rules. (6) User Interface — interaction with user.

■ Q: What is the difference between forward and backward chaining?

Ans:

Forward chaining (data-driven): start with known facts, apply rules to derive new facts, continue until goal reached. Good
when: many possible goals, data is available upfront. Example: monitoring system detecting anomalies. Backward
chaining (goal-driven): start with goal, work back to find required facts. Good when: specific goal known, want to ask only
relevant questions. Used in PROLOG. Example: medical diagnosis — start with suspected disease, ask only relevant
questions.

■ Q: What is MYCIN? Why is it historically significant?

Ans:

MYCIN (Stanford, 1970s) is a medical expert system that diagnosed bacterial infections and recommended antibiotic
treatments. Significance: (1) First ES in medicine — demonstrated AI could match expert doctors. (2) Introduced
certainty factors for handling uncertainty (before probability theory was applied to AI). (3) Showed backward chaining for
diagnosis. (4) Its performance exceeded that of medical students and equaled specialists. (5) EMYCIN (Empty MYCIN)
became a reusable ES shell.
 CHAPTER 6

Planning & Problem Solving

State Space, 8-Puzzle, STRIPS

6.1 State Space Representation

A problem is represented as a state space: a set of all possible states, actions to move between states, initial
state, and goal state(s). Search algorithms explore this state space to find a solution (path from initial to goal).

6.2 8-Puzzle Problem

3x3 grid with 8 numbered tiles and 1 blank. Move blank to reach goal.

Initial State: Goal State:

2 8 3 1 2 3

1 6 4 8 4

7 5 7 6 5

State: configuration of tiles

Actions: move blank UP, DOWN, LEFT, RIGHT

Goal Test: current state = goal state

Path Cost: number of moves

Heuristics:

h1 = number of misplaced tiles (admissible)

h2 = Manhattan distance (sum of distances to goal) -- BETTER

For initial state above:

h1 = tiles 2,8,1,6 are misplaced = 4 tiles wrong

h2 = dist(2) + dist(8) + dist(1) + dist(6) + ...

= 1 + 3 + 1 + 2 + ... (calculate each tile distance to goal)

6.3 Water Jug Problem

Problem: 4-liter jug, 3-liter jug, unlimited water supply.
 Goal: Get exactly 2 liters in the 4-liter jug.

State: (x, y) where x=water in 4L jug, y=water in 3L jug

Initial: (0, 0)

Goal: (2, ?) -- 2 liters in 4L jug

Solution:

(0,0) -> Fill 4L: (4,0)

(4,0) -> Pour to 3L: (1,3)

(1,3) -> Empty 3L: (1,0)

(1,0) -> Pour 4L->3L: (0,1)

(0,1) -> Fill 4L: (4,1)

(4,1) -> Pour to 3L: (2,3) <- GOAL! (2 in 4L jug)

6.4 STRIPS Planning

STRIPS (Stanford Research Institute Problem Solver) is a formal planning language. Each action is defined
with: Preconditions (what must be true before), Add list (what becomes true after), Delete list (what becomes
false after).

Example: Robot moving blocks

Action: MOVE(block, from, to)

Preconditions: On(block, from), Clear(block), Clear(to)

Add list: On(block, to), Clear(from)

Delete list: On(block, from), Clear(to)

Initial state: On(A, Table), On(B, Table), On(C, A), Clear(B), Clear(C)

Goal: On(A, B)

Plan:

MOVE(C, A, Table): remove C from A -> A is now clear

MOVE(A, Table, B): place A on B -> On(A,B) achieved!

Exam / Viva / Interview — Questions & Answers

■ Q: What is state space search? Explain with the 8-puzzle example.

Ans:

State space search explores all possible configurations to find a path from initial to goal state. For 8-puzzle: State = tile
configuration (3x3 grid). Initial = given mixed arrangement. Actions = move blank UP/DOWN/LEFT/RIGHT. Goal = tiles
in order 1-8. Search algorithms (BFS, DFS, A*) explore states. A* with Manhattan distance heuristic is most efficient.
Manhattan distance = sum of each tile's distance to its goal position — admissible because tiles cannot overlap.

■ Q: What is STRIPS? How does it represent planning problems?

Ans:

STRIPS is a planning language where each action has: Preconditions (conditions that must hold before action), Add list
(facts that become true after action), Delete list (facts that become false after action). Planning finds a sequence of
actions from initial state to goal state. Example: MOVE(A, Table, B) — Precond: On(A,Table), Clear(A), Clear(B). Add:
On(A,B), Clear(Table). Delete: On(A,Table), Clear(B). STRIPS is foundational to all modern AI planning.
 CHAPTER 7

Machine Learning
Decision Trees, KNN, Naive Bayes — with Calculations

7.1 Types of Machine Learning

Type Description Examples Algorithms

Learns from labeled

training data (input-output Spam detection, image Decision Tree, SVM, Neural
Supervised pairs) classification Net, KNN, Naive Bayes

Finds patterns in Customer segmentation, K-Means, DBSCAN, PCA,

Unsupervised unlabeled data anomaly detection Autoencoders

Agent learns by trial and

error with Game playing, robot Q-Learning, SARSA, Policy
Reinforcement rewards/penalties control, trading Gradient, DQN

Mix of labeled and Self-training, Label

Semi-supervised unlabeled data Web content classification propagation

7.2 Decision Tree — ID3 Algorithm (Full Calculation)

A Decision Tree splits data based on features to classify examples. ID3 (Iterative Dichotomiser 3) selects the
feature with highest Information Gain (IG) at each split.

Formulas:

Entropy H(S) = -Sum[ p_i * log2(p_i) ]

where p_i = proportion of class i in set S

H=0: pure (all same class). H=1: maximally mixed (50-50).

Information Gain IG(S, A) = H(S) - Sum[ (|Sv|/|S|) * H(Sv) ]

where Sv = subset of S where attribute A has value v

=== FULL WORKED EXAMPLE ===

Play Tennis dataset (14 examples):

Outlook: Sunny(5), Overcast(4), Rain(5)

Play: Yes(9), No(5)

Step 1: Calculate H(S) for root node

 H(S) = -(9/14)log2(9/14) - (5/14)log2(5/14)

= -(0.643)(-.637) - (0.357)(-1.485)

= 0.410 + 0.530 = 0.940 bits

Step 2: Calculate IG for Outlook attribute

Sunny subset (5 examples): Play=Yes(2), No(3)

H(Sunny) = -(2/5)log2(2/5) - (3/5)log2(3/5)

= -(0.4)(-1.322) - (0.6)(-0.737)

= 0.529 + 0.442 = 0.971

Overcast subset (4 examples): Play=Yes(4), No(0)

H(Overcast) = -(4/4)log2(4/4) - 0 = 0 (pure!)

Rain subset (5 examples): Play=Yes(3), No(2)

H(Rain) = -(3/5)log2(3/5) - (2/5)log2(2/5)

= 0.442 + 0.529 = 0.971

IG(S, Outlook) = H(S) - [(5/14)H(Sunny)+(4/14)H(Over)+(5/14)H(Rain)]

= 0.940 - [(5/14)(0.971)+(4/14)(0)+(5/14)(0.971)]

= 0.940 - [0.347 + 0 + 0.347]

= 0.940 - 0.694 = 0.246 bits

Similarly calculate IG for Temperature, Humidity, Wind.

Choose attribute with HIGHEST IG as root node.

Recursively build tree on subsets.

Overcast -> always Yes (pure) -> LEAF node: Play=Yes

7.3 K-Nearest Neighbors (KNN)

Algorithm: classify new point by majority vote of k nearest training points

1. Choose k (e.g., k=3)

2. Calculate distance from new point to all training points

(Euclidean: d = sqrt((x1-x2)^2 + (y1-y2)^2))

 3. Find k nearest neighbors

4. Class = majority class among k neighbors

Example: new point (5,4). Training data:

A(2,3) class=Red, B(4,5) class=Red

C(6,2) class=Blue, D(5,6) class=Blue, E(3,4) class=Red

d(new, A) = sqrt((5-2)^2+(4-3)^2) = sqrt(10) = 3.16

d(new, B) = sqrt((5-4)^2+(4-5)^2) = sqrt(2) = 1.41

d(new, C) = sqrt((5-6)^2+(4-2)^2) = sqrt(5) = 2.24

d(new, D) = sqrt((5-5)^2+(4-6)^2) = sqrt(4) = 2.00

d(new, E) = sqrt((5-3)^2+(4-4)^2) = sqrt(4) = 2.00

k=3 nearest: B(1.41), D(2.00), E(2.00)

Votes: B=Red, D=Blue, E=Red -> 2 Red, 1 Blue

Classify as: RED

Choosing k: odd k avoids ties. Small k=overfitting. Large k=underfitting.

7.4 Evaluation Metrics

Confusion Matrix (Binary Classification):

Predicted Positive Predicted Negative

Actual Positive TP FN

Actual Negative FP TN

Accuracy = (TP + TN) / (TP + TN + FP + FN)

Precision = TP / (TP + FP) [of predicted positive, how many correct?]

Recall = TP / (TP + FN) [of actual positive, how many found?]

F1 Score = 2 * Precision * Recall / (Precision + Recall)

Overfitting: model too complex, memorizes training data, fails on new data

Underfitting: model too simple, fails even on training data

Regularization: penalty for complexity (L1/Lasso, L2/Ridge)

 Cross-validation: k-fold -- train on k-1 folds, test on 1, repeat k times

Exam / Viva / Interview — Questions & Answers

■ Q: What is the difference between supervised, unsupervised, and reinforcement learning?

Ans:

Supervised: learns from labeled data (input-output pairs) — algorithm learns mapping from inputs to outputs. Examples:
email spam classification, image recognition. Unsupervised: finds hidden patterns in unlabeled data — no target output.
Examples: customer segmentation, anomaly detection, dimensionality reduction. Reinforcement: agent learns by
interacting with environment, receives rewards/penalties — maximizes cumulative reward. Examples: AlphaGo, game
AI, robot navigation. No supervisor, learns from consequences of actions.

■ Q: Explain the ID3 algorithm for Decision Trees. What is entropy and information gain?

Ans:

ID3 builds a decision tree by recursively choosing the best attribute to split on. Entropy H(S) = -Sum[p_i * log2(p_i)]
measures impurity/disorder. H=0 means pure (all same class). H=1 means maximally mixed. Information Gain IG(S,A) =
H(S) - weighted sum of entropy of subsets after splitting on A. ID3 chooses attribute with HIGHEST information gain at
each step. Recursively applied until pure subsets or no more attributes.
 CHAPTER 8

Neural Networks & Deep Learning

Perceptron, Backpropagation, CNN, RNN

8.1 Biological vs Artificial Neuron

Biological Neuron Artificial Neuron (Perceptron)

Dendrites receive signals Inputs (x1, x2, ..., xn)

Synapse strength Weights (w1, w2, ..., wn)

Cell body sums inputs Weighted sum: z = sum(wi*xi) + b

Axon fires if threshold exceeded Activation function: output = f(z)

Signal to next neurons Output passed to next layer

8.2 Perceptron — Model & Learning Rule (Calculation)

Perceptron (single neuron):

Output y = 1 if (w1*x1 + w2*x2 + ... + wn*xn + b) >= 0

0 otherwise

Perceptron Learning Rule:

wi_new = wi_old + learning_rate * (target - output) * xi

b_new = b_old + learning_rate * (target - output)

=== WORKED EXAMPLE: Learn AND gate ===

Inputs: x1, x2. Target: x1 AND x2

Learning rate = 0.1. Initial: w1=0, w2=0, b=0

Training data: (0,0)->0, (0,1)->0, (1,0)->0, (1,1)->1

Epoch 1:

(0,0)->0: z=0*0+0*0+0=0, output=1 (z>=0). Error=0-1=-1.

w1=0+0.1*(-1)*0=0, w2=0+0.1*(-1)*0=0, b=0+0.1*(-1)=-0.1

(0,1)->0: z=0*0+0*1+(-0.1)=-0.1, output=0. Error=0-0=0. No update.

 (1,0)->0: z=0*1+0*0+(-0.1)=-0.1, output=0. Error=0. No update.

(1,1)->1: z=0*1+0*1+(-0.1)=-0.1, output=0. Error=1-0=1.

w1=0+0.1*1*1=0.1, w2=0+0.1*1*1=0.1, b=-0.1+0.1*1=0

...Continue training epochs until convergence...

Perceptron convergence theorem: if data is linearly separable,

perceptron WILL converge to a solution in finite steps.

Limitation: cannot learn XOR (not linearly separable).

Solution: Multi-layer perceptron (MLP) with hidden layers.

8.3 Multilayer Perceptron & Backpropagation

MLP has input layer, one or more hidden layers, and output layer. Backpropagation trains it by: (1) Forward
pass — compute output. (2) Compute loss (error). (3) Backward pass — propagate error backward, compute
gradients. (4) Update weights using gradient descent.

Activation Functions:

Sigmoid: f(z) = 1/(1+e^-z) [0,1] -- vanishing gradient problem

Tanh: f(z) = tanh(z) [-1,1] -- better than sigmoid

ReLU: f(z) = max(0,z) [0,inf) -- most popular, fast

Softmax: converts outputs to probabilities (multiclass)

Loss Functions:

MSE (regression): L = (1/n) * sum((y_pred - y_true)^2)

Cross-Entropy (class): L = -sum(y_true * log(y_pred))

Gradient Descent: w = w - learning_rate * (dL/dw)

Batch GD: use all data each step (stable, slow)

SGD: use 1 sample each step (fast, noisy)

Mini-batch: use small batch (best of both)

8.4 Deep Learning Overview

Architecture Full Name Best For Key Feature
 Convolutional filters extract local
CNN Convolutional Neural Network Images, video features; pooling reduces size

Sequences, text, time Hidden state carries memory

RNN Recurrent Neural Network series across time steps

Gates control what to

remember/forget — solves
LSTM Long Short-Term Memory Long sequences, NLP vanishing gradient

Self-attention mechanism —
NLP, translation, processes all positions
Transformer Transformer generation simultaneously

Generative Adversarial Generator vs Discriminator

GAN Network Image generation adversarial training

Exam / Viva / Interview — Questions & Answers

■ Q: What is a perceptron? Explain the perceptron learning rule.

Ans:

Perceptron: simplest neural network — single artificial neuron. Output = 1 if weighted sum of inputs >= threshold, else 0.
Learning rule: adjust weights based on error. wi_new = wi + lr * (target - output) * xi. For each training example: compute
output, calculate error (target - output), update each weight. Convergence theorem: if data is linearly separable,
perceptron converges. Limitation: cannot solve XOR (not linearly separable). Solution: multilayer networks with hidden
layers.

■ Q: What is backpropagation? How does it train a neural network?

Ans:

Backpropagation trains multilayer networks by: (1) Forward pass — inputs propagate through layers to compute output.
(2) Compute loss (error between output and target). (3) Backward pass — use chain rule to compute gradient of loss
with respect to each weight (dL/dw). (4) Update weights: w = w - lr * (dL/dw). Repeats for many epochs. Chain rule
allows gradients to propagate from output layer backward through hidden layers.

■ Q: What is the difference between CNN and RNN?

Ans:

CNN (Convolutional Neural Network): designed for spatial data (images). Uses convolutional filters to detect local
features (edges, textures) + pooling to reduce dimensions. Features detected regardless of position (translation
invariance). Best for: image classification, object detection. RNN (Recurrent Neural Network): designed for sequential
data. Hidden state carries information from previous time steps — provides memory. Best for: time series, NLP, speech.
Problem: vanishing gradient for long sequences. LSTM/GRU solve this with gating mechanisms.
 CHAPTER 9

Natural Language Processing

NLP Pipeline, Language Models, Word Embeddings

9.1 What is NLP?

Natural Language Processing (NLP) is a field of AI that enables computers to understand, interpret, generate,
and interact with human language. Challenges: ambiguity (multiple meanings), context-dependence, idioms,
sarcasm, cultural references.

9.2 NLP Pipeline

Ste
p Name Description Example

1 Tokenization Split text into words/sentences "I love AI" -> ["I", "love", "AI"]

Remove common words (the,

2 Stopword Removal is, and) "love AI" (removed "I")

Stemming/Lemmat
3 ization Reduce words to root form "running" -> "run"

Label each word with part of

4 POS Tagging speech "love"=VB, "AI"=NN

Named Entity Recognition —

5 NER find names, places "BUET" = Organization

6 Parsing Analyze grammatical structure Parse tree of sentence

7 Semantic Analysis Extract meaning Subject-verb-object relations

9.3 N-gram Language Models

N-gram: sequence of N words. Language model estimates P(word | context).

Unigram (N=1): P(w) = count(w) / total_words

Bigram (N=2): P(w2|w1) = count(w1,w2) / count(w1)

Trigram (N=3): P(w3|w1,w2) = count(w1,w2,w3) / count(w1,w2)

Example corpus: "the cat sat on the mat the cat"

Bigram probabilities:

P(cat|the) = count("the cat")/count("the") = 2/3 = 0.67

P(sat|cat) = count("cat sat")/count("cat") = 1/2 = 0.5

 Sentence probability (bigram):

P("the cat sat") = P(the) * P(cat|the) * P(sat|cat)

= (3/8) * 0.67 * 0.5 = 0.126

Problem: Sparsity -- unseen N-grams have 0 probability.

Solution: Smoothing (add-1/Laplace, Kneser-Ney)

9.4 Word Embeddings — Word2Vec

Word embeddings represent words as dense vectors in continuous space where semantically similar words are
close. Word2Vec (Google, 2013) learns embeddings by predicting context words.

Word2Vec approaches:

CBOW (Continuous Bag of Words):

Predict center word from surrounding context words

Input: context words -> Output: center word

Skip-gram:

Predict context words from center word (better for rare words)

Input: center word -> Output: context words

Famous Word2Vec relationships (vector arithmetic):

King - Man + Woman ≈ Queen

Paris - France + Germany ≈ Berlin

Bigger - Big + Small ≈ Smaller

Applications: similarity search, recommendation, document classification

Exam / Viva / Interview — Questions & Answers

■ Q: What is NLP? What are the main steps in an NLP pipeline?

Ans:

NLP enables computers to process human language. Pipeline: (1) Tokenization — split text into tokens
(words/sentences). (2) Stopword removal — remove common words (the, is). (3) Stemming/Lemmatization — reduce to
root form (running->run). (4) POS Tagging — label each word (noun, verb, adjective). (5) Named Entity Recognition —
identify names, places, organizations. (6) Parsing — analyze grammatical structure. (7) Semantic analysis — extract
meaning and relationships.

■ Q: What is a language model? Explain bigram model with an example.

Ans:

Language model: estimates probability of a sequence of words — P(w1,w2,...,wn). Bigram model: approximates using
only previous word: P(wi|w1..wi-1) ≈ P(wi|wi-1). Probability estimated from corpus: P(wi|wi-1) =
count(wi-1,wi)/count(wi-1). Example: if "the cat" appears 10 times and "the" appears 15 times, P(cat|the)=10/15=0.67.
Sentence P("the cat sat")=P(the)*P(cat|the)*P(sat|cat). Problem: unseen bigrams get 0 probability — solved by
smoothing.
 CHAPTER 10

Fuzzy Logic & Genetic Algorithm

Membership Functions, GA Traced

10.1 Fuzzy Logic

Classical (crisp) logic: everything is either true (1) or false (0). Fuzzy logic: truth values range from 0 to 1 —
allows partial membership. Models human reasoning about vague concepts like "tall", "hot", "fast".

Aspect Crisp (Classical) Logic Fuzzy Logic

Values 0 or 1 only Any value between 0 and 1

Sets Sharp boundaries Gradual boundaries

Example Temperature > 30 is HOT (yes/no) Temperature 28 might be 0.6 HOT

AND=min, OR=max, NOT=1-x (same

Operations formulas) AND=min, OR=max, NOT=1-x

Use cases Digital circuits, databases Control systems, AI, expert systems

10.2 Membership Functions — Examples

Membership function mu(x) gives degree of membership of x in fuzzy set.

Example: Fuzzy set "TALL" for height in cm

Trapezoidal membership function for TALL:

mu_TALL(x) = 0 if x < 160

(x-160)/20 if 160 <= x < 180 (rising)

1 if 180 <= x <= 190 (core)

(210-x)/20 if 190 < x <= 210 (falling)

0 if x > 210

Examples:

mu_TALL(155) = 0 (not tall at all)

mu_TALL(170) = (170-160)/20 = 0.5 (somewhat tall)

mu_TALL(185) = 1 (definitely tall)

mu_TALL(200) = (210-200)/20 = 0.5 (somewhat tall)

 Fuzzy operations:

Fuzzy AND: mu(A AND B) = min(mu(A), mu(B))

Fuzzy OR: mu(A OR B) = max(mu(A), mu(B))

Fuzzy NOT: mu(NOT A) = 1 - mu(A)

Defuzzification: convert fuzzy output to crisp value

Centroid method: x* = Sum[mu(x)*x] / Sum[mu(x)]

10.3 Genetic Algorithm

Genetic Algorithm (GA) is a search/optimization algorithm inspired by biological evolution. Uses population of
candidate solutions, applies selection, crossover (recombination), and mutation to evolve better solutions over
generations.

GA Component Biological Analogy In Algorithm

Chromosome Individual organism Candidate solution (bit string or array)

Gene Unit of heredity Single variable/parameter

Population Group of organisms Set of candidate solutions

Fitness Survival of the fittest How good the solution is (objective function)

Selection Natural selection Choose better individuals to reproduce

Crossover Sexual reproduction Combine two parents to create offspring

Mutation Random DNA change Random small change in chromosome

=== GENETIC ALGORITHM TRACED EXAMPLE ===

Problem: Maximize f(x) = x^2, x is 4-bit integer (0 to 15)

Initial Population (random 4-bit chromosomes):

P1: 0110 -> x=6, fitness=36

P2: 1101 -> x=13, fitness=169

P3: 0100 -> x=4, fitness=16

P4: 1000 -> x=8, fitness=64

Total fitness = 285

Selection (Roulette Wheel -- proportional to fitness):

P1 probability: 36/285 = 0.13

P2 probability: 169/285 = 0.59 <- most likely selected

 P3 probability: 16/285 = 0.06

P4 probability: 64/285 = 0.22

Selected pairs for crossover: (P2,P4) and (P2,P1)

Crossover (single-point, point=2):

P2: 11|01 + P4: 10|00 -> Offspring: 1100=12, 1001=9

P2: 11|01 + P1: 01|10 -> Offspring: 1110=14, 0101=5

New population:

O1: 1100 -> x=12, fitness=144

O2: 1001 -> x=9, fitness=81

O3: 1110 -> x=14, fitness=196 (better than parent!)

O4: 0101 -> x=5, fitness=25

Mutation (flip bit 3 of O4): 0101 -> 0111 = 7, fitness=49

Best in new generation: O3 with x=14, f=196 (was P2 with f=169)

After many generations, converges toward x=15, f=225 (maximum)

Exam / Viva / Interview — Questions & Answers

■ Q: What is fuzzy logic? How does it differ from classical logic?

Ans:

Fuzzy logic extends classical binary logic (0 or 1) to allow truth values between 0 and 1. Classical: temperature > 30 is
either HOT or NOT HOT. Fuzzy: temperature 28 might be 0.6 HOT and 0.4 NOT HOT. Membership function mu(x) gives
degree of belonging [0,1]. Operations: AND=min, OR=max, NOT=1-x. Applications: washing machines (fuzzy load
sensing), HVAC systems, anti-lock brakes, camera autofocus. Advantages: handles vagueness, mirrors human
reasoning naturally.

■ Q: Explain Genetic Algorithm. What are selection, crossover, and mutation?

Ans:

GA mimics evolution to optimize. Population of candidate solutions (chromosomes) evolves over generations. Selection:
choose fitter individuals to reproduce (roulette wheel — proportional to fitness, or tournament). Crossover: combine two
parent chromosomes at a random point to create offspring — explores new regions of search space. Mutation: randomly
change bits — maintains diversity, avoids local optima. Process: Initialize -> Evaluate fitness -> Select parents ->
Crossover -> Mutate -> Repeat until convergence.
 CHAPTER 11

Master Reference
All Algorithms, Formulas, Quick Revision

Search Algorithms — Summary

Complete
Algorithm Category ? Optimal? Time Space Key Feature

Shortest path (uniform

BFS Uninformed Yes Yes* O(b^d) O(b^d) cost)

DFS Uninformed No No O(b^m) O(bm) Memory efficient

Optimal for
UCS Uninformed Yes Yes O(b^C*) O(b^C*) non-uniform cost

BFS optimal + DFS

IDDFS Uninformed Yes Yes* O(b^d) O(bd) memory

Greedy Informed No No O(b^m) O(b^m) Fast but not optimal

A* Informed Yes Yes** O(b^d) O(b^d) Best informed search

Hill Climbing Local No No O(inf) O(1) No memory, fast

Simulated
Annealing Local Yes*** Yes*** Varies O(1) Avoids local optima

Note: *unit cost, **admissible heuristic, ***with slow enough cooling

ML Algorithms — Summary
Algorithm Type Pros Cons Best For

Interpretable, handles Classification,

Decision Tree Supervised mixed data Overfitting explainability needed

Slow prediction, needs Small datasets,

KNN Supervised Simple, no training storage recommendation

Fast, works with small Independence

Naive Bayes Supervised data assumption Text classification, spam

Black box, needs big Images, speech, complex

Neural Network Supervised High accuracy, flexible data patterns

K-Means Unsupervised Simple, scalable K must be specified Customer segmentation

Q-Learning RL Model-free Slow convergence Game AI, robot control

Key Formulas
 SEARCH:

f(n) = g(n) + h(n) [A* evaluation function]

Admissible: h(n) <= h*(n) [never overestimate]

INFORMATION THEORY / DECISION TREE:

Entropy H(S) = -Sum[ p_i * log2(p_i) ]

Info Gain IG(S,A) = H(S) - Sum[ (|Sv|/|S|) * H(Sv) ]

NEURAL NETWORKS:

Weighted sum: z = Sum(wi * xi) + b

Sigmoid: f(z) = 1 / (1 + e^-z)

ReLU: f(z) = max(0, z)

Weight update: w = w - lr * (dL/dw)

MSE Loss: L = (1/n) * Sum((y_pred - y_true)^2)

FUZZY LOGIC:

AND: min(mu_A, mu_B)

OR: max(mu_A, mu_B)

NOT: 1 - mu_A

Centroid defuzzification: x* = Sum[mu(x)*x] / Sum[mu(x)]

N-GRAM LANGUAGE MODEL:

Bigram: P(wi | wi-1) = count(wi-1, wi) / count(wi-1)

EVALUATION METRICS:

Accuracy = (TP+TN) / (TP+TN+FP+FN)

Precision = TP / (TP+FP)

Recall = TP / (TP+FN)

F1 Score = 2*P*R / (P+R)

Quick Concept Reference

Concept One-Line Definition
 Machine passes if interrogator cannot distinguish it from human in text
Turing Test conversation

Rational Agent Perceives environment, acts to maximize performance measure

PEAS Framework: Performance, Environment, Actuators, Sensors

Admissible Heuristic h(n) never overestimates true cost — guarantees A* optimality

Forward Chaining Data-driven inference: facts -> rules -> conclusions

Backward Chaining Goal-driven inference: start from goal, find supporting facts

AI that emulates domain expert using rule-based knowledge + inference

Expert System engine

Entropy Measure of impurity/disorder in a set: H=0 pure, H=1 maximally mixed

Backpropagation Algorithm to train neural nets by propagating error gradient backward

Overfitting Model too complex — memorizes training data, fails on new data

Fuzzy Set Set with gradual membership degrees between 0 and 1 (not just 0 or 1)

Evolutionary optimization: selection + crossover + mutation on

Genetic Algorithm population

Word Embedding Dense vector representation of words capturing semantic similarity

Reinforcement Learning Agent learns by trial and error — maximizes cumulative reward signal

CNN Neural network for images using convolution filters + pooling

RNN/LSTM Neural network for sequences — maintains hidden state as memory

Best of luck for your AI & Expert Systems exam, viva, and interview!