Artificial Intelligence

Module 1

Prepared by Asit Das 1

 Intelligence and AI
- Intelligence: Intelligence is the ability to think, to learn from experience, to solve
problems, and to adapt to new situations.
- Intelligence is important because it has an impact on many human behaviors.
But…..
- Artificial intelligence is the simulation of human intelligence processes by machines,
especially computer systems.
- Specific applications of AI include expert systems, natural language processing, speech
recognition and machine vision.
AI programming focuses on three cognitive aspects, such as learning, reasoning, and
self-correction.
- Learning Processes - This part of AI programming is concerned with gathering data
and creating rules and transformed it into useful information.
- The rules, which are also called algorithms, offer computing
devices with step-by-step instructions for accomplishing a
particular job).
- Reasoning Processes - This part of AI programming is concerned with selecting
the best algorithm to achieve the desired result.
- Self-correction Processes - This part of AI programming aims to fine-tune algorithms
regularly in order to ensure that they offer the most
reliablePrepared
resultsby possible.
Asit Das 2
So AI is an extensive field of computer science which focuses on:
- Developing intelligent machines capable of doing activities that would normally
require human intelligence.
- While AI is a multidisciplinary science with numerous methodologies, advances in
deep learning and machine learning create a paradigm shift in almost every aspect
of technology.
Examples of AI-Artificial Intelligence
• Google Maps and Ride-Hailing Applications - Online Ads-Network
• Face Detection and recognition - Text Editors and Autocorrect
• Chatbots - Search and Recommendation algorithms
• E-Payments - Digital Assistant
• Social media - Healthcare
• Gaming - Banking and Finance
• Smart Home devices - Security and Surveillance
• Smart Keyboard App - Music and Media Streaming Service
• Smart Speaker - Smart Email Apps
• E-Commerce - Space Exploration
Prepared by Asit Das 3
 Advs and Dis advs of AI

Advantages
• Good at detail-oriented jobs
• Reduced time for data-heavy tasks
• Delivers consistent results and
• AI-powered virtual agents are always available.
• Disadvantages
• Expensive
• Requires deep technical expertise
• Limited supply of qualified workers to build AI tools
• Only knows what it's been shown and
• Lack of ability to generalize from one task to another.

Prepared by Asit Das 4

Strong AI vs. weak AI
• AI can be categorized as either weak or strong.
- Weak AI, also known as narrow AI,
- It is designed and trained to complete a specific task.
- Example: Industrial robots and virtual personal
assistants, such as Apple's Siri, use weak AI.
- Strong AI, also known as artificial general intelligence (AGI),
- It describes programming that can replicate the cognitive abilities of the
human brain.
- When presented with an unfamiliar task, a strong AI system can use fuzzy
logic to apply knowledge from one domain to another and find a solution
autonomously.
- In theory, a strong AI program should be able to pass both a Turing Test and
the Chinese room test.

Prepared by Asit Das 5

 Different types of AI
AI can be categorized into four types, beginning with the task-specific intelligent systems in
wide use today and progressing to sentient systems, which do not yet exist. - The categories
are as follows:
• Type 1: Reactive machines :
- These AI systems have no memory and are task specific.
- An example is Deep Blue, the IBM chess program that beat Garry Kasparov in the 1990s.
Deep Blue can identify pieces on the chessboard and make predictions, but because it
has no memory, it cannot use past experiences to inform future ones.
• Type 2: Limited memory :
- These AI systems have memory, so they can use past experiences to inform future
decisions.
- Some of the decision-making functions in self-driving cars are designed this way.
• Type 3: Theory of mind :
- Theory of mind is a psychology term. When applied to AI, it means that the system
would have the social intelligence to understand emotions.
- This type of AI will be able to infer human intentions and predict behavior, a necessary
skill for AI systems to become integral members of human teams.
• Type 4: Self-awareness:
- In this category, AI systems have a sense of self, which gives them consciousness.
- Machines with self-awareness understand their own current state. This type of AI does
not yet exist.
Prepared by Asit Das 6
 Applications of AI

AI has made its way into a wide variety of applications. Apart form this we discuss nine
examples as follows:
1. AI in healthcare
- The biggest bets are on improving patient outcomes and reducing costs.
- Companies are applying machine learning to make better and faster diagnoses
than humans. best-known healthcare technologies is IBM Watson.
- It understands natural language and can respond to questions asked of it.
- The system mines patient data and other available data sources to form a
hypothesis, which it then presents with a confidence scoring schema.
- Other AI applications include using online virtual health assistants and chatbots to
help patients and healthcare customers.
- Find medical information, schedule appointments, understand the billing process
and complete other administrative processes.
- An array of AI technologies is also being used to predict, fight and understand
pandemics such as COVID-19.
Prepared by Asit Das 7
2. AI in business.
- ML algorithms are being integrated into analytics and customer relationship
management(CRM) platforms to uncover information on how to better serve
customers.
- Chatbots have been incorporated into websites to provide immediate service to
customers.
- Automation of job positions has also become a talking point among academics and
IT analysts.
3. AI in education
- AI can automate grading, giving educators more time.
- It can assess students and adopt to their needs, helping them work at their own
pace.
- AI tutors can provide additional support to students, ensuring they stay on track.
And it could change where and how students learn, perhaps even replacing some
teachers.
4. AI in finance
- AI in personal finance applications, such as Intuit Mint or TurboTax, is disrupting
financial institutions.
- Applications such as these collect personal data and provide financial advice.
- Today, artificial intelligence software performs
Prepared by Asit Das much of the trading on Wall Street.8
5. AI in law
- The discovery process -- sifting through documents -- in law is often overwhelming
for humans.
- Using AI to help automate the legal industry's labor-intensive processes is saving
time and improving client service.
- Law firms are using machine learning to describe data and predict outcomes,
computer vision to classify and extract information from documents and natural
language processing to interpret requests for information.
6. AI in manufacturing
- Manufacturing has been at the forefront of incorporating robots into the work
flow.
- For example, the industrial robots that were at one time programmed to perform
single tasks and separated from human workers,
7. AI in banking.
- Banks are successfully employing chatbots to make their customers aware of
services and offerings and to handle transactions that don't require human
intervention.
- AI virtual assistants are being used to improve and cut the costs of compliance
with banking regulations.
- Banking organizations are also using AI to improve their decision-making for loans,
and to set credit limits and identify investment
Prepared by Asit Das opportunities. 9
8. AI in transportation
- In addition to AI's fundamental role in operating autonomous vehicles, AI
technologies are used in transportation to manage traffic, predict flight delays, and
make ocean shipping safer and more efficient.
9. Security
- AI and machine learning are at the top of the buzzword list security vendors use
today to differentiate their offerings.
- Those terms also represent truly viable technologies.
- Organizations use machine learning in security information and event
management (SIEM) software and related areas to detect anomalies
- It is easily identify suspicious activities that indicate threats.
- By analyzing data and using logic to identify similarities to known malicious code
- AI can provide alerts to new and emerging attacks much sooner than human
employees and previous technology iterations.
- The maturing technology is playing a big role in helping organizations fight off
cyber attacks.

Prepared by Asit Das 10

Responsibility of AI

Prepared by Asit Das 11

 Agent
- In AI, an intelligent agent (IA) is anything which perceives its environment,
takes actions autonomously in order to achieve goals, and may improve its
performance with learning or may use knowledge.
- An agent is anything that can be viewed as :
– perceiving its environment through sensors and
– acting upon that environment through actuators
(Note: Every agent can perceive its own actions (but not always the effects)

Prepared by Asit Das 12

- To understand the structure of Intelligent Agents, we should be familiar with
Architecture and Agent programs.
- Architecture is the machinery that the agent executes on. It is a device with
sensors and actuators, for example, a robotic car, a camera, a PC.
- Agent program is an implementation of an agent function. An agent function is a
map from the percept sequence(history of all that an agent has perceived to date)
to an action.
Agent = Architecture + Agent Program

Prepared by Asit Das 13

 Different types of Agent
Following are the different types of agent model:
1. Reactive
2. Deliberative
3. Goal-driven
4. Utility driven
5. Learning agents
1. Reactive Agent:
• Reactive agents are software agents that carry out a simple task of retrieving pre-
set behaviors similar to reflexes.
• Reactive agents do not maintain the internal state, unlike deliberative agents.
• Simply be said that an agent that has no internal state is a reactive agent
• Reactive agent does not maintains its internal state and predicts the effects of
actions.
• Reactive agents consume fewer system resources, which cannot generate results
that are good as those from deliberative agents.
• Few reactive agents can re-plan the actions quickly.

Prepared by Asit Das 14

Limitations of Reactive Agents :
- They cannot react automatically on the basis of information from the external environment.
- Reactive agents must have enough data available in the local or internal environment to
figure out a satisfactory action.
- In the decision-making process, it is difficult for reactive agents to take into account the
external or non-local information.
- Reactive agents do not understand the relationship between environmental and individual
behavior.
- These agents cannot understand the overall behavior.

Prepared by Asit Das 15

2. Deliberative Agent
- A deliberative agent is a software agent that contains the symbolic world and
makes decisions via symbolic reasoning.
- Deliberative agent can reach its goal by reacting automatically based on the
external environment.
- Deliberative agent maintains a symbolic representation of the world. It can process
the images of the external environment, which enables it to plan its actions.
- Intentional systems are the base for deliberative agents. Deliberation decides what
should be achieved, and how to achieve.
- The state of affairs chosen by a deliberative agent intentionally is known as an
intention. Intentions derive means-end reasoning.
- Intentions stimulate an attempt to execute the intention, and hence they lead to
an action.
- A deliberative agent has two types of attitudes:
- Informative (which involves information about the environment)
- Pro-attitudes (which guide the actions of the agent)

Prepared by Asit Das 16

Fig. of ReactivePrepared
and Deliberative
by Asit Das Agents 17
3. Goal-Driven Agent
- These kinds of agents take decisions based on how far they are currently from their
goal(description of desirable situations).
- Their every action is intended to reduce its distance from the goal.
- This allows the agent a way to choose among multiple possibilities, selecting the one
which reaches a goal state.
- The knowledge that supports its decisions is represented explicitly and can be modified,
which makes these agents more flexible.
- They usually require search and planning. The goal-driven agent’s behavior can easily
be changed.

Prepared by Asit Das 18

4. Utility Driven Agent
- The agents which are developed
having their end uses as building
blocks are called utility-driven
agents.
- When there are multiple possible
alternatives, then to decide which
one is best, utility-driven agents
are used.
- They choose actions driven on a
preference (utility) for each state.
Sometimes achieving the desired
goal is not enough. We may look
for a quicker, safer, cheaper trip to
reach a destination.
- Agent happiness should be taken
into consideration. Utility describes
how “happy” the agent is. Because
of the uncertainty in the world, a
utility agent driven the action that
maximizes the expected utility.
- A utility function maps a state onto
a real number which describes the
associated degree of happiness.
Prepared by Asit Das 19
5. Learning Agent

A learning agent in AI is the type of agent that can learn from its past experiences or it
has learning capabilities.
- It starts to act with basic knowledge and then is able to act and adapt
automatically through learning.
- A learning agent has mainly four conceptual components, which are:
• Learning element: It is responsible for making improvements by learning from the
environment
• Critic: The learning element takes feedback from critics which describes how well
the agent is doing with respect to a fixed performance standard.
• Performance element: It is responsible for selecting external action
• Problem Generator: This component is responsible for suggesting actions that will
lead to new and informative experiences.

Prepared by Asit Das 20

Prepared by Asit Das 21
 Environment
• The environment in AI is everything that surrounds the agent but not the agent
itself.
• The agent takes input from the environment through sensors and delivers the
output to the environment through actuators.
• The environment in which an AI functions can be considered as the entity that the
agent used to make sense of things around it to eventually act upon things that
can be used to effectively solve a problem.
• Based on the AI system, an agent can have the ability to either partially observe
the surrounding environment or fully understand the same by keeping a track of
the history and using the data it has learned from to assess the changes around it.
• In the case of sequential environments, the AI agent uses its memory to analyze
past actions to directly determine the next suitable actions it has to take.
• A stochastic environment on the other hand is random in nature and it cannot be
determined effectively by the agent.

Prepared by Asit Das 22

Prepared by Asit Das 23
 Properties of Environment in AI
• An environment can be described as a situation in which an agent is present.
• The environment is where agent lives, operate and provide the agent with something
to sense and act upon it.
• An environment is mostly said to be non-feministic.
Properties of Environment :
As per Russell and Norvig, an environment can
have various features from the point of view
of an agent:
1. Fully observable vs Partially Observable
2. Static vs Dynamic
3. Discrete vs Continuous
4. Deterministic vs Stochastic
5. Single-agent vs Multi-agent
6. Episodic vs sequential
7. Known vs Unknown
8. Accessible vs Inaccessible

Prepared by Asit Das 24

1. Fully observable vs Partially Observable:
• If an agent sensor can sense or access the complete state of an environment at each
point of time then it is a fully observable environment, else it is partially observable.
• A fully observable environment is easy as there is no need to maintain the internal
state to keep track history of the world.
• An agent with no sensors in all environments then such an environment is called as
unobservable.
2. Deterministic vs Stochastic:
• If an agent's current state and selected action can completely determine the next
state of the environment, then such environment is called a deterministic
environment.
• A stochastic environment is random in nature and cannot be determined completely
by an agent.
Examples: Chess – there would be only a few possible moves for a coin at the current state and
these moves can be determined.
Self-Driving Cars- the actions of a self-driving car are not unique, it varies time to time.
3. Episodic vs Sequential:
• In an episodic environment, there is a series of one-shot actions, and only the
current percept is required for the action.
• However, in Sequential environment, an agent requires memory of past actions to
determine the next best actions.
Prepared by Asit Das 25
4. Single-agent vs Multi-agent:
• If only one agent is involved in an environment, and operating by itself then such
an environment is called single agent environment.
• However, if multiple agents are operating in an environment, then such an
environment is called a multi-agent environment.
• The agent design problems in the multi-agent environment are different from
single agent environment.
5. Static vs Dynamic:
• If the environment can change itself while an agent is deliberating then such
environment is called a dynamic environment else it is called a static environment.
• Static environments are easy to deal because an agent does not need to continue
looking at the world while deciding for an action.
• However for dynamic environment, agents need to keep looking at the world at
each action.
• Taxi driving is an example of a dynamic environment whereas Crossword puzzles
are an example of a static environment.

Prepared by Asit Das 26

6. Discrete vs Continuous:
• If in an environment there are a finite number of percepts and actions that can be
performed within it, then such an environment is called a discrete environment
else it is called continuous environment.
• A chess game comes under discrete environment as there is a finite number of
moves that can be performed.
• A self-driving car is an example of a continuous environment.
7. Known vs Unknown:
• Known and unknown are not actually a feature of an environment, but it is an
agent's state of knowledge to perform an action.
• In a known environment, the results for all actions are known to the agent. While
in unknown environment, agent needs to learn how it works in order to perform
an action.
• It is quite possible that a known environment to be partially observable and an
Unknown environment to be fully observable.
8. Accessible vs Inaccessible:
• If an agent can obtain complete and accurate information about the state's
environment, then such an environment is called an Accessible environment else it
is called inaccessible.
• An empty room whose state can be defined by its temperature is an example of an
accessible environment.
• Information about an event on earth is an example of Inaccessible environment.

Prepared by Asit Das 27

 State space

• A state space is the set of all possible configurations of a system.

• It is a useful abstraction for reasoning about the behavior of a given system and is
widely used in the fields of artificial intelligence and game theory.
• Thus State Space is known as the set of all possible and known states of a system.
• In state-space, each unique point represents a state of the system.
• For example, Take a pendulum moving in to and fro motion. The state of such an
idealized pendulum is represented by its angle and its angular velocity.
- State Space Representation consist of defining an INITIAL State (from where to
start), the GOAL State (The destination)
- Then we follow certain set of sequence of steps (called States). Let's define each
of them separately.
- State: AI problem can be represented as a well formed set of possible states
- A state space is the total space available for the agent in the state.

Prepared by Asit Das 28

 Knowledge representation
• Knowledge Representation in AI describes the representation of knowledge. Basically,
it is a study of how the beliefs, intentions, and judgments of an intelligent agent can
be expressed suitably for automated reasoning.
• One of the primary purposes of Knowledge Representation includes modeling
intelligent behavior for an agent.
• Knowledge Representation and Reasoning (KR, KRR) represents information from the
real world for a computer to understand
• Then utilize this knowledge to solve complex real-life problems like communicating
with human beings in natural language.
• Knowledge representation in AI is not just about storing data in a database, it allows a
machine to learn from that knowledge and behave intelligently like a human being.
- The different kinds of knowledge that need to be represented in AI include:
• Objects
• Events
• Performance
• Facts
• Meta-Knowledge
• Knowledge-base
Prepared by Asit Das 29
Different Types of Knowledge
There are 5 types of Knowledge such as:
• Declarative Knowledge – It includes concepts,
facts, and objects and expressed in a
declarative sentence.
• Structural Knowledge – It is a basic problem-
solving knowledge that describes the
relationship between concepts and objects.
• Procedural Knowledge – This is responsible
for knowing how to do something and
includes rules, strategies, procedures, etc.
• Meta Knowledge – Meta Knowledge
defines knowledge about other types of
Knowledge.
• Heuristic Knowledge – This represents some
expert knowledge in the field or subject.
These are the 5 important types of Knowledge Representation in AI.

Prepared by Asit Das 30

 Rationality
• Rationality is nothing but status of being reasonable, sensible, and having good
sense of judgment.
• Rationality implies the conformity of one's beliefs with one's reasons to believe, or of
one's actions with one's reasons for action.
• It is concerned with expected actions and results depending upon what the agent
has perceived.
• Performing actions with the aim of obtaining useful information is an important part
of rationality.
What is Ideal Rational Agent?
• An ideal rational agent is the one, which is capable of doing expected actions to
maximize its performance measure, on the basis of −
• Its percept sequence
• Its built-in knowledge base
Rationality of an agent depends on the following −
- The performance measures, which determine the degree of success.
- Agent’s Percept Sequence till now.
- The agent’s prior knowledge about the environment.
- The actions that the agent can carry out.
Prepared by Asit Das 31
• A rational agent always performs right action where the right action means the action
that causes the agent to be most successful in the given percept sequence.
• The problem the agent solves is characterized by Performance Measure, Environment,
Actuators, and Sensors (PEAS).
Ex: Automated Taxi Driver:
- Performance Measure: Safe, fast, legal, comfortable trip, maximize profits.
- Environment: Roads, other traffic, customers.
- Actuators: Steering wheel, accelerator, brake, signal, horn.
- Sensors: Cameras, sonar, speedometer, GPS, odometer, engine sensors,
keyboard.

Turing Test:
- The Turing Test is a method of inquiry in artificial intelligence (AI) for determining
whether or not a computer is capable of thinking like a human being.
- In this test, Turing proposed that the computer can be said to be an intelligent if it can
mimic human response under specific conditions.
- The test is named after Alan Turing, 1950 , the founder of the Turing Test and an
English computer scientist, cryptanalyst, mathematician and theoretical biologist.

Prepared by Asit Das 32

Player A is a computer, Player B is human, and Player C is an
interrogator. Interrogator is aware that one of them is
machine, but he needs to identify this on the basis of
questions and their responses.

Prepared by Asit Das 33

Features required for a machine to pass the Turing test:
• Natural language processing: NLP is required to communicate with Interrogator in
general human language like English.
• Knowledge representation: To store and retrieve information during the test.
• Automated reasoning: To use the previously stored information for answering the
questions.
• Machine learning: To adapt new changes and can detect generalized patterns.
• Vision (For total Turing test): To recognize the interrogator actions and other
objects during a test.
• Motor Control (For total Turing test): To act upon objects if requested.

Prepared by Asit Das 34

 Search Techniques- Definition and
Importance

• In Artificial Intelligence, Search techniques are most important areas of Artificial

Intelligence.
• Universal problem-solving methods.
• Rational agents or Problem-solving agents in AI mostly used these search
techniques or algorithms to solve a specific problem and provide the best result.

Prepared by Asit Das 35

 Search Techniques/Algorithm Terminologies
Search: Searching is a step by step procedure to solve a search-problem in a given
search space.
• A search problem can have three main factors:
– Search Space: Search space represents a set of possible solutions, which a
system may have.
– Start State: It is a state from where agent begins the search.
– Goal test: It is a function which observe the current state and returns whether
the goal state is achieved or not.
• Search tree: A tree representation of search problem is called Search tree.
- The root of the search tree is the root node which is corresponding to the
initial state.
• Actions: It gives the description of all the available actions to the agent.
• Transition model: A description of what each action do, can be represented as a
transition model.
• Path Cost: It is a function which assigns a numeric cost to each path.
• Solution: It is an action sequence which leads from the start node to the goal
node.
• Optimal Solution: If a solution has the lowest
Prepared by Asit Dascost among all solutions. 36
 Properties or Importance of Search Algorithms

Four essential properties of search algorithms:

1. Completeness: A search algorithm is said to be complete if it guarantees to
return a solution if at least any solution exists for any random input.
2. Optimality: If a solution found for an algorithm is guaranteed to be the best
solution (lowest path cost) among all other solutions, then such a solution for is
said to be an optimal solution.
3. Time Complexity: Time complexity is a measure of time for an algorithm to
complete its task.
4. Space Complexity: It is the maximum storage space required at any point during
the search, as the complexity of the problem.

Prepared by Asit Das 37

Types of search algorithms

Prepared by Asit Das 38

Uninformed/Blind Search
• The uninformed search does not contain any domain knowledge such as closeness,
the location of the goal.
• It operates in a brute-force way as it only includes information about how to
traverse the tree and how to identify leaf and goal nodes.
• Uninformed search applies a way in which search tree is searched without any
information about the search space like initial state operators and test for the goal.
• So it is also called blind search. It examines each node of the tree until it achieves
the goal node.
• Ex: DFS,BFS,ID,DLS etc
Informed Search
• Informed search algorithms use domain knowledge.
• Problem information is available which can guide the search.
• Informed search strategies can find a solution more efficiently than an uninformed
search strategy. I
• Also called as Heuristic search.
• A heuristic is a way which might not always be guaranteed for best solutions but
guaranteed to find a good solution in reasonable time.
• Ex: Traveling salesman problem, Greedy Search, A* Search , Best first search etc
Prepared by Asit Das 39
 Depth First Search (DFS)
• Depth-first search is a recursive algorithm for traversing a tree or graph data
structure.
• It is called the depth-first search because it starts from the root node and follows
each path to its greatest depth node before moving to the next path.
• DFS uses a stack data structure for its implementation.
• The process of the DFS algorithm is similar to the BFS algorithm.
Advantage:
• DFS requires very less memory as it only needs to store a stack of the nodes on the
path from root node to the current node.
• It takes less time to reach to the goal node than BFS algorithm (if it traverses in the
right path).
Dis-advantage:
• There is the possibility that many states keep re-occurring, and there is no
guarantee of finding the solution.
• DFS algorithm goes for deep down searching and sometime it may go to the
infinite loop.

Prepared by Asit Das 40

Example:
Follow the order as:
Root node--->Left node ----> right node.
Start searching from root node:
- S --> A --> B, --> D --> E,
- After traversing E, it will backtrack the
tree as E has no other successor and
still goal node is not found.
- After backtracking it will traverse node
C --> G
- Here it will terminate as it found goal
node.

Prepared by Asit Das 41

Time Complexity: Time complexity of DFS will be equivalent to the node traversed by
the algorithm. It is given by:

T(n)= 1+ n2+ n3 +.........+ nm=O(nm)

Where, m= maximum depth of any node and this can be much larger than d
(Shallowest solution depth)

Space Complexity:
DFS algorithm needs to store only single path from the root node, hence space
complexity of DFS is equivalent to the size of the fringe set, which is O(bm).

Optimal:
DFS search algorithm is non-optimal, as it may generate a large number of steps or
high cost to reach to the goal node.

Completeness: DFS search algorithm is complete within finite state space as it will
expand every node within a limited search tree.

Prepared by Asit Das 42

 Breadth-first Search (BFS)

• BFS is the most common search strategy for traversing a tree or graph.
• This algorithm searches breadth wise in a tree or graph, so it is called breadth-first
search.
• Algorithm starts searching from the root node of the tree and expands all
successor node at the current level before moving to nodes of next level.
• The BFS algorithm is an example of a general-graph search algorithm.
• Breadth-first search implemented using FIFO queue data structure.
Advantages:
• BFS will provide a solution if any solution exists.
• If there are more than one solutions for a given problem, then BFS will provide the
minimal solution which requires the least number of steps.
Disadvantages:
• It requires lots of memory since each level of the tree must be saved into memory
to expand the next level.
• BFS needs lots of time if the solution is far away from the root node.

Prepared by Asit Das 43

• Example:
• In the tree structure, the
traversing of the tree using BFS
algorithm.
• From the root node S to goal
node K.
• BFS search algorithm traverse in
layers, traversed path will be:
• S---> A--->B---->C--->D---->G---
>H--->E---->F---->I---->K

Prepared by Asit Das 44

Time Complexity:
Time Complexity of BFS algorithm can be obtained by the number of nodes traversed
in BFS until the shallowest Node.
Where the d= depth of shallowest solution and b is a node at every state.
• T (b) = 1+b2+b3+.......+ bd= O (bd)

Space Complexity:
Space complexity of BFS algorithm is given by the Memory size of frontier which is
O(bd).

Completeness: BFS is complete, which means if the shallowest goal node is at some
finite depth, then BFS will find a solution.

Optimality: BFS is optimal if path cost is a non-decreasing function of the depth of the
node.

Prepared by Asit Das 45

Depth-Limited Search Algorithm (DLS)

• A DLS algorithm is similar to DFS with a predetermined limit.

• DLS can solve the drawback of the infinite path in the DFS.
• The node at the depth limit will treat as it has no successor nodes further.

DLS can be terminated with two Conditions of failure:

• Standard failure value: It indicates that problem does not have any solution.
• Cutoff failure value: It defines no solution for the problem within a given depth limit.

• Advantages: DLS is Memory efficient.

• Disadvantages: DLS also has a disadvantage of incompleteness.

(It may not be optimal if the problem has more than one solution.)

Prepared by Asit Das 46

 Completeness: DLS search algorithm is
complete if the solution is above the
depth-limit.

Time Complexity: Time complexity of

DLS algorithm is O(bℓ).

Space Complexity: Space complexity of

DLS algorithm is O(b×ℓ)

Optimal: Depth-limited search can be

viewed as a special case of DFS, and it is
also not optimal even if ℓ>d.

Prepared by Asit Das 47

 ID Search(IDS) or ID Depth First Search(IDDFS)

• The iterative deepening algorithm is a combination of DFS and BFS algorithms.

• This search algorithm finds out the best depth limit and does it by gradually
increasing the limit until a goal is found.
• This algorithm performs DFS up to a certain "depth limit", and it keeps increasing
the depth limit after each iteration until the goal node is found.
• This Search algorithm combines the benefits of BFS's fast search and DFS's
memory efficiency.
• The iterative search algorithm is useful uninformed search when search space is
large, and depth of goal node is unknown.
Advantages:
• It combines the benefits of BFS and DFS search algorithm in terms of fast search
and memory efficiency.
Disadvantages:
• The main drawback of IDDFS is that it repeats all the work of the previous phase.

Prepared by Asit Das 48

 Example:

- The tree structure is

showing the IDDFS.
- IDDFS algorithm performs
various iterations until it
does not find the goal node.
- The iteration performed by
the algorithm is given as:

1'st Iteration-----> A
2'nd Iteration----> A, B, C
3'rd Iteration------>A, B, D, E, C, F, G
4'th Iteration------>A, B, D, H, I, E, C,
F, K, G
In the fourth iteration, the algorithm
will find the goal node.

Prepared by Asit Das 49

Completeness:
• This algorithm is complete is
ifthe branching factor is
finite.
Time Complexity:
• Let's suppose b is the
branching factor and depth is
d then the worst-case time
complexity is O(bd).
Space Complexity:
• The space complexity of
IDDFS will be O(bd).
Optimal:
• IDDFS algorithm is optimal if
path cost is a non- decreasing
function of the depth of the
node.
Prepared by Asit Das 50
 Iterative broadening

• Iterative broadening is a search method designed for trees of fixed depth and
uniform branching factor.
• Any node that has at least one goal node in its descendants has exactly s
successful children, where s is some constant;
• That is, trees where decisions made at each point are equally important.
• The method is to expand only the first c branches at each node;
• If the entire tree is searched under this restriction without success, c is increased
by some small amount and a search is made through the extra siblings then
available.
• An intuitive argument for the algorithm is given, followed by an analysis showing it
expands fewer nodes than conventional search methods in some cases.
• The analysis is backed up by experimental results showing improvements in a
crossword puzzle generator.

Prepared by Asit Das 51

• Rather than increasing the depth of the search, iterative broadening increases its
breadth at every iteration.
• Thus on the first iteration only the first child of every node is expanded; on the
next iteration both the first and second, and so forth.
• The intuition is that goal nodes are not usually randomly distributed in a tree,
• So it is wasteful to explore an entire portion of a tree at once.
• The basic idea is to search the space using artificial breadth cutoffs that are
gradually increased until a goal is found.
• If the goal nodes for a given problem are distributed randomly along the fringe of
the search tree then iterative broadening leads to orders-of-magnitude savings in
the time needed to search a space satisfying this assumption.

Prepared by Asit Das 52

 Depth Limited search(DLS)

• A DLS algorithm is similar to DFS with a predetermined limit.

• DLS can solve the drawback of the infinite path in the DFS.
• In this algorithm, the node at the depth limit will treat as it has no successor nodes
further.
DLS can be terminated with two Conditions of failure:
• Standard failure value: It indicates that problem does not have any solution.
• Cutoff failure value: It defines no solution for the problem within a given depth
limit.
Advantages:
• Depth-limited search is Memory efficient.
Disadvantages:
• Depth-limited search also has a disadvantage of incompleteness.
• It may not be optimal if the problem has more than one solution.

Prepared by Asit Das 53

Example:

Completeness: DLS search

algorithm is complete if the solution
is above the depth-limit.

Time Complexity: Time complexity

of DLS algorithm is O(bℓ).

Space Complexity: Space complexity

of DLS algorithm is O(b×ℓ).

Optimal: DLS can be viewed as a

special case of DFS, and it is also not
optimal even if ℓ>d.

Prepared by Asit Das 54

 Issues in design of heuristics
A heuristic evaluation or design should not replace usability testing. Although the
heuristics relate to criteria that affect your site’s usability, the issues identified in a
heuristic design are different than those found in a usability test.

Advantages Disadvantages

•It can provide some quick and relatively

inexpensive feedback to designers.
•It requires knowledge and experience to
•You can obtain feedback early in the
apply the heuristics effectively.
design process.
•Trained usability experts are sometimes
•Assigning the correct heuristic can help
hard to find and can be expensive.
suggest the best corrective measures to
•You should use multiple experts and
designers.
aggregate their results.
•You can use it together with other
•The evaluation may identify more minor
usability testing methodologies.
issues and fewer major issues.
•You can conduct usability testing to
further examine potential issues.

Prepared by Asit Das 55

 Best First Search (Greedy Search)

• Best first or Greedy best-first search algorithm always selects the path which
appears best at that moment.
• It is the combination of DFS and BFS algorithms.
• It uses the heuristic function and search.
• Best-first search allows us to take the advantages of both algorithms.
• With the help of best-first search, at each step, we can choose the most promising
node.
• In the best first search algorithm, we expand the node which is closest to the goal
node.
• The closest cost is estimated by heuristic function, i.e.
f(n)= g(n)
• Where, h(n)= estimated cost from node n to the goal.
• The Best first search algorithm is implemented by the priority queue.

Prepared by Asit Das 56

Algo : Best first search
• Step 1: Place the starting node into the OPEN list.
• Step 2: If the OPEN list is empty, Stop and return failure.
• Step 3: Remove the node n, from the OPEN list which has the lowest value of h(n), and
places it in the CLOSED list.
• Step 4: Expand the node n, and generate the successors of node n.
• Step 5: Check each successor of node n, and find whether any node is a goal node or
not. If any successor node is goal node, then return success and terminate the search,
else proceed to Step 6.
• Step 6: For each successor node, checks for evaluation function f(n), and then check if
the node in either OPEN or CLOSED list. If the node has not been in both list, then add it
to the OPEN list.
• Step 7: Return to Step 2.
Advantages:
• Best first search can switch between BFS and DFS by gaining the advantages of both the algo.
• This algorithm is more efficient than BFS and DFS algorithms.
Disadvantages:
• It can behave as an unguided depth-first search in the worst case scenario.
• It can get stuck in a loop as DFS.
• This algorithm is not optimal.
Prepared by Asit Das 57
Example:
Consider the below search
problem, and we will traverse it
using greedy best-first search.
At each iteration, each node is
expanded using evaluation
function f(n)=h(n) , which is
given in the below table.

Time Complexity: The worst

case time complexity of
Greedy best first search is
O(bm).

Space Complexity: The worst case space

complexity of Greedy best first search is
O(bm). Where, m is the maximum depth Complete: Greedy best-first search is also
of the search space. incomplete, even if the given state space is
Optimal: Greedy best first search finite.
algorithm is not optimal.

Prepared by Asit Das 58

In this search example, we are using two lists
which are OPEN and CLOSED Lists. Following
are the iteration for traversing the above
example.
Expand the nodes of S and put in the CLOSED
list

Initialization: Open [A, B], Closed [S]

Iteration 1: Open [A], Closed [S, B]

Iteration 2: Open [E, F, A], Closed [S, B]

: Open [E, A], Closed [S, B, F]

Iteration 3: Open [I, G, E, A], Closed [S, B, F]

: Open [I, E, A], Closed [S, B, F, G]

Hence the final solution path will be: S----> B----->F----> G

Prepared by Asit Das 59

Example-2

Prepared by Asit Das 60

Prepared by Asit Das 61
Prepared by Asit Das 62
Prepared by Asit Das 63
Prepared by Asit Das 64
 A* Search Algorithm
- A* search is the most commonly known form of best-first search.
- It uses heuristic function h(n), and cost to reach the node n from the start state g(n).
- It has combined features of UCS and greedy best-first search.
- A* search algorithm finds the shortest path through the search space using the
heuristic function.
- This search algorithm expands less search tree and provides optimal result faster.
- A* algorithm is similar to UCS except that it uses g(n)+h(n) instead of g(n).
- In A* search algorithm, we use search heuristic as well as the cost to reach the
node.
- Hence we can combine both costs as following, and this sum is called as a fitness
number.

Prepared by Asit Das 65

Algorithm : A* search
Step1: Place the starting node in the OPEN list.
Step 2: Check if the OPEN list is empty or not, if the list is empty then return failure and
stops.
Step 3: Select the node from the OPEN list which has the smallest value of evaluation
function (g+h), if node n is goal node then return success and stop, otherwise
Step 4: Expand node n and generate all of its successors, and put n into the closed list. For
each successor n', check whether n' is already in the OPEN or CLOSED list, if not then
compute evaluation function for n' and place into Open list.
Step 5: Else if node n' is already in OPEN and CLOSED, then it should be attached to the
back pointer which reflects the lowest g(n') value.
Step 6: Return to Step 2.
Advantages:
• A* search algorithm is optimal and complete.
• This algorithm can solve very complex problems.
Disadvantages:
• It does not always produce the shortest path as it mostly based on heuristics
• A* search algorithm has some complexity issues.
• The main drawback of A* is memory requirement.
Prepared by Asit Das 66
Example:

In this example, we will

traverse the given graph
using the A* algorithm. The
heuristic value of all states
is given in the below table
so we will calculate the f(n)
of each state using the
formula f(n)= g(n) + h(n),
where g(n) is the cost to
reach any node from start
state.

Here we will use OPEN and

CLOSED list.

Prepared by Asit Das 67

 Solution:

Initialization: {(S, 5)}

Iteration1: {(S--> A, 4), (S-->G, 10)}

Iteration2: {(S--> A-->C, 4), (S--> A--

>B, 7), (S-->G, 10)}

Iteration3: {(S--> A-->C--->G, 6), (S-->

A-->C--->D, 11), (S--> A-->B, 7), (S--
>G, 10)}

Iteration 4 : will give the final result,

as S--->A--->C--->G
it provides the optimal path with
cost 6.

Prepared by Asit Das 68

Points to remember:
- A* algorithm returns the path which occurred first, and it does not search for
all remaining paths.
- The efficiency of A* algorithm depends on the quality of heuristic.
- A* algorithm expands all nodes which satisfy the condition f(n)

Complete: A* algorithm is complete as long as:

- Branching factor is finite.
- Cost at every action is fixed.

Optimal: A* search algorithm is optimal if it follows below two conditions:

- Admissible: The first condition requires for optimality is that h(n) should be
an admissible heuristic for A* tree search.
- Consistency: Second required condition is consistency for only A* graph-search.

Time Complexity: Depends on heuristic function, and the number of nodes expanded is
exponential to the depth of solution d. So the time complexity is O(b^d), where b is the
branching factor.

Space Complexity: The space complexity of A* search algorithm is O(b^d)

Prepared by Asit Das 69
 AO* search
• AO* algorithm is a best first search algorithm.
• AO* algorithm uses the concept of AND-OR graphs to decompose any complex
problem given into smaller set of problems.
• AND-OR graphs are specialized graphs that are used in problems that can be
broken down into sub problems.
• AND side of the graph represent a set of task that need to be done to achieve the
main goal
• As the or side of the graph represent the different ways of performing task to
achieve the same main goal.
• The AO* algorithm is a knowledge-based search technique, meaning the start
state and the goal state is already defined.
• Best path is found using heuristics.
• The time complexity of the algorithm is significantly reduced due to the informed
search technique.
• Compared to the A* algorithm , AO* algorithm is very efficient in searching the
AND-OR trees very efficiently.

Prepared by Asit Das 70

 Example-

Working of AO algorithm:
• The AO* algorithm works on
the formula given below :
f(n) = g(n) + h(n)
where,
• g(n): The actual cost of traversal
from initial state to the current
state.
• h(n): The estimated cost of
traversal from the current state
to the goal state.
• f(n): The actual cost of traversal
from the initial state to the goal
state.

Above example all numbers in brackets are the heuristic value i.e h(n). Each edge is
considered to have a value of 1 by default.
Prepared by Asit Das 71
Step-1
Starting from node A, we first
calculate the best path.
f(A-B) = g(B) + h(B) = 1+4= 5 ,
- where 1 is the default cost
value of travelling from A to B
- 4 is the estimated cost from B
to Goal state

f(A-C-D) = g(C) + h(C) + g(D) +

h(D) = 1+2+1+3 = 7 ,
- Here we are calculating the
path cost as both C and D
because they have the AND-
Arc.
- The default cost value of
travelling from A-C is 1,
- From A-D is 1, but the
heuristic value given for C
and D are 2 and 3
respectively hence making
the cost as 7. Prepared by Asit Das 72
Step-2
Using the same formula as
step-1, the path is now
calculated from the B node,
f(B-E) = 1 + 6 = 7.
f(B-F) = 1 + 8 = 9
Hence, the B-E path has
lesser cost. Now the
heuristics have to be updated
since there is a difference
between actual and heuristic
value of B. The minimum cost
path is chosen and is updated
as the heuristic , in our case
the value is 7. And because of
change in heuristic of B there
is also change in heuristic of
A which is to be calculated
again.
f(A-B) = g(B) + updated((h(B))
= 1+7=8
Prepared by Asit Das 73
Step-3
Comparing path of f(A-B) and f(A-C-D) it
is seen that f(A-C-D) is smaller. Hence
f(A-C-D) needs to be explored.
Now the current node becomes C node
and the cost of the path is calculated,
f(C-G) = 1+2 = 3
f(C-H-I) = 1+0+1+0 = 2
f(C-H-I) is chosen as minimum cost path,
also there is no change in heuristic since
it matches the actual cost. Heuristic of
path of H and I are 0 and hence they are
solved, but Path A-D also needs to be
calculated , since it has an AND-arc.
f(D-J) = 1+0 = 1, hence heuristic of D
needs to be updated to 1. And finally the
f(A-C-D) needs to be updated.
f(A-C-D) = g(C) + h(C) + g(D) +
updated((h(D)) = 1+2+1+1 =5.

As we can see that the solved path is f(A-C-D).

Prepared by Asit Das 74
What is the difference between A* Algorithm and AO* algorithm?
• A* algorithm and AO* algorithm are used in the field of Artificial Intelligence.
• An A* algorithm is an OR graph algorithm while the AO* algorithm is an AND-OR
graph algorithm.
• A* algorithm guarantees to give an optimal solution while AO* doesn't . since AO*
doesn't explore all other solutions once it got a solution.
• A* algorithm provides with the optimal solution, whereas AO* stops when it finds
any solution.
• AO* algorithm requires lesser memory compared to A* algorithm.
• AO* algorithm doesn't go into infinite loop whereas the A* algorithm can go into
an infinite loop.

Prepared by Asit Das 75

 Hill Climbing

• Hill climbing algorithm is a local search algorithm which continuously moves in the
direction of increasing elevation/value to find the peak of the mountain or best
solution to the problem.
• It terminates when it reaches a peak value where no neighbor has a higher value.
• Hill climbing is used for optimizing the mathematical problems.
• One of the widely discussed examples of Hill climbing algorithm is Traveling-
salesman Problem in which we need to minimize the distance traveled by the
salesman.
• It is also called greedy local search as it only looks to its good immediate neighbor
state and not beyond that.
• A node of hill climbing algorithm has two components which are state and value.
• Hill Climbing is mostly used when a good heuristic is available.
• In this algorithm, we don't need to maintain and handle the search tree or graph
as it only keeps a single current state.

Prepared by Asit Das 76

Features of Hill Climbing:
Following are some main features of Hill Climbing Algorithm:
• Generate and Test variant:
-Hill Climbing is the variant of Generate and Test method.
-The Generate and Test method produce feedback which helps to decide
which direction to move in the search space.
• Greedy approach:
-Hill-climbing search moves in the direction which optimizes the cost.
• No backtracking:
-It does not backtrack the search space, as it does not remember
the previous states.

Prepared by Asit Das 77

 State-space Diagram for Hill Climbing
- State-space landscape is a graphical representation of the hill-climbing algorithm
- which is showing a graph between various states of algorithm and Objective function/Cost.
- On Y-axis we have taken the function which can be an objective function or cost function,
- state-space on the x-axis.
- If the function on Y-axis is cost then, the goal of search is to find the global minimum and local
minimum.
- If the function of Y-axis is Objective function, then the goal of the search is to find the global
maximum and local maximum.

Prepared by Asit Das 78

Different regions in the state space landscape:
• Local Maximum: Local maximum is a state which is better than its neighbor states, but there
is also another state which is higher than it.
• Global Maximum: Global maximum is the best possible state of state space landscape. It has
the highest value of objective function.
• Current state: It is a state in a landscape diagram where an agent is currently present.
• Flat local maximum: It is a flat space in the landscape where all the neighbor states of
current states have the same value.
• Shoulder: It is a plateau region which has an uphill edge.
Types of Hill Climbing Algorithm:
• Simple hill Climbing:
-Less time consuming and
- Less optimal solution and the solution is not guaranteed
• Steepest-Ascent hill-climbing:
- It examines all the neighboring nodes of the current state and
- selects one neighbor node which is closest to the goal state.
- This algorithm consumes more time as it searches for multiple neighbors
• Stochastic hill Climbing:
- Stochastic hill climbing does not examine for all its neighbor before moving.
- Rather, this search algorithm selects one neighbor node at random and decides
whether to choose it as a current state or examine another state.
Prepared by Asit Das 79
 Simulated Annealing (SA) in AI
• Simulated Annealing is a stochastic global search optimization algorithm.
• The algorithm is inspired by annealing in metallurgy where metal is heated to a
high temperature quickly, then cooled slowly, which increases its strength and
makes it easier to work with.
• It distinguishes between different local optima.
• SA is a memory less algorithm and does not use any information gathered during
search.
• SA is an iterative improvement algorithms.
Example:
- A typical example is the traveling salesman problem, which belongs to the NP-
complete class of problems.
- For these problems, there is a very effective practical algorithm called simulated
annealing (thus named because it mimics the process undergone by misplaced atoms
in a metal when its heated and then slowly cooled)

Prepared by Asit Das 80

There are a set of steps that are performed for simulated annealing in AI. These steps
can be summarized as follows:
• SA creates a trial point randomly.
• The algorithm selects the distance between the current point and the trial point
by a probability distribution.
• The scale of such distribution is temperature. With the annealing function trial,
point distribution distance is set.
• To keep the boundaries intact, the trial point is shifted gradually.
• The SA formula determines if the new point is better than the older or not.
• If the new point is better, it is made as a next point,
• while if the new point is worse, it can still be accepted depending upon the
simulated annealing acceptance function.
• A systematic algorithm gradually reduces the temperature selecting the best
point that gets generated in the process.
• The simulated annealing is concluded when it reaches the lowest minima or any
of the specific stopping criteria.

Prepared by Asit Das 81

 Constraint Satisfaction Problem (CSP)
• Constraint satisfaction means solving a problem under certain constraints or rules.
• Constraint satisfaction is a technique where a problem is solved when its values
satisfy certain constraints or rules of the problem.
• Such type of technique leads to a deeper understanding of the problem structure
as well as its complexity.
• Constraint satisfaction depends on three components, namely:
X: It is a set of variables.
D: It is a set of domains where the variables reside.
There is a specific domain for each variable.
C: It is a set of constraints which are followed by the set of variables
Solving Constraint Satisfaction Problems:
The requirements to solve a constraint satisfaction problem (CSP) is:
• A state-space
• The notion of the solution.
• A state in state-space is defined by assigning values to some or all variables such as
{X1=v1, X2=v2, and so on…}.

Prepared by Asit Das 82

Types of Domains in CSP:
Two types of domains which are used by the variables :
• Discrete Domain: It is an infinite domain which can have one state for multiple
variables.
For example, a start state can be allocated infinite times for each variable.
• Finite Domain: It is a finite domain which can have continuous states describing
one domain for one specific variable. It is also called a continuous domain.

Constraint Types in CSP

With respect to the variables, basically there are following types of constraints:
• Unary Constraints: It is the simplest type of constraints that restricts the value of a
single variable.
• Binary Constraints: It is the constraint type which relates two variables. A value x2
will contain a value which lies between x1 and x3.
• Global Constraints: It is the constraint type which involves an arbitrary number of
variables.

Prepared by Asit Das 83

CSP Problems
• Constraint satisfaction
includes those problems
which contains some
constraints while solving the
problem.
• CSP includes the following
problems:
• Graph Coloring: The problem
where the constraint is that
no adjacent sides can have
the same color.
• Sudoku Playing: The
gameplay where the • n-queen problem: In n-queen problem, the
constraint is that no number constraint is that no queen should be placed
from 0-9 can be repeated in either diagonally, in the same row or column.
the same row or column. • Crossword: In crossword problem, the constraint
is that there should be the correct formation of
the words, and it should be meaningful.

Prepared by Asit Das 84

 8-puzzle problem

• The puzzle can be solved by moving the tiles one by one in the single empty space
and thus achieving the Goal state.
• Instead of moving the tiles in the empty space we can visualize moving the empty
space in place of the tile.
• The empty space cannot move diagonally and can take only one step at a time.
• The 8-puzzle is a sliding puzzle that consists of a frame of numbered square tiles in
random order with one tile missing.
• The more general n-puzzle is a classical problem which can be solved using graph
search techniques.
• N-puzzle that consists of N tiles (N+1 titles with an empty tile) where N can be 8
• In our example N = 8. (that is square root of (8+1) = 3 rows and 3 columns)
• So, basically in these types of problems we have given a initial state or initial
configuration (Start state) and a Goal state or Goal Configuration.
• Here We are solving a problem of 8 puzzle that is a 3x3 matrix.

Prepared by Asit Das 85

 Initial state Goal state

Solution:
- The puzzle can be solved by moving the tiles one by one in the single empty space
and thus achieving the Goal state.
Rules of solving puzzle:
- Instead of moving the tiles in the empty space we can visualize moving the empty
space in place of the tile.
- The empty space can only move in four directions (Movement of empty space)
Up , Down, Right or Left
- The empty space cannot move diagonally and can take only one step at a time.

Prepared by Asit Das 86

• Breath First Search to solve Eight puzzle problem

Time complexity:
In worst case time
complexity in BFS
is O(b^d)
know as order of
b raise to power
d. In this
particular case it
is (3^20).

Note: If we solve this problem with depth first search, then it will go to depth instead of
exploring layer wise nodes. Prepared by Asit Das 87
 To solve the problem
with Heuristic search or
informed search :
Heuristic values of each
node to calculate cost
function. (f=g+h)

Note: See the initial state and

goal state carefully all values
except (4,5 and 8) are at their
respective places.
so, the heuristic value for first
node is 3.
(Three values are misplaced to
reach the goal).
And let's take actual cost (g)
according to depth.

Prepared by Asit Das 88

 Crypt-arithmatic Problem

- Cryptarithmetic Problem is a type of CSP, where the game is about digits and its
unique replacement either with alphabets or other symbols.
- In this problem, the digits (0-9) get substituted by some possible alphabets or
symbols.
- The task in cryptarithmetic problem is to substitute each digit with an alphabet to
get the result arithmetically correct.
The rules or constraints on a cryptarithmetic problem are as follows:
• There should be a unique digit to be replaced with a unique alphabet.
• The result should satisfy the predefined arithmetic rules, i.e., 2+2 =4, nothing else.
• Digits should be from 0-9 only.
• There should be only one carry forward, while performing the addition operation
on a problem.
• The problem can be solved from both sides, i.e., L.H.S or R.H.S
• Let’s understand the cryptarithmetic problem as well its constraints better with
the help of an example:

Prepared by Asit Das 89

Example 1: S E N D + M O R E = M O N E Y
Solution: Starting from the left hand side (L.H.S) , the terms are S and M. Assign a
digit which could give a satisfactory result. Let’s assign S->9 and M->1.

Hence, we get a satisfactory result by adding

up the terms and got an assignment for O as
O->0 as well.

Now, move ahead to the next terms E and O to get N

as its output.

Adding E and O, which means 5+0=0, which

is not possible because according to
cryptarithmetic constraints, we cannot
assign the same digit to two letters. So, we
need to think more and assign some other
value.

Note: When we will solve further, we will get one carry, so after applying it, the answer
will be satisfied. Prepared by Asit Das 90
Further, adding the next two terms N and R we
get,

But, we have already assigned E->5. Thus, the

above result does not satisfy the values
Again, after solving the whole problem, we will get a carryover on this term, so our
answer will be satisfied

where 1 will be carry forward to the

above term
Prepared by Asit Das 91
Again, on adding the last
two terms, i.e., the
rightmost terms D and E,
we get Y as its result.

where 1 will be carry forward

to the above term

Keeping all the constraints in mind, the final resultant is as follows:

The representation of the assignment of the

digits to the alphabets.

Prepared by Asit Das 92

More examples of crypt-arithmatic problems can be:

Solve these two in your paper

Prepared by Asit Das 93