ARTIFICIAL INTELLIGENCE

COMPLETE STUDY NOTES

PART 1: BASIC CONCEPTS
For Data Science Internships & Placements

Simple enough for a 15-year-old | Powerful enough for interviews

📚 What's Inside — Basic Part

This document covers 7 foundational AI topics with 10 sections each:

• Topic 1: What is Artificial Intelligence?

• Topic 2: Intelligent Agents
• Topic 3: Breadth-First Search (BFS)
• Topic 4: Depth-First Search (DFS)
• Topic 5: A* Search Algorithm
• Topic 6: Hill Climbing Search
• Topic 7: Simulated Annealing

Each topic includes: Definition, Explanation with Example, Mathematical Formula,

Interview Q&A, Common Mistakes, When to Use/Not Use, Diagram Description,
Python Code, Quick Revision Summary, and Algorithm Comparison.

🔑 How to Use These Notes

• First read — go top to bottom, understand each concept

• For revision — jump to Section 9 (Quick Revision) of each topic
• Before interview — focus on Sections 4 (Interview Q&A) and 5 (Mistakes)
• For coding practice — copy Section 8 (Python Code) and run it
 PART 1 — BASIC CONCEPTS
MODULE 1: Introduction to Artificial Intelligence

Topic 1: What is Artificial Intelligence?

1. Definition
📖 Definition

Artificial Intelligence (AI) is the science of making machines (computers) think and act like
humans — solving problems, learning from experience, understanding language, and
making decisions.

2. Explanation with Example

Imagine your brain helping you decide what to eat for lunch. You look at the options, remember what
you liked before, and choose the best meal. AI tries to make computers do exactly this — but for any
kind of task!

AI systems are built to do things that normally require human intelligence like: recognizing faces in
photos (used in your phone's camera), recommending movies on Netflix, detecting spam emails,
driving self-driving cars, and answering your questions (like this AI!).

Example: When you type 'pizza near me' in Google Maps, the AI understands your request (natural
language), finds your location, searches nearby restaurants, ranks them by rating and distance, and
shows you results. All of this happens in milliseconds — that's AI working for you!

There are two ways AI can reason: (1) Optimal Reasoning — finding the mathematically best answer
(like a chess engine calculating millions of moves ahead), and (2) Human-like Reasoning — making
good-enough decisions quickly, like how we use shortcuts or 'gut feelings'. Both approaches are useful
in different situations.

3. Mathematical Formula
📐 Formula

AI = f(perception, reasoning, learning, action)

Performance Measure (PEAS Framework):

P = Performance measure (how well the agent does)
E = Environment (where the agent operates)
 A = Actuators (what the agent uses to act)
S = Sensors (how the agent perceives the world)

Turing Test: A machine passes if a human cannot distinguish its responses from a human's

4. Real Data Scientist Interview Questions & Answers

Q1: What is the difference between Artificial Intelligence and Machine Learning?
A: AI is the broad concept of machines performing tasks that require human-like intelligence.
Machine Learning is a subset of AI where machines learn from data without being explicitly
programmed. Think of AI as the goal and ML as one of the tools to achieve that goal. For example,
spam detection = AI goal; training a classifier on email data = ML approach.
Q2: Can you explain the PEAS framework with an example?
A: PEAS stands for Performance, Environment, Actuators, Sensors. For a self-driving car: P = safe,
fast, legal driving; E = roads, traffic, pedestrians; A = steering wheel, brakes, accelerator; S =
cameras, GPS, radar. It helps define what an intelligent agent needs to do its job effectively.
Q3: What are the main goals of AI?
A: The main goals are: (1) Thinking humanly — cognitive modelling, (2) Thinking rationally — laws of
logic, (3) Acting humanly — passing the Turing Test, (4) Acting rationally — doing the right thing to
maximize a goal. Data scientists mostly care about the fourth: building systems that act rationally to
maximize performance on a given task.

5. Common Mistakes to Avoid

⚠️Watch Out!

• ❌ Thinking AI = just coding if-else rules. Real AI learns from data!

• ❌ Confusing AI, ML, and Deep Learning. Remember: AI > ML > Deep Learning
(nested subsets)
• ❌ Assuming AI always finds the perfect/optimal answer — it often finds 'good enough'
answers
• ❌ Ignoring the environment — AI performance depends heavily on the data it was
trained on
• ❌ Thinking AI is magic — it's math, statistics, and code working together

6. When to Use vs When NOT to Use

✅ USE When... ❌ DO NOT USE When...
Task is too complex for manual rules Task has simple, fixed rules
Large amounts of data are available Data is very limited
Pattern recognition is needed Perfect accuracy is required (AI can make
mistakes)
Speed and scale are important Interpretability is critical (some AI is a 'black box')
Real-time decision making required Budget/computation is very limited
7. Visual / Diagram Description
Diagram Description

Picture a tree with 'AI' as the trunk. The first big branch is 'Machine Learning'. From that
branch grows a smaller branch: 'Deep Learning'. Other branches from AI include: Expert
Systems, Robotics, Natural Language Processing, Computer Vision.

At the roots of the tree: Mathematics, Statistics, Computer Science, Psychology, Philosophy.

At the leaves (applications): Chatbots, Self-driving cars, Medical diagnosis,

Recommendation systems, Fraud detection.

8. Python Code Snippet

# Simple AI decision example (rule-based)
def should_take_umbrella(weather):
if weather == 'rainy':
return True
elif weather == 'cloudy':
return True # maybe take it
else:
return False

# ML approach: learn from past weather data

from [Link] import DecisionTreeClassifier
import numpy as np

# Features: [temperature, humidity, cloud_cover]

X_train = [Link]([[20, 80, 90], [30, 40, 10], [22, 75, 85]])
y_train = [Link]([1, 0, 1]) # 1=umbrella, 0=no umbrella

model = DecisionTreeClassifier()
[Link](X_train, y_train)
print([Link]([[21, 78, 88]])) # Output: [1] - take umbrella!

9. Quick Revision Summary

🚀 Quick Recap

• ⭐ AI = making machines think and act intelligently

• ⭐ Key areas: Search, Knowledge Representation, ML, Planning, NLP
• ⭐ PEAS framework defines an intelligent agent's requirements
• ⭐ AI vs ML vs Deep Learning: nested subsets
• ⭐ Optimal reasoning = best answer; Human-like = fast, good enough

10. Comparison with Similar Algorithms

Feature Rule-Based AI Machine Learning AI Deep Learning AI
How it learns Manually coded rules Learns from data Learns from massive
data via neural networks
Data needed None Medium amount Very large amount
Example Spam filter with Spam filter with ML Image recognition
keywords
Flexibility Low Medium High
Explainability Very easy to explain Moderate Hard (black box)
 Topic 2: Intelligent Agents
1. Definition
📖 Definition

An Intelligent Agent is any entity (software, robot, or system) that: (1) PERCEIVES its
environment through sensors, (2) PROCESSES the information using AI, and (3) ACTS
upon the environment through actuators to achieve a GOAL.

2. Explanation with Example

Think of an intelligent agent like a smart security guard. The guard (agent) watches the premises
(perceives using cameras/eyes), decides if something is suspicious (processes), and calls the police or
locks doors (acts). That's exactly how an AI agent works!

Types of Agents explained simply:

• Simple Reflex Agent: Like a thermostat — if temp < 20°C → turn on heater. Reacts to current situation
only. No memory.
• Model-Based Agent: Like a chess player who remembers previous moves. Has an internal model of
the world.
• Goal-Based Agent: Like a GPS navigation system. Knows the goal (destination) and plans how to
reach it.
• Utility-Based Agent: Like a smart GPS that considers traffic, fuel, and time — picks the BEST route.
Maximizes a utility score.
• Learning Agent: Like Netflix recommendations — gets smarter over time by learning from your
choices.

Real example: Google Maps is a goal-based + utility-based agent. It perceives your location (sensors =
GPS), has a goal (reach destination), and picks the best route considering traffic, distance, and time
(utility).

3. Mathematical Formula
📐 Formula

Agent Function: f: P* → A
Where P* = sequence of percepts (all observations so far)
A = action to take

Rational Agent: chooses action that MAXIMIZES expected performance

Rationality = arg max E[Performance | percept_sequence, action]

PEAS: Performance | Environment | Actuators | Sensors

4. Real Data Scientist Interview Questions & Answers
Q1: What is a rational agent and how does it differ from an omniscient agent?
A: A rational agent chooses the best action based on available information to maximize expected
performance. An omniscient agent would know everything and always make perfect decisions — but
that's impossible in the real world. For example, a weather prediction AI (rational) makes the best
forecast from current data; an omniscient AI would know exactly if it will rain. Data scientists build
rational agents because perfect knowledge is rarely available.
Q2: Can you design a simple intelligent agent for product recommendations?
A: Yes! Sensors: User's browsing history, purchase data, ratings. Performance measure: Click-
through rate, purchase conversions. Environment: E-commerce website. Actuators: Display product
recommendations. The agent type would be Learning Agent — it improves recommendations by
learning from which suggestions users actually clicked. Technically it'd use collaborative filtering or a
neural network.
Q3: What is the difference between a goal-based and utility-based agent?
A: A goal-based agent knows what goal to achieve (reach point B) but doesn't care HOW it gets
there. A utility-based agent assigns a score to different paths and picks the highest scoring one. In
practice: A basic GPS is goal-based (just find ANY route); Google Maps is utility-based (find the
BEST route by scoring time, traffic, distance, tolls).

5. Common Mistakes to Avoid

⚠️Watch Out!

• ❌ Assuming all agents are the same — different types exist for different tasks
• ❌ Ignoring the environment type — a fully observable environment needs different
strategies than a partial one
• ❌ Confusing sensors with input features — they are analogous, but sensors is the
agent-level term
• ❌ Building a simple reflex agent when memory (model-based) is needed — agent will
fail in dynamic tasks
• ❌ Forgetting that rational ≠ perfect — rational just means 'best given what it knows'

6. When to Use vs When NOT to Use

✅ USE When... ❌ DO NOT USE When...
Automating repetitive tasks (bots) Static data analysis (use statistical tools instead)
Real-time decision making (trading algorithms) One-time computations (no need for ongoing
perception)
Games (chess, video game NPCs) When the environment is fully predictable and
never changes
Recommendation systems When budget is too limited for real-time
processing
Robot navigation/control Safety-critical systems without human oversight
7. Visual / Diagram Description
Diagram Description

Draw a circle in the center labeled 'AGENT'. Draw arrows pointing INTO the circle labeled
'Percepts' (from the environment). Draw arrows pointing OUT labeled 'Actions' (back to
environment).

Surround the agent with a large box labeled 'ENVIRONMENT'. Add: 'Sensors' on the input
side, 'Actuators' on the output side.

For agent types, draw a pyramid: Bottom layer = Simple Reflex, Next = Model-Based, Next =
Goal-Based, Next = Utility-Based, Top = Learning Agent. Complexity increases upward,
flexibility increases upward.

8. Python Code Snippet

# Simulating an Intelligent Agent

class SimpleReflexAgent:
def __init__(self):
[Link] = {'dirty': 'clean', 'clean': 'move'}

def perceive(self, environment_status):

return environment_status # sensor reading

def act(self, percept):

action = [Link](percept, 'idle')
return action

# Simulate a vacuum cleaner agent

agent = SimpleReflexAgent()
rooms = ['dirty', 'clean', 'dirty']

for i, room in enumerate(rooms):

percept = [Link](room)
action = [Link](percept)
print(f'Room {i+1}: status={percept}, action={action}')
# Room 1: status=dirty, action=clean
# Room 2: status=clean, action=move
# Room 3: status=dirty, action=clean

9. Quick Revision Summary

🚀 Quick Recap

• ⭐ Agent = perceive + process + act in an environment

• ⭐ 5 types: Simple Reflex, Model-Based, Goal-Based, Utility-Based, Learning
• ⭐ Rational agent maximizes expected performance (not always perfect)
• ⭐ PEAS = Performance, Environment, Actuators, Sensors — always define these first
• ⭐ Learning agents improve over time — most modern AI systems are this type
10. Comparison with Similar Algorithms
Agent Type Memory? Knows Goal? Optimizes? Example
Simple Reflex No No No Thermostat
Model-Based Yes No No Robot vacuum
Goal-Based Yes Yes No Basic GPS
Utility-Based Yes Yes Yes Google Maps
Learning Agent Yes Yes Yes + Learns Netflix AI
 MODULE 2: Search Algorithms

Topic 3: Breadth-First Search (BFS)

1. Definition
📖 Definition

Breadth-First Search (BFS) is a graph/tree traversal algorithm that explores all neighbor
nodes at the current level (depth) BEFORE moving deeper. It searches level by level,
starting from the root, using a QUEUE data structure.

2. Explanation with Example

Imagine you lost your keys in your house. You search your house floor by floor (level by level): first all
rooms on Floor 1, then all rooms on Floor 2, etc. That's exactly how BFS works — it's thorough and
guaranteed to find the shortest path!

How BFS works step by step:

1. Start at the root/starting node
2. Add it to a QUEUE (think of a line at a movie theater — first in, first out)
3. Remove the first node from the queue
4. Add all its unvisited neighbors to the queue
5. Repeat until you find the goal or the queue is empty

Example: Social network — 'Find all friends within 2 connections from Rahul':
Level 0: Rahul (start)
Level 1: Priya, Arjun, Simran (direct friends)
Level 2: Kiran, Dev, Meera (friends of friends)

BFS would visit Level 1 completely before touching Level 2. It guarantees finding the CLOSEST
connection first — which is why LinkedIn shows '2nd connection' vs '3rd connection'!

Time Complexity: O(V + E) where V = vertices (nodes), E = edges (connections). Space: O(V).

3. Mathematical Formula
📐 Formula

Time Complexity: O(b^d)

b = branching factor (average number of children per node)
d = depth of the shallowest goal node
 Space Complexity: O(b^d) ← stores all nodes at the current level

Completeness: YES — always finds a solution if one exists

Optimality: YES — finds shortest path (if all edges have equal cost)

4. Real Data Scientist Interview Questions & Answers

Q1: When would you use BFS over DFS in a real-world problem?
A: Use BFS when you need the shortest path in an unweighted graph, like finding the minimum
number of steps in a puzzle, or finding the closest friend on a social network. Use DFS when memory
is limited or you need to explore all possibilities without caring about depth. Classic BFS example:
finding the minimum number of moves in a word ladder puzzle (cat→bat→bad→…).
Q2: What are the limitations of BFS for large graphs?
A: BFS stores ALL nodes at the current level in memory. If the branching factor b=10 and depth d=6,
that's 10^6 = 1 million nodes in memory! This makes it impractical for very large/deep graphs. In
practice, solutions like Bidirectional BFS (searching from both ends) or A* are used when the state
space is huge — like route planning for a city.
Q3: Is BFS always optimal? Explain with an example.
A: BFS is optimal ONLY when all edge weights are equal (unweighted graph). If edges have different
costs, BFS might find a path with fewer steps that's actually more expensive. Example: Route A has
3 roads but all are highways (fast). Route B has 2 roads but with heavy traffic. BFS picks Route B
(fewer steps) even though A is better. For weighted graphs, use Dijkstra's or A* instead.

5. Common Mistakes to Avoid

⚠️Watch Out!

• ❌ Using a STACK instead of a QUEUE (that's DFS, not BFS!)

• ❌ Not marking nodes as visited — this causes infinite loops in cyclic graphs
• ❌ Assuming BFS works for weighted graphs — it doesn't find optimal path if weights
differ
• ❌ Confusing Time Complexity O(V+E) for graphs vs O(b^d) for trees
• ❌ Forgetting that BFS can be very memory-hungry for wide/deep graphs

6. When to Use vs When NOT to Use

✅ USE When... ❌ DO NOT USE When...
Finding SHORTEST path in unweighted graphs Weighted graphs (use Dijkstra's or A*)
Social network: degrees of separation Very deep or infinite state spaces (memory
explodes)
Web crawlers exploring pages level by level When memory is limited
GPS navigation on unweighted maps When you only need ANY path, not shortest
Solving puzzles like Rubik's cube (minimum Very large graphs where approximate solutions
 moves) are ok

7. Visual / Diagram Description

Diagram Description

Draw a tree with Root at top. Level 0: Node A. Level 1: Nodes B, C. Level 2: Nodes D, E, F,
G.

BFS visits in this order: A → B → C → D → E → F → G (left to right, level by level).

Next to the tree, draw a QUEUE box showing nodes being added and removed:
Start: Queue = [A]
Process A: Queue = [B, C]
Process B: Queue = [C, D, E]
Process C: Queue = [D, E, F, G]
...and so on

Use different colors for each level: Level 0 = Blue, Level 1 = Green, Level 2 = Orange.

8. Python Code Snippet

from collections import deque

def bfs(graph, start, goal):

queue = deque([[start]]) # queue of paths
visited = set([start])

while queue:
path = [Link]() # FIFO - first in, first out
node = path[-1] # last node in current path

if node == goal:
return path # found shortest path!

for neighbor in [Link](node, []):

if neighbor not in visited:
[Link](neighbor)
[Link](path + [neighbor])

return None # no path found

# Example: Social network connections

network = {
'Rahul': ['Priya', 'Arjun'],
'Priya': ['Kiran', 'Dev'],
'Arjun': ['Simran'],
'Kiran': [], 'Dev': [], 'Simran': []
}

path = bfs(network, 'Rahul', 'Dev')

print(f'Shortest path: {path}') # ['Rahul', 'Priya', 'Dev']
 print(f'Degrees of separation: {len(path)-1}') # 2

9. Quick Revision Summary

🚀 Quick Recap

• ⭐ BFS uses a QUEUE — explores level by level (breadth first)

• ⭐ Guarantees SHORTEST path in unweighted graphs
• ⭐ Time & Space: O(b^d) — can be memory-heavy
• ⭐ Always mark visited nodes to avoid infinite loops
• ⭐ Best for: social networks, web crawlers, minimum-step puzzles

10. Comparison with Similar Algorithms

Feature BFS DFS A* Search
Data structure Queue (FIFO) Stack (LIFO) Priority Queue
Shortest path? YES (unweighted) NO YES (weighted)
Memory usage HIGH - O(b^d) LOW - O(bd) MEDIUM
Completeness YES NO (infinite graphs) YES
Speed Slower (wide) Faster (deep) Fastest (heuristic)
Best for Fewest steps Exploring all paths Real-world navigation
 Topic 4: Depth-First Search (DFS)
1. Definition
📖 Definition

Depth-First Search (DFS) is a search algorithm that explores as FAR as possible along each
branch before backtracking. It goes DEEP into one path until it reaches a dead end, then
backtracks and tries another path. Uses a STACK data structure.

2. Explanation with Example

Imagine you're exploring a maze. DFS strategy: always take the first available turn, keep going forward
until you hit a wall, then backtrack to the last junction and try a different turn. You go DEEP into the
maze before trying alternatives.

How DFS works step by step:

1. Start at the root/start node — push to STACK
2. Pop the top node from the stack
3. If it's the goal, done! If not, push all its unvisited neighbors
4. Continue until goal found or stack is empty

Real example: File system search. When Windows searches for a file called '[Link]', it goes into
C:\Users\, then Documents\, then Work\, then deep into each subfolder — that's DFS! It fully explores
one folder path before trying another.

DFS can be done RECURSIVELY (the function calls itself) which is elegant but can cause stack
overflow for very deep trees. Iterative DFS uses an explicit stack to avoid this.

Time: O(V+E) for graphs, O(b^m) for trees where m = max depth. Space: O(bm) — much better than
BFS!

3. Mathematical Formula
📐 Formula

Time Complexity: O(b^m)

b = branching factor, m = maximum depth of the tree

Space Complexity: O(b*m) ← only stores current path + alternatives

This is MUCH better than BFS which needs O(b^d)

Completeness: NO for infinite depth spaces (can get lost forever)

Optimality: NO — finds A solution, not the BEST solution
4. Real Data Scientist Interview Questions & Answers
Q1: When would DFS be preferred over BFS in a data science context?
A: DFS is preferred when: (1) Memory is limited — DFS uses O(bm) vs BFS's O(b^d) space. (2) You
need to find ANY solution, not the shortest. (3) Exploring decision trees — DFS naturally fits tree
structures. (4) Topological sorting of workflows/pipelines. In data science, DFS is used in feature
selection trees, dependency resolution, and network analysis where you follow chains of connections
deeply.
Q2: What is backtracking and how does it relate to DFS?
A: Backtracking is DFS's superpower — when DFS hits a dead end (no more unvisited neighbors), it
automatically goes back to the previous node and tries a different path. It's like using an eraser on a
wrong answer and trying again. In data science, backtracking is used in hyperparameter optimization
(trying one combination deeply, backing off if it fails), constraint satisfaction problems, and solving
Sudoku puzzles computationally.
Q3: Can DFS handle cyclic graphs? How?
A: Without modification, DFS will loop forever in cyclic graphs (A→B→A→B…). The fix is simple:
maintain a 'visited' set. Before visiting any node, check if it's already in the visited set. If yes, skip it. If
no, add it and continue. This is always required when implementing DFS on real-world graphs like
social networks, web links, or road maps.

5. Common Mistakes to Avoid

⚠️Watch Out!

• ❌ Not tracking visited nodes in cyclic graphs — causes infinite loops

• ❌ Using DFS when you need the shortest/optimal path — DFS won't guarantee that
• ❌ Stack overflow in recursive DFS for very deep trees — use iterative DFS instead
• ❌ Forgetting to backtrack properly in recursive implementations
• ❌ Assuming DFS is always slower than BFS — for deep solutions, DFS is faster

6. When to Use vs When NOT to Use

✅ USE When... ❌ DO NOT USE When...
Topological sorting of tasks/dependencies Need SHORTEST path (use BFS or A*)
Detecting cycles in graphs Infinite or very deep search spaces without depth
limit
Solving mazes and puzzles (any solution needed) Wide but shallow trees (BFS is better)
Tree traversals (in-order, pre-order, post-order) When all solutions must be found quickly
Memory is limited (DFS uses much less than Real-time navigation (BFS or A* is better)
BFS)

7. Visual / Diagram Description

Diagram Description

Draw a tree: Root A, children B and C, B's children D and E, C's children F and G.
 DFS (starting from A, going left first) visits: A → B → D → [backtrack to B] → E → [backtrack
to A] → C → F → [backtrack to C] → G

Trace the path with an arrow going DOWN into D, then an arrow going UP back to B
(backtrack), then DOWN to E, then UP to A, then DOWN through C, F, G.

Show a STACK alongside: [A] → [B,C] → [D,E,C] → [E,C] → [C] → [F,G] → [G] → []

Color the backtrack arrows in red to make them visually distinct from forward arrows (in
blue).

8. Python Code Snippet

# DFS - Two ways to implement

# Method 1: Recursive (elegant but can overflow for deep trees)

def dfs_recursive(graph, node, visited=None):
if visited is None:
visited = set()
[Link](node)
print(f'Visiting: {node}')
for neighbor in [Link](node, []):
if neighbor not in visited:
dfs_recursive(graph, neighbor, visited)
return visited

# Method 2: Iterative with explicit Stack (safer for deep trees)

def dfs_iterative(graph, start, goal):
stack = [start]
visited = set()
path = []

while stack:
node = [Link]() # LIFO - last in, first out
if node in visited:
continue
[Link](node)
[Link](node)
if node == goal:
return path
for neighbor in reversed([Link](node, [])):
if neighbor not in visited:
[Link](neighbor)
return None

graph = {'A': ['B','C'], 'B': ['D','E'], 'C': ['F'], 'D':[],'E':[],'F':[]}

print(dfs_iterative(graph, 'A', 'F')) # ['A', 'C', 'F']

9. Quick Revision Summary

🚀 Quick Recap
 • ⭐ DFS uses a STACK — goes deep before going wide
• ⭐ Does NOT guarantee shortest path — finds any solution
• ⭐ Great memory efficiency: O(bm) vs BFS's O(b^d)
• ⭐ Always use visited set to avoid infinite loops in cyclic graphs
• ⭐ Best for: mazes, tree traversals, topological sort, cycle detection

10. Comparison with Similar Algorithms

Feature DFS BFS Iterative Deepening
(IDDFS)
Strategy Go deep first Go wide first DFS with depth limit
Memory O(bm) - LOW O(b^d) - HIGH O(bd) - LOW
Shortest path? NO YES YES
Complete? NO (infinite) YES YES
Best case Goal is deep Goal is shallow Unknown depth
 Topic 5: A* Search Algorithm
1. Definition
📖 Definition

A* (pronounced 'A-Star') is an informed search algorithm that finds the SHORTEST path
from a start to a goal by using a heuristic function to guide the search. It combines the
guarantees of BFS (optimal path) with the speed of heuristic search (intelligent direction).

2. Explanation with Example

Imagine Google Maps finding the best route from Mumbai to Pune. Instead of randomly trying all roads
(BFS), it intelligently focuses on roads that seem to head towards Pune. That's A* — it uses a 'smart
guess' (heuristic) to explore the most promising paths first!

A* uses a scoring formula: f(n) = g(n) + h(n)

g(n) = exact cost to reach node n from start (actual distance traveled)
h(n) = estimated cost from n to goal (heuristic — a smart guess)
f(n) = total estimated cost of best solution through n

A* explores nodes with the LOWEST f(n) first, using a Priority Queue.

Example: Finding the shortest path in a city grid:

g(n) = roads already traveled (exact)
h(n) = straight-line distance to destination (heuristic)

Common heuristics: Manhattan distance (for grids), Euclidean distance (for maps), Hamming distance
(for strings).

Key property: If h(n) NEVER overestimates the true cost (admissible heuristic), A* is GUARANTEED to
find the optimal path. This makes it both complete and optimal!

3. Mathematical Formula
📐 Formula

f(n) = g(n) + h(n)

g(n) = cost from start to node n (known, exact)
h(n) = estimated cost from n to goal (heuristic)
f(n) = total estimated path cost

Admissibility condition: h(n) <= h*(n) for all n

h*(n) = true cost to reach goal from n
If this holds, A* is OPTIMAL
 Manhattan Distance (grid): h(n) = |x1-x2| + |y1-y2|
Euclidean Distance (maps): h(n) = sqrt((x1-x2)^2 + (y1-y2)^2)

4. Real Data Scientist Interview Questions & Answers

Q1: What makes A* better than Dijkstra's algorithm?
A: Dijkstra's algorithm explores ALL nodes outward from the start equally (no direction preference).
A* uses a heuristic h(n) to focus exploration towards the goal, making it much faster in practice. If
h(n)=0 everywhere, A* becomes Dijkstra's. If h(n) is perfect (equals true cost), A* goes directly to goal
without exploring unnecessary nodes. For GPS navigation, A* is far more efficient than Dijkstra's.
Q2: What is an admissible heuristic? Give an example.
A: An admissible heuristic never overestimates the actual cost to reach the goal. Example: For a
GPS routing problem, straight-line (bird's eye) distance is admissible because actual road distance is
always >= straight-line distance. You can never travel LESS than the straight-line distance. If your
heuristic sometimes overestimates, A* might skip the optimal path and find a suboptimal one.
Q3: How would you apply A* in a recommendation system?
A: In content recommendation, think of 'interest state' as a graph. Start state = user's current
interests. Goal state = predicted content they'd love. g(n) = cost of showing n recommendations (user
fatigue, irrelevance score). h(n) = estimated remaining interest gap. A* navigates from current
preferences to ideal content recommendation path. More practically, A* is used in game AI
pathfinding which powers NPC movement in video games — directly applicable to simulation-based
recommendation testing.

5. Common Mistakes to Avoid

⚠️Watch Out!

• ❌ Using an inadmissible heuristic — A* may not find the optimal path

• ❌ Confusing g(n) and h(n): g is known/exact, h is estimated
• ❌ Not using a priority queue — A* requires ordering by f(n)
• ❌ Re-adding already-visited nodes to open list without checking
• ❌ Choosing h(n)=0 makes A* work but then it's just Dijkstra's (slower)

6. When to Use vs When NOT to Use

✅ USE When... ❌ DO NOT USE When...
GPS and map navigation (Google Maps, Uber When no good heuristic exists (use BFS or
routing) Dijkstra's)
Game pathfinding (character movement in Very large state spaces with no heuristic
games) guidance
Robot motion planning When heuristic computation is too expensive
Network routing protocols Unweighted graphs (BFS is simpler and equally
good)
Puzzle solving (15-puzzle, sliding tiles) Real-time systems where computation must be
 near-instant

7. Visual / Diagram Description

Diagram Description

Draw a grid (5x5). Mark S (Start) in top-left, G (Goal) in bottom-right. Some cells are walls
(black).

For each open cell, show two numbers: g (top-left, blue) and h (bottom-right, red). The f
value (green) = g + h shown in the cell center.

Draw the open list (priority queue) on the side, sorted by f value. Show A* picking the lowest-
f node each step.

Highlight the final optimal path in yellow. Compare it to a naive path (blue, longer) to show A*
finds better routes.

The key visual insight: A* expands fewer nodes than BFS because h(n) steers it toward the
goal.

8. Python Code Snippet

import heapq

def astar(grid, start, goal):

# h = Manhattan distance heuristic
def heuristic(a, b):
return abs(a[0]-b[0]) + abs(a[1]-b[1])

open_list = []
[Link](open_list, (0, start))
came_from = {}
g_cost = {start: 0}

while open_list:
f, current = [Link](open_list)

if current == goal:
# Reconstruct path
path = []
while current in came_from:
[Link](current)
current = came_from[current]
return path[::-1]

row, col = current

for dr, dc in [(-1,0),(1,0),(0,-1),(0,1)]: # 4 directions
neighbor = (row+dr, col+dc)
if 0<=neighbor[0]<len(grid) and 0<=neighbor[1]<len(grid[0]):
if grid[neighbor[0]][neighbor[1]] == 0: # not a wall
new_g = g_cost[current] + 1
if new_g < g_cost.get(neighbor, float('inf')):
 came_from[neighbor] = current
g_cost[neighbor] = new_g
f_val = new_g + heuristic(neighbor, goal)
[Link](open_list, (f_val, neighbor))
return None

# 0=open, 1=wall
grid = [[0,0,1,0],[0,0,0,0],[1,0,1,0],[0,0,0,0]]
path = astar(grid, (0,0), (3,3))
print(f'Path found: {path}') # Shortest path coordinates

9. Quick Revision Summary

🚀 Quick Recap

• ⭐ A* = BFS intelligence + heuristic guidance. Formula: f(n) = g(n) + h(n)

• ⭐ g(n) = exact cost traveled so far; h(n) = estimated cost to goal
• ⭐ Admissible heuristic = never overestimates → guarantees optimal path
• ⭐ Uses Priority Queue ordered by f(n) — always expands cheapest-seeming path
• ⭐ Used in GPS, games, robots. Most widely used pathfinding algorithm in practice

10. Comparison with Similar Algorithms

Feature BFS Dijkstra's A*
Uses weights? No Yes Yes
Uses heuristic? No No YES (key advantage)
Optimal path? Yes (unweighted) Yes Yes (if admissible h)
Speed Slow Medium Fast
Memory O(b^d) O(V) O(b^d) worst case
Use case Unweighted graphs Shortest path in graph Pathfinding with map
 MODULE 3: Local Search Algorithms

Topic 6: Hill Climbing Search

1. Definition
📖 Definition

Hill Climbing is a local search algorithm that continuously moves to a better neighboring
state, like climbing a hill towards the peak. It's greedy — at each step, it picks the neighbor
with the HIGHEST improvement. It has no memory of past states.

2. Explanation with Example

Imagine you're blindfolded on a hilly landscape and want to reach the highest point. You feel the
ground around you and step in whichever direction feels steepest uphill. That's hill climbing — always
move upward, step by step, until no neighboring direction is higher.

How it works:
1. Start with a random initial state (random position on the hill)
2. Look at all neighboring states
3. Move to the neighbor with the highest value (steepest ascent)
4. Repeat until no neighbor is better (you've reached a 'local peak')

The big problem: Local Maxima! The algorithm might stop at a small hill (local maximum) thinking it's
the top, when the actual highest peak is elsewhere.

Real-world example: Model hyperparameter tuning. Start with random learning_rate=0.1,

batch_size=32. Try nearby values. If learning_rate=0.05 gives better accuracy, move there. Keep
adjusting until no small tweak improves things — that's hill climbing for hyperparameter optimization!

Variants: Steepest Ascent (check all neighbors, pick best), Stochastic (pick random uphill neighbor),
Random Restart (restart from different points to escape local maxima).

3. Mathematical Formula
📐 Formula

Objective: maximize f(x) [or minimize, depending on problem]

Algorithm update rule:

x_next = arg max f(neighbor) for all neighbors of x_current
If f(x_next) > f(x_current): move to x_next
 Else: STOP (local maximum reached)

For minimization (loss in ML): move to neighbor with LOWEST f(n)

Gradient Ascent (continuous version):

x_new = x_old + alpha * gradient(f(x_old))
alpha = step size (learning rate)

4. Real Data Scientist Interview Questions & Answers

Q1: What are the three main problems with hill climbing?
A: (1) Local Maxima: Algorithm stops at a small peak, not the global highest peak. Like being stuck
on a small hill when Mount Everest is nearby. (2) Plateaus: A flat region where all neighbors have
equal value — the algorithm doesn't know which direction to go. (3) Ridges: A diagonal hill where
each step goes sideways but the peak is along the ridge. Solutions: Random Restart Hill Climbing
(try from multiple starting points), Simulated Annealing (accept worse moves with some probability).
Q2: How is gradient descent in machine learning related to hill climbing?
A: They're the same concept! Gradient descent is a continuous version of hill climbing (but for
minimization, not maximization). In ML, we minimize the loss function. Gradient descent: take the
gradient (slope) of the loss at current weights, step in the direction that DECREASES loss. Hill
climbing: check neighbors, move to the one that INCREASES the objective. Neural network training
IS hill climbing in a very high-dimensional space.
Q3: How would you implement random restart hill climbing for hyperparameter optimization?
A: Run hill climbing multiple times from different random starting points. Example: For tuning a
Random Forest, start 10 random configs (n_estimators, max_depth, min_samples). For each, hill
climb by tweaking one parameter at a time and keeping improvements. After all 10 runs, take the
best result. This is essentially what tools like Optuna and HyperOpt do — they implement random
restart + hill climbing variants for ML hyperparameter search.

5. Common Mistakes to Avoid

⚠️Watch Out!

• ❌ Getting stuck in local maxima and thinking the problem is solved

• ❌ Not implementing random restart — one run often gives suboptimal results
• ❌ Using hill climbing for problems with a flat landscape (plateaus everywhere)
• ❌ Forgetting hill climbing is memoryless — it doesn't remember paths it already tried
• ❌ Applying hill climbing to discrete problems where gradient isn't meaningful

6. When to Use vs When NOT to Use

✅ USE When... ❌ DO NOT USE When...
Hyperparameter optimization (learning rate, tree Problems with many local optima (will get stuck)
depth)
Feature selection in ML models When you need the guaranteed global optimum
 Scheduling optimization problems Problems with flat plateaus (no direction to move)
TSP (Travelling Salesman Problem) When the search space is small enough for
approximation exhaustive search
When you need a quick approximate solution When exact optimality is required

7. Visual / Diagram Description

Diagram Description

Draw a landscape (like rolling hills) on an X-Y chart. Y-axis = quality/fitness score. X-axis =
different states/solutions.

Mark: Global Maximum (tallest hill), Local Maximum (a smaller hill), Plateau (flat region),
Ridge (diagonal narrow peak).

Show a ball starting at the left. Arrow goes UP to the local maximum where it gets STUCK.
Another ball starts further right and climbs to the global maximum.

This illustrates why random restart is needed — starting position matters!

Add a separate mini-diagram showing Gradient Descent in ML: a bowl-shaped loss curve
with a ball rolling DOWN to the minimum (opposite of hill climbing — we minimize loss).

8. Python Code Snippet

import random

def objective(x):
# Example: maximize f(x) = -(x-3)^2 + 9 (peak at x=3)
return -(x - 3)**2 + 9

def get_neighbors(x, step=0.5):

return [x - step, x + step]

def hill_climbing(start_x, max_iter=100):

current = start_x
current_v = objective(current)

for _ in range(max_iter):
neighbors = get_neighbors(current)
best_n = max(neighbors, key=objective)
best_v = objective(best_n)

if best_v > current_v: # move uphill

current = best_n
current_v = best_v
else:
break # stuck at local/global max
return current, current_v

# Random Restart Hill Climbing

 best_x, best_val = None, float('-inf')
for _ in range(10): # 10 random restarts
start = [Link](-10, 10)
x, val = hill_climbing(start)
if val > best_val:
best_x, best_val = x, val

print(f'Best x: {best_x:.2f}, Best value: {best_val:.2f}')

# Output: Best x: 3.00, Best value: 9.00

9. Quick Revision Summary

🚀 Quick Recap

• ⭐ Hill climbing = always move to better neighbor, stop when no improvement

• ⭐ Greedy & memoryless — fast but can get stuck in local maxima
• ⭐ 3 problems: Local maxima, Plateaus, Ridges
• ⭐ Solution to local maxima: Random Restart (try multiple starting points)
• ⭐ Gradient Descent in ML = hill climbing (minimization version) in continuous space

10. Comparison with Similar Algorithms

Feature Hill Climbing Random Restart Simulated Genetic
HC Annealing Algorithm
Memory None None per restart None Population memory
Escapes local NO Sometimes YES (probabilistic) YES
max?
Speed Very Fast Fast Medium Slow
Optimality Not guaranteed Better chance Near-optimal Near-optimal
Complexity Very simple Simple Moderate Complex
 Topic 7: Simulated Annealing
1. Definition
📖 Definition

Simulated Annealing (SA) is an optimization algorithm inspired by the process of slowly

cooling molten metal (annealing). It's like hill climbing but with a twist: it sometimes accepts
WORSE solutions (with decreasing probability over time) to escape local optima and find the
global optimum.

2. Explanation with Example

Imagine a metal being heated and then slowly cooled. When very hot, atoms can move freely (we
explore widely). As it cools, atoms settle into a stable structure (we converge to a solution). Simulated
Annealing copies this process!

The key idea: At HIGH temperature, accept bad moves freely (explore). As temperature DECREASES,
accept bad moves less often (exploit). By the end, only accept improvements.

Why does accepting bad moves help? Because hill climbing can get stuck at a local maximum. By
sometimes moving DOWNHILL, SA can escape local traps and eventually find the global optimum.

Step-by-step:
1. Start with a random solution and high temperature T
2. Pick a random neighbor
3. If neighbor is better: always accept it
4. If neighbor is worse: accept it with probability = e^(-delta/T) where delta = how much worse
5. Slowly decrease T (cooling schedule)
6. Repeat until T is near zero

Real example: Chip layout design. Engineers use SA to place millions of transistors on a chip to
minimize wire length. Sometimes they temporarily accept a worse layout to explore new arrangements
— eventually finding a near-optimal chip design.

3. Mathematical Formula
📐 Formula

Acceptance Probability:
P(accept) = 1 if delta_E < 0 (new is BETTER)
P(accept) = e^(-deltaE/T) if delta_E > 0 (new is WORSE)
where deltaE = E(new) - E(current) [energy/cost difference]
T = current temperature
 Cooling Schedule (linear): T(t) = T_initial - alpha * t
Cooling Schedule (exponential): T(t) = T_initial * alpha^t
alpha = cooling rate (typically 0.95 to 0.99)

At high T: e^(-deltaE/T) is close to 1 → accept most bad moves

At low T: e^(-deltaE/T) is close to 0 → almost never accept bad moves

4. Real Data Scientist Interview Questions & Answers

Q1: What is the cooling schedule in simulated annealing and why does it matter?
A: The cooling schedule controls how fast temperature T decreases. (1) Too fast cooling: like hill
climbing — gets stuck in local optima. (2) Too slow cooling: wastes computation time exploring bad
solutions. Common choices: Exponential (T *= 0.95 each iteration) is most common and practical.
Linear (T -= constant) works for simple problems. The cooling schedule is a hyperparameter you tune
— like learning rate in neural networks. It directly determines solution quality vs computation time
tradeoff.
Q2: How does Simulated Annealing relate to Boltzmann distribution in physics?
A: Directly! In physics, the probability of a system being in a high-energy state at temperature T is
e^(-E/kT) (Boltzmann distribution). SA copies this — the probability of accepting a worse state (higher
energy) is e^(-deltaE/T). At high temperature, energy fluctuations are large (more exploration). As
T→0, the system settles into the lowest energy state (optimal solution). SA is literally physics-inspired
optimization.
Q3: For what type of problems is Simulated Annealing commonly used in industry?
A: SA is used for NP-hard combinatorial optimization problems where exact solutions are too
expensive. Examples: (1) VLSI chip design — placing components to minimize wire length. (2)
Traveling Salesman Problem — finding the shortest delivery route. (3) Job scheduling — assigning
tasks to minimize total completion time. (4) Portfolio optimization in finance — finding asset
allocations. (5) Neural architecture search — finding optimal network structures. When the search
space is discrete, combinatorial, and huge, SA is a go-to choice.

5. Common Mistakes to Avoid

⚠️Watch Out!

• ❌ Setting cooling rate too fast — algorithm becomes hill climbing, gets stuck
• ❌ Setting temperature too low at start — no exploration, like starting already cold
• ❌ Setting temperature too high and never cooling — random walk, no convergence
• ❌ Not tuning the cooling schedule — this is the most critical hyperparameter
• ❌ Forgetting that SA gives near-optimal, not guaranteed optimal results

6. When to Use vs When NOT to Use

✅ USE When... ❌ DO NOT USE When...
NP-hard combinatorial optimization (TSP, Simple problems where exact methods work
scheduling)
 When problem has many local optima When you need 100% guaranteed optimal
solution
Circuit and chip layout design Real-time applications (SA can be slow)
Protein structure prediction Smooth, convex problems (gradient descent is
better)
When approximate near-optimal solution is When computation time is extremely limited
acceptable

7. Visual / Diagram Description

Diagram Description

Draw two charts side by side:

Chart 1 (Temperature vs Time): A curve that starts HIGH and gradually decreases to near
zero — like a cooling curve. Mark 'High T = High exploration' at top and 'Low T =
Exploitation' at bottom.

Chart 2 (Solution Quality vs Time): A noisy/jagged line that starts low (random), has lots of
ups and downs in the beginning (exploring), but gradually trends upward, settling on a good
solution at the end.

Also draw a comparison landscape: Hill Climbing gets stuck at a small hill (red X). SA has a
dotted path that sometimes goes DOWN (accepting worse moves) before finding the global
peak (green checkmark).

8. Python Code Snippet

import math, random

def simulated_annealing(problem, T_initial=1000, T_min=0.01, alpha=0.95):

current = problem.random_solution()
current_val = [Link](current)
best = current
best_val = current_val
T = T_initial
iteration = 0

while T > T_min:

neighbor = problem.get_neighbor(current)
neighbor_val = [Link](neighbor)
delta = neighbor_val - current_val

# Accept if better OR with probability e^(-delta/T)

if delta > 0 or [Link]() < [Link](delta / T):
current, current_val = neighbor, neighbor_val

if current_val > best_val: # track global best

best, best_val = current, current_val

T *= alpha # cool down (exponential schedule)

iteration += 1
 return best, best_val

# Quick TSP-like demo with a simple number problem

class NumberProblem:
def random_solution(self): return [Link](-10, 10)
def evaluate(self, x): return -(x-3)**2 + 9 # peak at x=3
def get_neighbor(self, x): return x + [Link](-0.5, 0.5)

best_x, best_v = simulated_annealing(NumberProblem())

print(f'Best x: {best_x:.3f}, Best value: {best_v:.3f}')
# Output: Best x: ~3.000, Best value: ~9.000

9. Quick Revision Summary

🚀 Quick Recap

• ⭐ Simulated Annealing = Hill Climbing + ability to escape local optima

• ⭐ Key idea: Accept worse solutions with probability e^(-deltaE/T)
• ⭐ High temperature = explore freely; Low temperature = exploit best found
• ⭐ Cooling schedule (alpha) is the critical hyperparameter
• ⭐ Best for: TSP, chip design, scheduling — large combinatorial optimization

10. Comparison with Similar Algorithms

Feature Hill Climbing Simulated Annealing Genetic Algorithm
Accepts worse moves? NEVER YES (probabilistically) YES
(crossover/mutation)
Escapes local optima? NO YES YES
Population? Single solution Single solution Multiple solutions
Computation Very fast Moderate Slower
Tuning needed? Minimal Cooling schedule Many parameters
Guaranteed optimal? NO NO NO
 MASTER CHEAT SHEET — BASIC AI
Algorithm Key Idea Data Optimal? Memory Best Use
Structure Case
BFS Level by level Queue (FIFO) YES HIGH O(b^d) Shortest path,
(unweighted) social networks
DFS Go deep first Stack (LIFO) NO LOW O(bm) Cycle detection,
topological sort
A* f=g+h guided Priority Queue YES (if MEDIUM GPS routing,
admissible h) game
pathfinding
Hill Climbing Greedy ascent None (local NO NONE Hyperparamete
moves) r tuning
Simul. HC + bad None (local Near-optimal NONE TSP, chip
Annealing moves moves) layout,
scheduling

🎯 Interview Quick Hits — Remember These!

• AI vs ML vs DL: AI is the goal, ML is one method, DL is a subset of ML

• PEAS = Performance, Environment, Actuators, Sensors — always define for any agent
problem
• BFS = Queue, DFS = Stack, A* = Priority Queue — data structure is the key difference
• A* formula: f(n) = g(n) + h(n) — always know this by heart
• Admissible heuristic: h(n) never overestimates → A* is optimal
• Hill Climbing problem: Local Maxima — fix with Random Restart
• Simulated Annealing: accept worse moves with P = e^(-deltaE/T) — higher T = more
accepting
• DFS is NOT optimal but uses less memory. BFS IS optimal but uses more memory
• Rational agent = acts to maximize expected performance given available info
• Heuristic = educated guess that guides search — not exact, but fast

Next: Part 2 (Intermediate) covers Games, CSP, Logic & Theorem Proving | Part 3 (Advanced) covers First-
Order Logic, Planning, Bayesian Networks