Unit: 1

1. Role of Algorithms in Computing

Main Points:

1. Definition
2. Importance of Algorithms
3. Relationship between Algorithm and Program
4. Efficiency and Optimization
5. Applications in Real Life

Detailed Explanation:

Main Point Sub Points Explanation

An algorithm is a finite, ordered sequence of well-defined
1. Definition - instructions designed to solve a specific problem. It is
independent of programming language.
a) Foundation of Every software program, mobile app, or AI model is based
2. Importance
Computing on algorithmic logic.
b) Structured Helps in dividing complex problems into smaller,
Problem Solving manageable steps.
3. Relationship between Algorithm is a blueprint; Program is its implementation in
-
Algorithm and Program a specific language like Python, C, etc.
4. Efficiency and a) Time
Reduces execution time.
Optimization Efficiency
b) Space
Uses minimum memory resources.
Efficiency
Used in searching, sorting, encryption, data compression, AI
5. Applications -
decision making, etc.

Diagram:
Problem Definition
↓
Algorithm Design
↓
Program Implementation
↓
Testing & Analysis
↓
Execution & Output
2. Algorithms
Main Points:

1. Definition
2. Characteristics of Good Algorithms
3. Steps in Algorithm Development
4. Example

Detailed Explanation:

Main Point Sub Points Explanation

An algorithm is a set of instructions to perform a task or solve a
1. Definition -
problem in a finite number of steps.
2. Characteristics a) Input Zero or more inputs must be provided.
b) Output Must produce at least one output.
c) Finiteness Must terminate after finite steps.
d) Definiteness Each instruction should be unambiguous.
e) Effectiveness Each operation should be basic and executable.
3. Steps in a) Problem
Identify input, process, and output.
Development Definition
b) Algorithm
Write logic in sequential form.
Design
c) Testing Check correctness with sample data.
d) Optimization Improve efficiency if needed.
Algorithm to find maximum of two numbers: Step 1: Read A, B
4. Example -
Step 2: If A > B, print A else print B Step 3: Stop

Flowchart:
Start
↓
Input A, B
↓
A > B ?
/ \
Yes No
| |
Print A Print B
↓
Stop
3. Algorithms as a Technology
Main Points:

1. Definition
2. Role in Modern Computing
3. Key Aspects of Algorithm Technology
4. Real-world Applications

Detailed Explanation:

Main Point Sub Points Explanation

Treating algorithms as a technology means focusing on
1. Definition -
performance, scalability, and adaptability.
2. Role in Modern
a) Software Efficiency Determines execution speed and responsiveness.
Computing
b) Scalability Efficient algorithms can handle large input sizes.
c) Cost Optimization Reduces resource and energy consumption.
3. Key Aspects a) Algorithm Design Crafting efficient logic.
b) Algorithm Analysis Measuring time and space complexity.
c) Algorithm
Applying algorithms in software systems.
Implementation
Used in AI, cryptography, data science, networking, and
4. Applications -
optimization problems.

Flowchart:
Algorithm Design → Analysis → Implementation → Testing → Deployment
4. Insertion Sort
Main Points:

1. Definition
2. Working Principle
3. Algorithm Steps
4. Example
5. Complexity Analysis
6. Advantages & Disadvantages

Detailed Explanation:

Main Point Sub Points Explanation

Insertion Sort is a simple
comparison-based sorting algorithm
1. Definition - that builds the sorted array one
element at a time by inserting each
new element into its correct position.
Similar to arranging playing cards in
2. Working Principle - hand — pick one card and insert it
into the correct position.
a) Start from index 1 (second
element). b) Compare it with elements
to its left. c) Shift greater elements
3. Algorithm Steps
one position ahead. d) Insert key in
correct position. e) Repeat till array
end.
For [5, 2, 4, 6, 1] → [2, 5, 4, 6, 1] →
4. Example -
[2, 4, 5, 6, 1] → [1, 2, 4, 5, 6]
a) Best Case: O(n) (sorted input). b)
5. Complexity Average Case: O(n²). c) Worst Case:
O(n²). d) Space: O(1).
6. + Simple, in-place sorting. –
Advantages/Disadvantages Inefficient for large datasets.

Flowchart:
Start
↓
For i = 1 to n-1
↓
Key = A[i]
↓
Compare with A[j]
↓
Shift elements > Key
↓
lInsert Key
↓
End For
↓
Stop
5. Analyzing Algorithms
Main Points:

1. Definition
2. Goals of Analysis
3. Types of Analysis
4. Parameters Measured

Detailed Explanation:

Main Point Sub Points Explanation

Algorithm analysis determines how
1. Definition - efficiently an algorithm performs in
terms of time and space.
a) Performance comparison between algorithms. b)
2. Goals
Predict behavior for large inputs.
a) Worst Case: Maximum time required (slowest
3. Types of
case). b) Average Case: Expected time for random
Analysis
inputs. c) Best Case: Minimum time for ideal input.
4. Parameters a) Time Complexity – Number of basic operations.
Measured b) Space Complexity – Amount of memory used.

Diagram:
Algorithm
↓
Input → Processing → Output
↓
Analyze Time & Space Requirements
6. Designing Algorithms
Main Points:

1. Definition
2. Algorithm Design Strategies
3. Design Steps
4. Verification and Validation

Detailed Explanation:

Main Point Sub Points Explanation

The process of
constructing efficient and
1. Definition - logical steps to solve a
given computational
problem.
a) Divide & Conquer – Divide problem into subproblems (e.g.,
Merge Sort). b) Greedy – Take locally optimal choices (e.g.,
2. Design
Kruskal’s Algorithm). c) Dynamic Programming – Store
Strategies
results of subproblems (e.g., Fibonacci). d) Backtracking – Try
all possibilities and backtrack if needed (e.g., N-Queens).
3. Design Problem Definition → Model Formulation → Algorithm
Steps Design → Analysis → Implementation.
Check correctness,
4.
- completeness, and
Verification
efficiency.

Flowchart:
Problem Definition → Strategy Selection → Algorithm Development → Analysis → Testing
7. Asymptotic Notation
Main Points:

1. Definition
2. Purpose
3. Types of Notations
4. Examples

Detailed Explanation:

Main
Sub Points Explanation
Point
Mathematical notations used to describe
1.
- growth rate of an algorithm’s running time
Definition
as input size increases.
Compares algorithm efficiency independent
2. Purpose -
of hardware or compiler.
a) Big O (O) – Upper bound / Worst-case. b)
3. Types Omega (Ω) – Lower bound / Best-case. c) Theta
(Θ) – Tight bound / Average-case.
4.
- Linear search: O(n), Ω(1), Θ(n/2).
Example

Diagram:
Ω(g(n)) ≤ Θ(g(n)) ≤ O(g(n))
8. Standard Notations
Main Points:

1. Definition
2. Types
3. Application in Analysis

Detailed Explanation:

Notation Meaning Mathematical Definition Example

O(g(n)) Upper bound f(n) ≤ c·g(n) for n ≥ n₀ f(n)=2n+3 = O(n)
Ω(g(n)) Lower bound f(n) ≥ c·g(n) for n ≥ n₀ f(n)=3n+2 = Ω(n)
Θ(g(n)) Tight bound c₁·g(n) ≤ f(n) ≤ c₂·g(n) f(n)=5n+2 = Θ(n)
o(g(n)) Non-tight upper bound f(n)/g(n) → 0 as n→∞ f(n)=n/logn = o(n)
ω(g(n)) Non-tight lower bound f(n)/g(n) → ∞ as n→∞ f(n)=n² = ω(n)

Table:

Notation Use Case Meaning

O Worst-case Maximum time
Ω Best-case Minimum time
Θ Average-case Typical case
9. Common Functions
Main Points:

1. Definition
2. Common Growth Functions
3. Growth Rate Comparison
4. Graphical Representation

Detailed Explanation:

Function Type Example Time Complexity Explanation

Constant Array access O(1) Executes in same time regardless of input.
Logarithmic Binary search O(log n) Time increases slowly with n.
Linear Linear search O(n) Time proportional to input size.
Quadratic Bubble Sort O(n²) Time grows with square of n.
Cubic Matrix Multiplication O(n³) Common in nested loops.
Exponential Tower of Hanoi O(2ⁿ) Time doubles with each increase in n.
Factorial Traveling Salesman O(n!) Grows extremely fast.

Graph:
Time ↑
|
| O(2ⁿ)
| O(n²)
| O(n log n)
| O(n)
| O(log n)
| O(1)
|______________________> Input Size (n)
 Unit: 2
1. The Maximum-Subarray Problem
Main Points:

1. Definition and Objective

2. Problem Statement and Example
3. Approaches to Solve
4. Divide and Conquer Solution
5. Pseudocode
6. Complexity Analysis
7. Applications

Sub Points with Explanation:

1 ⃣ Definition and Objective

 The Maximum Subarray Problem aims to find a contiguous subarray (containing at least one
element) which has the largest sum among all possible subarrays of a given array.
 It helps in analyzing gain/loss patterns, e.g., stock prices or temperature variations.

2 ⃣ Problem Statement and Example

Given an array A[1…n] of real numbers (positive or negative), find indices i and j such that the sum
A[i] + A[i+1] + … + A[j] is maximum.

Example:
A = [−2, 1, −3, 4, −1, 2, 1, −5, 4]
Maximum sum = 6 (subarray [4, −1, 2, 1])

3 ⃣ Approaches to Solve
Method Description Time Complexity

Brute Force Check all possible subarrays O(n²) or O(n³)

Divide & Conquer Split array into parts and combine O(n log n)

Kadane’s Algorithm Dynamic approach; track current and global sum O(n)

4 ⃣ Divide and Conquer Solution

 Divide: Split array into left and right halves.

 Conquer: Recursively find max subarray in left, right, and crossing middle.
 Combine: Return maximum of three.

Formula:
MaxSum = max(LeftSum, RightSum, CrossSum)
5 ⃣ Pseudocode
FIND-MAXIMUM-SUBARRAY(A, low, high)
if high == low:
return (low, high, A[low])
else:
mid = (low + high)//2
(left_low, left_high, left_sum) = FIND-MAXIMUM-SUBARRAY(A, low, mid)
(right_low, right_high, right_sum) = FIND-MAXIMUM-SUBARRAY(A, mid+1, high)
(cross_low, cross_high, cross_sum) = FIND-MAX-CROSSING-SUBARRAY(A, low, mid,
high)
if left_sum ≥ right_sum and left_sum ≥ cross_sum:
return (left_low, left_high, left_sum)
elif right_sum ≥ left_sum and right_sum ≥ cross_sum:
return (right_low, right_high, right_sum)
else:
return (cross_low, cross_high, cross_sum)

6 ⃣ Complexity Analysis

 Recurrence: T(n) = 2T(n/2) + Θ(n)

 Using Master Theorem: T(n) = Θ(n log n)

7 ⃣ Applications

 Stock market profit prediction

 Climate data variation analysis
 Financial gain/loss analysis

Flowchart:
Start
↓
Divide array into two halves
↓
Find max subarray (Left, Right)
↓
Find max crossing subarray
↓
Compare and return maximum
↓
End
2. Strassen’s Algorithm for Matrix Multiplication
Main Points:

1. Need for Faster Multiplication

2. Concept and Formulae
3. Steps of Algorithm
4. Pseudocode
5. Complexity Analysis
6. Applications

Sub Points with Explanation:

1 ⃣ Need for Faster Multiplication

 Conventional matrix multiplication takes O(n³) time.

 Strassen’s algorithm reduces it to O(n^2.81) by minimizing multiplications.

2 ⃣ Concept and Formulae

For two matrices:

A = |a b| B = |e f|
|c d| |g h|

Compute:

M1 = (a + d)(e + h)
M2 = (c + d)e
M3 = a(f - h)
M4 = d(g - e)
M5 = (a + b)h
M6 = (c - a)(e + f)
M7 = (b - d)(g + h)

Then:

C11 = M1 + M4 - M5 + M7
C12 = M3 + M5
C21 = M2 + M4
C22 = M1 - M2 + M3 + M6

3 ⃣ Steps of Algorithm

1. Divide matrices A and B into four submatrices each.

2. Compute seven products (M1–M7) recursively.
3. Use results to compute final matrix C.

4 ⃣ Pseudocode
STRASSEN(A, B):
if size(A) == 1:
return A * B
else:
divide A, B into submatrices
compute M1 to M7
combine them to form C
return C
5 ⃣ Complexity Analysis

Recurrence: T(n) = 7T(n/2) + O(n²)

By Master Theorem → T(n) = O(n^2.81)

6 ⃣ Applications

 Graphics rendering
 Scientific simulations
 Machine learning matrix operations

Diagram:
A (2x2) + B (2x2)
↓
Divide into submatrices
↓
Compute M1–M7
↓
Combine into C (result)
3. The Substitution Method for Solving
Recurrences
Main Points:

1. Definition
2. General Approach
3. Steps in Substitution Method
4. Example
5. Advantages

Sub Points with Explanation:

1 ⃣ Definition

 The substitution method is used to prove asymptotic bounds (O, Ω, Θ) for recurrences by guessing
the form of solution and proving by induction.

2 ⃣ General Approach

Used for recurrences like:

T(n) = aT(n/b) + f(n)

3 ⃣ Steps

1. Guess the form of T(n).

2. Use induction hypothesis to prove the inequality.
3. Find constants that satisfy the inequality.

4 ⃣ Example

Given: T(n) = 2T(n/2) + n

Guess: T(n) = O(n log n)

Proof:

T(n) ≤ 2c(n/2) log(n/2) + n

= cn log n - cn log 2 + n
≤ cn log n

✅ Proven.

5 ⃣ Advantages

 Simple and intuitive.

 Works well for recurrences with known patterns.

Flowchart:
Guess → Substitute → Simplify → Verify by Induction → Proved
4. The Recursion-Tree Method for Solving
Recurrences
Main Points:

1. Definition
2. Steps to Construct Tree
3. Calculation of Total Cost
4. Example
5. Advantage

Sub Points with Explanation:

1 ⃣ Definition

Visual method to estimate the total cost of a recurrence by drawing a tree where each node represents
subproblem cost.

2 ⃣ Steps

1. Draw root with cost of main problem.

2. Expand children according to recursive calls.
3. Continue until smallest subproblem.
4. Add costs across all levels.

3 ⃣ Example

T(n) = 2T(n/2) + n
Each level contributes cost n.

Level Nodes Cost per Node Total Cost

0 1 N n

1 2 n/2 n

2 4 n/4 n

... ... ... ...

Total = n log n.

4 ⃣ Advantage

 Easy to visualize recursive cost distribution.

 Helpful before applying the master theorem.

Diagram:
n
/ \
n/2 n/2
 / \ / \
n/4 n/4 n/4 n/4
5. The Master Method for Solving Recurrences
Main Points:

1. Definition
2. General Form
3. Three Cases
4. Examples
5. Advantages

Sub Points with Explanation:

1 ⃣ Definition

The Master Theorem provides an asymptotic bound for recurrences of the form:
T(n) = aT(n/b) + f(n)

2 ⃣ Parameters

 a = Number of subproblems
 b = Size shrink factor
 f(n) = Additional work outside recursion

3 ⃣ Cases
Case Condition Result

1 f(n) = O(n^(log_b a - ε)) T(n) = Θ(n^(log_b a))

2 f(n) = Θ(n^(log_b a)) T(n) = Θ(n^(log_b a) log n)

3 f(n) = Ω(n^(log_b a + ε)), regularity holds T(n) = Θ(f(n))

4 ⃣ Example

T(n) = 2T(n/2) + n → a=2, b=2

n^(log_b a) = n
→ Case 2 → T(n) = Θ(n log n)

5 ⃣ Advantages

 Direct and quick method.

 Avoids manual proof.

Flowchart:
Identify a, b, f(n)
↓
Compute n^(log_b a)
↓
Compare f(n) with n^(log_b a)
↓
Apply Case 1 / 2 / 3
↓
Get Asymptotic Bound
6. The Hiring Problem
Main Points:

1. Definition
2. Algorithm
3. Analysis (Worst and Expected Case)
4. Randomization Aspect
5. Applications

Sub Points with Explanation:

1 ⃣ Definition

 Classic example showing expected analysis in randomized algorithms.

 Task: Hire the best candidate sequentially; interview each one.

2 ⃣ Algorithm

1. Interview each candidate.

2. Hire if candidate better than all previous ones.
3. Continue till end.

3 ⃣ Analysis

 Worst case: All candidates are increasing order → n hires.

 Expected case: ≈ ln(n) hires.

Mathematically:
E[hires] = 1 + 1/2 + 1/3 + … + 1/n = Hn ≈ ln(n)

4 ⃣ Randomization Aspect

If candidates appear in random order, expected number of hires reduces drastically.

5 ⃣ Applications

 Real-world employee selection

 Randomized search and selection

Flowchart:
Start
↓
Interview candidate i
↓
Is candidate better than current best?
↙ ↘
Yes No
Hire new best Next candidate
↓
Repeat till all
↓
End
7. Indicator Random Variables
Main Points:

1. Definition
2. Purpose
3. Example (Hiring Problem)
4. Properties

Sub Points with Explanation:

1 ⃣ Definition

Indicator Random Variable (IRV) takes:

1 → if event occurs
0 → otherwise

2 ⃣ Purpose

Simplifies computation of expected values in probabilistic algorithms.

3 ⃣ Example

In the hiring problem:

Let Xi = 1 if ith candidate is hired.
Then total hires = X1 + X2 + ... + Xn
E[X] = ∑(1/i) = ln(n)

4 ⃣ Properties

 E[X] = Probability(Event occurs)

 Useful in analyzing expected cost/time of randomized algorithms.

Table:

Candidate Event (Hire?) Xi Contribution

1 Yes 1 1

2 No 0 0

3 Yes 1 1

... ... ... ...

8. Randomized Algorithms
Main Points:

1. Definition
2. Classification
3. Advantages and Disadvantages
4. Common Examples
5. Applications

Sub Points with Explanation:

1 ⃣ Definition

Algorithms that make random choices during execution to improve performance or average-case behavior.

2 ⃣ Classification
Type Description Example

Las Vegas Always correct result; time varies Randomized QuickSort

Monte Carlo Fixed time; result may be wrong Primality testing

3 ⃣ Advantages

 Simpler logic.
 Efficient for large datasets.
 Often faster in practice.

4 ⃣ Disadvantages

 May produce different outputs on different runs.

 Harder to debug.

5 ⃣ Applications

 Cryptography (key generation)

 Randomized QuickSort and Selection
 Machine learning sampling

Diagram:
Input → Random Number Generator → Algorithm → Randomized Output
 Unit: 3
1. Rod Cutting — Detailed Explanation
✅ Main Points

1. Introduction & Problem Definition

2. Economic Importance (Real-world use)
3. Optimal Substructure
4. Overlapping Subproblems
5. Dynamic Programming Solution
6. Top-down vs Bottom-up Approach
7. Time Complexity & Applications

1. Introduction & Problem Definition

Rod Cutting is a classic DP problem.

You are given a rod of length n and a price list for each length.
The aim is to determine maximum revenue possible by cutting the rod optimally.

Sub-points

 Input: rod length n + price list

 Output: maximum revenue
 Decision: where to cut the rod
 Constraint: unlimited cuts allowed

2. Economic Importance

Rod cutting models real industries (steel, plastic, wood) where raw materials are cut for profit.

Sub-points

 Maximize Profit: choose best piece size

 Avoid Wastage: compute efficient cuts
 Optimization: commercial use

3. Optimal Substructure

The optimal revenue for rod length n depends on best revenue of smaller lengths.

Sub-points

 Try all possible cuts: 1 to n

 Recurrence:
r(n) = max(p[i] + r(n-i))
 Best global solution = best of local choices

4. Overlapping Subproblems

Smaller subproblems (like r(3), r(4)) repeat.

Sub-points

 Inefficient recursion repeats work

 DP avoids recomputation
 Store values in table

5. Dynamic Programming Solutions

(a) Top-down with Memoization

 Recursion + storage
 Compute only needed values

(b) Bottom-up

 Build table from length 1 to n

 Always more efficient

6. Top-down vs Bottom-up (Table)

Feature Top-down Bottom-up

Approach Recursion Iteration

Memory Memo table DP table

Calls On demand All subproblems solved

Speed Faster than pure recursion Fastest

7. Time Complexity

 Pure recursion: O(2ⁿ)

 DP (top-down or bottom-up): O(n²)

✅ Rod Cutting Flowchart

Start
↓
Input n and price list
↓
Initialize DP table R[0..n]
↓
For i = 1 to n:
For j = 1 to i:
R[i] = max(R[i], price[j] + R[i-j])
↓
Output R[n]
↓
End
2. Matrix-Chain Multiplication (MCM) —
Detailed
✅ Main Points

1. Introduction & Goal

2. Matrix Multiplication Cost
3. Parenthesization Importance
4. Optimal Substructure
5. DP Recurrence Relation
6. DP Tables (m and s)
7. Algorithm Complexity

1. Introduction & Goal

MCM finds the most efficient way to multiply a chain of matrices.

Sub-points

 Matrices multiply only if dimensions match

 Order affects cost
 We must minimize scalar multiplications

2. Matrix Multiplication Cost

Multiplying A(p × q) and B(q × r) costs:

✔ p × q × r multiplications

3. Parenthesization Importance

Different parenthesization → different costs.

Example:
(A₁A₂)A₃ ≠ A₁(A₂A₃) in cost.

4. Optimal Substructure

To compute cost from i to j:

Choose best split at k: i ≤ k < j

Recurrence:
m[i,j] = min ( m[i,k] + m[k+1,j] + p[i-1]*p[k]*p[j] )

5. DP Tables

Two tables used:

(a) m[i,j] = minimum cost

(b) s[i,j] = split position

✅ Matrix-Chain Cost Table Diagram

i\j 1 2 3 4

1 0 18000 44000 66000

2 —0 9000 27000

3 —— 0 24000

4 —— — 0

6. Algorithm Complexity

 Using DP: O(n³) time

 Space: O(n²)

✅ Flowchart for MCM

Start
↓
Input matrix dimensions
↓
Initialize m[i,i] = 0
↓
For chain length = 2 to n:
For i = 1 to n-L+1:
j = i + L - 1
For k = i to j-1:
compute cost
update m[i,j]
↓
Print optimal cost & parenthesization
↓
End
3. Elements of Dynamic Programming — Detailed
✅ Main Points

1. Optimal Substructure
2. Overlapping Subproblems
3. State Definition
4. Recursive Relation
5. Table Construction
6. Choice Between Approaches
7. Applications

1. Optimal Substructure

Solution of problem depends on solutions of subproblems.

Example: LCS, MCM, Rod cutting.

2. Overlapping Subproblems

Same subproblems solved repeatedly.

DP saves time by storing answers.

3. State Definition

State represents a subproblem.

Examples:

 LCS[i,j] → LCS of X[1..i] and Y[1..j]

 MCM[i,j] → min cost of multiplying matrix i to j

4. Recursive Relation

Core of DP.

Example:
dp[i] = dp[i-1] + dp[i-2]

5. Table Construction

 1D for simple DP
 2D for complex DP

✅ Flowchart of Generic DP
Define DP state → Build Recurrence → Create Table → Fill Table → Output Result
4. Longest Common Subsequence (LCS) —
Detailed
✅ Main Points

1. Definition
2. Difference between Subsequence & Substring
3. Optimal Substructure
4. DP Recurrence
5. Constructing LCS Table
6. Backtracking to find LCS
7. Applications

1. Definition

LCS: longest sequence present in both strings not necessarily contiguous.

2. Subsequence vs Substring (Table)

Feature Subsequence Substring

Contiguous No Yes

Example ABC from AXBYC BY

3. Optimal Substructure

 If characters match → include

 If not → choose maximum of two choices

Recurrence:
If X[i]=Y[j] → L[i,j] = 1 + L[i-1,j-1]
Else → L[i,j] = max(L[i-1,j], L[i,j-1])

4. DP Table Example
ØACGT

Ø0 0 00 0

A 0 1 11 1

G0 1 12 2

T 0 1 12 3

5. Backtracking

Start from bottom-right and move:

  Diagonal ← match
 Up/Left ← choose larger

✅ LCS Flowchart
Start → Fill LCS matrix →
Check characters →
Match → diagonal move →
No match → max(up,left) →
Reconstruct string → End
5. Optimal Binary Search Trees (OBST) —
Detailed
✅ Main Points

1. Introduction
2. Probabilities Used
3. Cost Definition
4. Optimal Substructure
5. DP Recurrence
6. DP Tables
7. Use Cases

1. Introduction

OBST finds a BST with minimum expected search time using probabilities.

2. Probabilities

 pᵢ = probability of successful search

 qᵢ = probability of unsuccessful search between keys

3. Cost Definition

The expected cost of searching in OBST:

e[i,j] = expected cost of searching keys from i to j

w[i,j] = sum of probabilities in subtree

4. Optimal Substructure

Each chosen root divides the problem into:

 Left subtree optimal

 Right subtree optimal

5. Recurrence
e[i,j] = min ( e[i,r-1] + e[r+1,j] + w[i,j] )

✅ OBST Table Diagram

i\j 0 1 2 3

0 e00 e01 e02 e03

1 — e11 e12 e13

2 — — e22 e23

3 — — — e33
6. Applications

 Auto-completion systems
 Dictionary search
 Syntax parsing
 Databases
 Unit: 4
✅ 1. 0/1 Knapsack Problem — Detailed Notes (7-
Marks)
Main Points with Detailed Sub-Points
1. Problem Definition (Detailed)

The knapsack problem is an optimization problem where we have a set of items and a bag (knapsack) with
a fixed capacity.

Sub-Points

✅ 1.1 Objective Function

 Aim: Maximize total profit or value placed in the knapsack.

 If item i has profit Pi and weight Wi, we want to select items such that
Total Profit = Σ Pi (selected items)
is maximum.

✅ 1.2 Constraint (Capacity Limit)

 The total weight of selected items must not exceed the knapsack capacity W.
 That is:
Σ Wi ≤ W
 This constraint makes the problem computationally challenging.

2. Problem Characteristics (Detailed)

✅ 2.1 Binary Decision Nature (0/1 Choice)

 Every item must be either fully taken (1) or left (0).

 No partial selection is allowed (unlike fractional knapsack).

✅ 2.2 Optimal Substructure

 Optimal solution to the entire problem contains optimal solutions to subproblems.

 If item i is chosen or not chosen → remaining problem is smaller.

✅ 2.3 Overlapping Subproblems

 Subproblems repeat during recursion.

 Example: computing knapsack(remaining_items, remaining_capacity) is reused.

3. Dynamic Programming Solution (Detailed)

✅ 3.1 DP Table Construction

  Create DP table K[n+1][W+1]
where n = number of items
W = capacity.
 Row = items considered
 Column = capacity considered
 Entry = best profit at that combination.

✅ 3.2 Recurrence Relation

If weight of item i (Wi) ≤ current capacity (w):

K[i][w] = max(
Pi + K[i-1][w-Wi], // take item
K[i-1][w] // do not take item
)

Else:

K[i][w] = K[i-1][w]

✅ 3.3 Time & Space Complexity

 Time: O(nW)
 Space: O(nW)
 Efficient for moderate constraints.

4. Applications (Detailed)

✅ 4.1 Budget Allocation

Selecting projects with limited budget.

✅ 4.2 Resource Allocation

Choosing tasks when CPU/memory is limited.

✅ 4.3 Cargo Loading

Maximizing profit under weight restrictions in aircraft/trucks.

✅ Diagram — Fully Detailed DP Table

Items → 0 1 2 3 4 ... Capacity W
-----------------------------------------
0 items | 0 0 0 0 0
1 item | 0 P1 P1 P1 P1
2 items | 0 P1 max(P2,P1) ...
3 items | ...
2. Job Sequencing with Deadlines — Detailed
Notes
Main Points with Expanded Sub-Points
1. Problem Definition (Detailed)

We are given n jobs, each having:

 a profit (Pi)
 a deadline (Di)
 takes 1 unit time

Objective:
✅ Select jobs such that total profit is maximum and
✅ each job is completed within its deadline

2. Characteristics (Detailed)

✅ 2.1 One Unit Time Jobs

Each job takes exactly 1 time slot.

✅ 2.2 Profit Maximization Problem

Higher profit jobs should get priority.

✅ 2.3 Greedy Strategy

Sort jobs in decreasing order of profit → try to schedule most profitable jobs first.

3. Steps of Greedy Algorithm (Detailed)

✅ 3.1 Sort Jobs

 Order jobs by profit descending.

 Highest profit job is attempted first.

✅ 3.2 Create Time Slot Array

If max deadline = Dmax

Create array slot[Dmax] initially empty.

✅ 3.3 Allocate Jobs

For each job:

 Find latest available slot ≤ deadline

 If slot empty → schedule job.

Example:
J1 (profit 100, deadline 2)
J2 (profit 80, deadline 1)
J3 (profit 50, deadline 3)

✅ Flowchart — Detailed
Start
|
Input (jobs with P, D)
|
Sort jobs by profit ↓
|
For each job in sorted list
|
Find latest free slot ≤ deadline
| |
Yes free No free
| |
Assign job Skip job
|
Continue
|
Print Scheduled Jobs + Max Profit
|
End
3. Activity Selection Problem — Detailed Notes
1. Problem Definition (Detailed)

Given a set of activities with:

 Start times
 Finish times

Goal:
✅ Select maximum number of non-overlapping activities.

2. Greedy Choice (Detailed)

✅ Earliest Finish Time Rule

Pick the activity that finishes earliest because:

 Leaves room for more activities

 Ensures maximum compatibility

3. Greedy Algorithm Steps (Detailed)

✅ 3.1 Sort Activities by Finish Time

Smallest finishing time first.

✅ 3.2 Select First Activity

Let it be A1 → Add to output list.

✅ 3.3 For Each Remaining Activity

If start_time ≥ finish_time(previous_selected)
→ Select activity.

✅ Diagram — Detailed Timeline

Activity: A1 A2 A3 A4
Start: 1 3 6 2
Finish: 3 4 9 8

Sorted by finish time:

A1 (1-3)
A2 (3-4)
A4 (2-8)
A3 (6-9)

Select:
A1 → A2 → A3
4. Elements of the Greedy Strategy — Detailed
Notes
1. Greedy Choice Property (Detailed)

A globally optimal solution can be reached by:

✅ Making a locally best choice first

Example:
Activity with earliest finish → gives best possible future choices.

2. Optimal Substructure (Detailed)

Greedy algorithms work only if:

 After making a choice,

 Remaining problem also has an optimal solution.

3. Greedy Algorithm Framework

✅ 3.1 Define Objective

Define what must be minimized or maximized.

✅ 3.2 Make a Greedy Choice

Pick best candidate according to greedy criteria.

✅ 3.3 Feasibility Check

Ensure adding this choice does not violate constraints.

✅ 3.4 Commit Irrevocably

Greedy does not backtrack → once chosen, cannot undo.

✅ 3.5 Solve Remaining Subproblem

Apply same logic to remaining items.

✅ Flowchart — Greedy Strategy Framework

Start
|
Identify all feasible choices
|
Select best local choice (Greedy Choice)
|
Check if choice is valid/feasible
|
Add to solution
|
Reduce/Transform remaining problem
 |
If remaining problem exists → repeat
|
End
5. Growing a Minimum Spanning Tree (MST) —
Detailed Notes
✅ Main Points with Detailed Sub-Points
1. Definition of MST (Detailed)

Given a connected, undirected, weighted graph G(V,E):

 A Spanning Tree is a subset of edges that connects all vertices with no cycles.
 A Minimum Spanning Tree is a spanning tree with minimum total edge weight.

✅ Sub-Point 1.1: Requirements of MST

 Includes all vertices

 Contains exactly |V| – 1 edges
 No cycles
 Minimum sum of weights

2. Approaches to Grow an MST

Two most popular MST algorithms:

 ✅ Kruskal’s Algorithm — grows MST by adding edges

 ✅ Prim’s Algorithm — grows MST by expanding a tree vertex-by-vertex

3. Cut Property (Detailed)

A cut divides vertices into two disjoint sets.

✅ Sub-Point 3.1 Safe Edge

The lightest edge across any cut that respects the existing partial MST is always safe to add.

Importance:

 Helps in selecting correct edges

 Ensures we do not form cycles
 Guarantees MST construction correctness

4. Cycle Property

Adding the heaviest edge in any cycle will never be part of an MST.

✅ Diagram — MST Growth Concept

Initial Graph
A--2--B
| |
3 1
| |
C--4--D

Growing MST:
Step 1: Select lightest edge → B-D (1)
Step 2: Next lightest → A-B (2)
Step 3: Next lightest → A-C (3)

MST Completed: 3 edges

6. Kruskal’s Algorithm — Detailed Notes
1. Idea (Detailed)

Kruskal’s algorithm builds MST by:

 Selecting the smallest edges first

 Ensuring no cycles form
 Using Disjoint Set (Union-Find) to track components

2. Step-by-Step Process

✅ 2.1 Sort All Edges

Arrange edges in increasing weight order.

✅ 2.2 Take Edge One by One

Pick the smallest edge:

 If it does not form a cycle, add to MST

 Else skip

✅ 2.3 Use Union-Find

To check cycles efficiently:

 Find() → identifies component

 Union() → merges two components

3. Time Complexity

 Sorting: O(E log E)

 Union-Find: Almost O(1)
Total: O(E log E)

✅ Flowchart — Kruskal’s Algorithm

Start
|
Sort edges by weight
|
For each edge (u,v):
|
If Find(u) ≠ Find(v)
|
Add edge to MST
|
Union(u, v)
|
Until MST has V-1 edges
|
End
7. Prim’s Algorithm — Detailed Notes
1. Idea (Detailed)

Prim’s algorithm grows MST like Dijkstra:

 Starts from any vertex

 At each step, adds the minimum weight edge connecting visited → unvisited vertex.

2. Step-by-Step Process

✅ 2.1 Initialize

 Choose any starting vertex

 Mark it as included
 Use Priority Queue to select min edge

✅ 2.2 Expand Tree

Repeat:

 Pick smallest weight edge from PQ

 Edge must connect included → not included
 Add vertex
 Insert new outgoing edges into queue

3. Time Complexity

Using min-heap: O(E log V)

Using adjacency matrix: O(V²)

✅ Diagram — Prim’s MST Growth

Start at A
Edges from A: A-B (2), A-C (3)
Choose A-B (2)
Now from A,B choose lowest edge: B-D (1)
Now choose A-C (3)
MST built
8. Bellman–Ford Algorithm — Detailed Notes
1. Purpose (Detailed)

Find Shortest Paths from a single source to all vertices in a graph that may contain:

✅ Negative weight edges

❌ But no negative cycles reachable from source

2. Key Concepts

✅ 2.1 Relaxation

Relaxing edge (u,v) with weight w:

if dist[v] > dist[u] + w:

dist[v] = dist[u] + w

✅ 2.2 Negative Cycle Detection

After V−1 relaxations, perform one more full relaxation:

 If any value updates → negative cycle exists.

3. Algorithm Steps

✅ 3.1 Initialization

 dist[source] = 0
 dist[others] = ∞

✅ 3.2 Relax All Edges V–1 Times

Each iteration reduces shortest path lengths.

✅ 3.3 Check for Negative Cycle

4. Time Complexity

O(V × E)

Flowchart — Bellman–Ford Algorithm

Start
|
Initialize distances
|
Repeat V-1 times:
Relax all edges
|
Check for negative cycle
|
Output distances
|
End
9. Single-Source Shortest Paths in DAG —
Detailed Notes
1. Key Requirement

Graph must be a Directed Acyclic Graph (DAG).

2. Idea (Detailed)

Since DAG has no cycles:

 Perform Topological Sort

 Relax edges in that order
 Guarantees correct shortest path in linear time

3. Steps

✅ 3.1 Topological Sort

Order nodes so all edges go from left to right.

✅ 3.2 Relax Edges in Topo Order

For each vertex u in topo order:

Relax all outgoing edges (u,v).

4. Time Complexity

O(V + E) — fastest shortest path algorithm when graph is DAG.

✅ Diagram — DAG Shortest Path

Topo Order: A → B → C → D
Relax edges in this order
Shortest paths computed
10. Dijkstra’s Algorithm — Detailed Notes
1. Purpose

Find shortest paths from a source to all vertices

✅ BUT only works when all edges have non-negative weights.

2. Key Concepts

✅ 2.1 Relaxation

Same as Bellman-Ford but done using fast selection based on PQ.

✅ 2.2 Greedy Approach

Select vertex with minimum tentative distance not yet processed.

3. Steps of Algorithm

✅ 3.1 Initialization

 dist[source] = 0
 dist[others] = ∞
 Maintain Min Priority Queue (Min-Heap)

✅ 3.2 Repeat Until PQ Empty

 Pick u with minimum dist

 For all adjacent vertices v:
Relax(u, v)

✅ 3.3 Final Distances Printed

4. Time Complexity

 Using Min Heap: O(E log V)

 Using Matrix: O(V²)

✅ Flowchart — Dijkstra’s Algorithm

Start
|
Initialize distances & PQ
|
While PQ not empty:
Extract min vertex u
For each neighbor v:
Relax edge (u,v)
|
Output shortest distances
|
End
 Unit: 5
1 ⃣ BACKTRACKING

Definition:

Backtracking is a refinement of brute force that systematically searches for a solution to a problem among
all available options.
It builds the solution incrementally, one component at a time, and removes (backtracks) the last added
component whenever it determines that the partial solution cannot lead to a complete solution.

In simple words, it is a depth-first search technique used for constraint satisfaction problems.

Flowchart:
┌────────────────────┐
│ Start │
└───────┬────────────┘
↓
┌────────────────────────┐
│ Choose next variable │
└─────────┬──────────────┘
↓
┌────────────────────────┐
│ Check if valid choice │
└─────────┬──────────────┘
Yes ↓ ↑ No
┌───────────────────┐ │
│ Add to solution │ │
└─────┬─────────────┘ │
↓ │
┌───────────────────┐ │
│ Solution complete?│────────┘
└─────┬─────────────┘
Yes ↓
┌────────────┐
│ Print / Use│
│ Solution │
└────────────┘
No ↓
Backtrack

Example (8-Queen Problem):

Place 8 queens on a chessboard such that no two queens attack each other.

Steps:

1. Place a queen in the first column of the first row.

2. Move to the next row.
3. Place a queen in the next safe column (no attacks in same column, row, diagonal).
4. If no column is safe → backtrack to previous row.
5. Continue until 8 queens are placed safely.

Possible Solution:
Queens placed at → (1,1), (2,5), (3,8), (4,6), (5,3), (6,7), (7,2), (8,4)
Explanation:

Backtracking explores all feasible configurations recursively.

When a choice violates a constraint (e.g., queen attacks another queen), the algorithm undoes that step and
tries another possibility.
This approach minimizes exploration of invalid solutions, saving time compared to pure brute force.

Advantages:

 Reduces unnecessary searches.

 Provides exact solutions for constraint problems.
 Uses recursion (easy to implement).
 Can find all or one valid solution.

Disadvantages:

 Time complexity is still exponential for large instances.

 May involve deep recursion, increasing stack usage.
 Performance depends on the order of decisions.

Characteristics:

 Recursive search through solution space.

 Employs pruning of invalid partial paths.
 Based on DFS traversal.
 Reversible step-by-step decision-making.

Uses:

 N-Queens, Sudoku solver, Crosswords.

 Graph Coloring, Maze solving.
 Combinatorial optimization.
2 ⃣ BRANCH AND BOUND ALGORITHM

Definition:

Branch and Bound (B&B) is an optimization technique used for solving NP-hard problems such as the
Knapsack or Traveling Salesman Problem.
It systematically divides the problem into smaller subproblems (branching) and uses bounding functions
to discard subproblems that cannot produce a better solution.

Flowchart:
┌─────────────────────┐
│ Start │
└────────┬────────────┘
↓
┌────────────────────────┐
│ Initialize Best Value │
└────────┬───────────────┘
↓
┌─────────────────────────┐
│ Branch into Subproblems │
└────────┬────────────────┘
↓
┌─────────────────────────┐
│ Compute Bound Value │
└────────┬────────────────┘
↓
┌──────────────────────────┐
│ Bound worse than Best? │
└──────┬────────┬──────────┘
↓Yes ↓No
┌────────────────┐ ┌────────────────────┐
│ Prune (discard)│ │ Explore Subproblem │
└────────────────┘ └──────┬─────────────┘
↓
┌────────────────────────┐
│ Update Best Solution │
└─────────┬──────────────┘
↓
Repeat

Example (0/1 Knapsack Problem):

Given items with weight and profit, and a knapsack capacity W = 10.

Item Weight Profit Profit/Weight

1 2 40 20

2 3 50 16.6

3 5 100 20

Branch: Include or exclude each item.

Bound: Maximum possible profit remaining.
If a branch’s bound < current best → prune that branch.
Explanation:

The algorithm keeps track of the best feasible solution and eliminates subproblems that can’t yield a better
result.
It uses bounding functions (upper/lower limits) to avoid exploring the entire search tree.

Advantages:

 Avoids exhaustive search.

 Finds optimal solution.
 Reduces complexity using bounds.
 Works well for combinatorial optimization.

Disadvantages:

 Still exponential in worst case.

 Performance depends on bound function quality.
 Requires priority queues for best-first branching.

Characteristics:

 Works on search tree representation.

 Employs branching (divide) and bounding (prune).
 Explores partial solutions selectively.

Uses:

 Traveling Salesman Problem (TSP).

 Job Scheduling.
 0/1 Knapsack Problem.
 Shortest Path & Assignment Problems.
3 ⃣ BREADTH-FIRST SEARCH (BFS)

Definition:

BFS is a graph traversal algorithm that explores all vertices level by level, visiting all neighbors of a node
before moving deeper.

Diagram:
Graph:
A
/ \
B C
/ \ \
D E F

BFS Traversal: A → B → C → D → E → F

Example:

Start from node A:

 Level 1: A
 Level 2: B, C
 Level 3: D, E, F
BFS uses a queue to maintain the order of traversal.

Explanation:

BFS starts from the root node and uses a queue data structure.
It’s ideal for finding shortest paths in unweighted graphs and minimum spanning levels.

Advantages:

 Finds shortest path efficiently.

 Non-recursive and easy to implement.
 Ideal for unweighted graphs.

Disadvantages:

 Requires more memory (queue + visited list).

 Not suitable for deep graphs.

Characteristics:

 Uses queue (FIFO) structure.

 Level-wise traversal.
 Non-recursive (iterative).

Uses:

 Shortest path finding.

 Social network analysis.
 Web crawlers.
 Broadcasting in networks.
4 ⃣ DEPTH-FIRST SEARCH (DFS)

Definition:

DFS is a graph traversal algorithm that explores as deep as possible along a branch before backtracking.

Diagram:
Graph:
A
/ \
B C
/ \
D E

DFS Traversal: A → B → D → E → C

Example:

Start from A → visit B → go deep to D → backtrack → visit E → backtrack → visit C.

Explanation:

DFS uses a stack (explicit or recursion).

It’s helpful for problems like cycle detection, topological sorting, and path existence.

Advantages:

 Requires less memory.

 Simple recursive implementation.
 Explores full paths quickly.

Disadvantages:

 May not find shortest path.

 Risk of infinite loop in cyclic graphs if not tracked.

Characteristics:

 Recursive / Stack-based.
 Depth-oriented traversal.
 Follows LIFO principle.

Uses:

 Path finding.
 Maze solving.
 Topological sorting.
 Cycle detection.
5 ⃣ 8-QUEEN PROBLEM

Definition:

The 8-Queen Problem is a classic backtracking problem that requires placing eight queens on an 8×8
chessboard so that no two queens attack each other, i.e., no two queens share the same row, column, or
diagonal.

Diagram:
Chessboard Representation (Sample Solution)
--------------------------------------------
Q - - - - - - -
- - - - Q - - -
- - - - - - - Q
- - - Q - - - -
- Q - - - - - -
- - - - - Q - -
- - Q - - - - -
- - - - - - Q -
(Q = Queen)

Example (Algorithm Steps):

1. Place a queen in the first column of the first row.

2. Move to the next row and find a safe column where no queen can attack.
3. If no safe column → backtrack to the previous row.
4. Repeat until all 8 queens are placed safely.
5. If all rows are filled → print solution.

Explanation:

The backtracking algorithm recursively tries all configurations:

 When a conflict occurs (same column or diagonal), it undoes the last move (backtrack).
 The process continues until all queens are placed safely or all options are exhausted.

This ensures a systematic exploration of all possibilities.

Advantages:

 Demonstrates backtracking concept clearly.

 Guarantees a valid solution if it exists.
 Reduces unnecessary search paths through pruning.

Disadvantages:

 Exponential time complexity (O(N!)).

 Inefficient for very large chessboards.
 Requires recursion and many checks per step.

Characteristics:

 Constraint Satisfaction problem.

 Uses recursion and backtracking.
 Checks column and diagonal conflicts.
  Based on Depth-First Search (DFS) logic.

Uses:

 Demonstrates recursive search logic.

 Used in AI, constraint programming, and chess algorithms.
 Foundation for solving N-Queens, Sudoku, and Puzzle problems.
6 ⃣ M-COLORING PROBLEM

Definition:

The M-Coloring Problem involves assigning M different colors to the vertices of a graph such that no two
adjacent vertices share the same color.

Diagram:
Graph:
(1)----- (2)
| |
(3)-----(4)

Using 3 colors:
Vertex 1 = Red
Vertex 2 = Blue
Vertex 3 = Green
Vertex 4 = Red

Example (Algorithm Steps):

1. Start with vertex 1 and assign a color.

2. Move to the next vertex and choose the lowest possible color that doesn’t conflict with adjacent
vertices.
3. If no color is available → backtrack.
4. Continue until all vertices are colored or backtrack completely if not possible.

Explanation:

This is a backtracking-based constraint problem.

It ensures adjacent vertices do not share the same color.
If M < chromatic number of graph → solution doesn’t exist.

Advantages:

 Systematic approach for graph coloring.

 Demonstrates constraint satisfaction efficiently.
 Reduces the problem into smaller feasible sets.

Disadvantages:

 Time complexity is exponential O(Mⁿ).

 Inefficient for large dense graphs.
 Heavy recursion usage.

Characteristics:

 Based on DFS traversal.

 Recursive and backtracking in nature.
 Checks for adjacency and color constraints.

Uses:

 Map coloring (e.g., no two countries share same color).

 Scheduling problems (e.g., exams, jobs).
 Register allocation in compilers.
 Resource management and frequency assignment.
7 ⃣ HAMILTONIAN CIRCUIT PROBLEM

Definition:

A Hamiltonian Circuit is a closed loop that visits each vertex exactly once and returns to the starting vertex.
If the path visits all vertices once but doesn’t return, it’s called a Hamiltonian Path.

Diagram:
Graph:
A —— B
| /|
| / |
| / |
C —— D

Hamiltonian Circuit: A → B → D → C → A

Example (Algorithm Steps):

1. Start from a vertex (e.g., A).

2. Visit the next unvisited vertex.
3. Continue visiting vertices until all are visited.
4. If you cannot proceed and not all vertices are visited → backtrack.
5. When all vertices are visited and last connects to the first → circuit found.

Explanation:

Backtracking is used to test each possible vertex sequence.

Whenever the next vertex violates adjacency or repeats, the algorithm backtracks.
The complexity grows factorially due to permutation exploration.

Advantages:

 Provides the foundation for Traveling Salesman Problem (TSP).

 Finds valid Hamiltonian paths and circuits.
 Explains recursive searching well.

Disadvantages:

 Exponential complexity (O(n!)).

 Not practical for large graphs.

Characteristics:

 NP-complete problem.
 Involves visiting all vertices exactly once.
 Uses backtracking to explore permutations.

Uses:

 Routing and circuit design.

 Network traversal.
 DNA sequencing in bioinformatics.
 Solving TSP.
8 ⃣ 0/1 KNAPSACK PROBLEM (Using Branch and Bound)

Definition:

In the 0/1 Knapsack problem, we must select a subset of given items with weights and profits, such that
total weight ≤ capacity and profit is maximized.
Each item can be either included (1) or excluded (0).

Table:

Item Weight Profit Profit/Weight

1 2 40 20

2 3 50 16.6

3 5 100 20

Example:

Capacity (W) = 8
Branch: Include or exclude each item.
Bound: Remaining potential profit (upper bound).
Best solution found = 140 (Items 1 & 3).

Explanation:

Branch and Bound creates a state-space tree of possible item combinations.

Bounding function estimates maximum achievable profit from a node.
If this bound < current best → prune that branch.

Advantages:

 Avoids exploring infeasible combinations.

 Guarantees optimal result.
 Efficient pruning with good bound.

Disadvantages:

 Still exponential in worst case.

 Needs careful bounding function.

Characteristics:

 Uses branching and bounding together.

 Explores search tree partially.
 Applicable for maximization/minimization problems.

Uses:

 Resource allocation.
 Project selection.
 Investment and portfolio optimization.
9 ⃣ 8-PUZZLE & 16-PUZZLE PROBLEMS

Definition:

The 8-puzzle and 16-puzzle are sliding tile problems where the goal is to arrange tiles in order using the
empty space.

 8-puzzle → 3×3 board

 16-puzzle → 4×4 board

Diagram:
Initial State: Goal State:
1 2 3 1 2 3
4 5 6 4 5 6
7 8 _ 7 8 _
(_ = blank space)

Example (8-Puzzle):

Initial:
123
456
7_8
→ Move 8 left → goal achieved.

Explanation:

Branch and Bound can solve puzzles by:

 Defining cost function f(n) = g(n) + h(n)

where g(n) = cost so far, h(n) = estimated cost to goal.
 Expanding the least-cost node first (Best-first search).

Advantages:

 Finds optimal path efficiently.

 Suitable for AI problem-solving.

Disadvantages:

 Memory-intensive.
 Computationally expensive for large boards (like 16-puzzle).

Characteristics:

 Uses heuristics and cost function.

 Branch and Bound or A* search method.

Uses:

 AI and game development.

 Search algorithm demonstration.
 Benchmark for state-space search techniques.
🔟 TRAVELING SALESMAN PROBLEM (TSP)

Definition:

The TSP seeks the shortest possible route that visits each city exactly once and returns to the starting city.

Diagram:
Cities: A, B, C, D
Distances:
A-B=10, A-C=15, A-D=20, B-C=35, B-D=25, C-D=30

Example:

Possible paths and their costs:

 A-B-C-D-A = 10 + 35 + 30 + 20 = 95
 A-C-B-D-A = 15 + 35 + 25 + 20 = 95
Optimal cost = 95

Explanation:

Using Branch and Bound, a state-space tree is generated for all paths.
Each node represents a partial tour, and bounding estimates the minimum cost from that node.
Branches with cost ≥ current best are pruned.

Advantages:

 Finds exact optimal path.

 Demonstrates efficiency of pruning.

Disadvantages:

 Exponential complexity (O(n!)).

 Large memory requirement.

Characteristics:

 NP-hard combinatorial problem.

 Uses branching and bounding of paths.
 Evaluates permutations efficiently.

Uses:

 Route optimization.
 Logistics and delivery scheduling.
 Circuit layout design.
11 ⃣ LIMITATIONS OF BRANCH AND BOUND

Definition:

Although powerful, Branch and Bound has several practical limitations due to its time and space
complexity.

Table:

Limitation Description

1 Exponential growth of subproblems

2 Requires large memory for state-space tree

3 Performance depends on bounding function

4 Difficult to parallelize

5 Not suitable for real-time systems

Explanation:

 For large NP-hard problems, the search tree expands rapidly.

 Ineffective bounds cause minimal pruning, leading to full tree exploration.
 Requires priority queues and dynamic data structures, increasing memory load.

Advantages (Despite Limitations):

 Still provides guaranteed optimal solutions.

 Can be optimized using heuristics.

Disadvantages:

 Exponential time for large instances.

 Space-consuming due to storing nodes.
 Complex to implement for real systems.

Characteristics:

 Depends heavily on quality of bounds.

 Works best with small to medium-sized datasets.

Uses (with optimization):

 Often combined with heuristics or approximation algorithms.

 Applied in AI, logistics, and operations research.