Design and Analysis of Algorithms:

(Unit-1)
Concept of Algorithm Efficiency in DAA:
The word Algorithm means "A set of finite rules or instructions to be followed in calculations
or other problem-solving operations"

Advantages of Algorithms:
• It is easy to understand.
• An algorithm is a step-wise representation of a solution to a given problem.
• In an Algorithm the problem is broken down into smaller pieces or steps hence, it is
easier for the programmer to convert it into an actual program.

Algorithm Efficiency refers to how well an algorithm performs in terms of time and space as
the size of the input increases.
How to analyze an Algorithm?
For a standard algorithm to be good, it must be efficient. Hence the efficiency of an
algorithm must be checked and maintained. It can be in two stages:

1. Priori Analysis:
"Priori" means "before". Hence Priori analysis means checking the algorithm before its
implementation. In this, the algorithm is checked when it is written in the form of
theoretical steps. This Efficiency of an algorithm is measured by assuming that all other
factors, for example, processor speed, are constant and have no effect on the
implementation. This is done usually by the algorithm designer. This analysis is independent
of the type of hardware and language of the compiler. It gives the approximate answers for
the complexity of the program.
2. Posterior Analysis:

"Posterior" means "after". Hence Posterior analysis means checking the algorithm after its
implementation. In this, the algorithm is checked by implementing it in any programming
language and executing it. This analysis helps to get the actual and real analysis report about
correctness(for every possible input/s if it shows/returns correct output or not), space
required, time consumed, etc. That is, it is dependent on the language of the compiler and
the type of hardware used.

Algorithm Efficiency:

Algorithm Efficiency refers to how well an algorithm performs in terms of time and space as
the size of the input increases.
An algorithm is defined as complex based on the amount of Space and Time it consumes.
Hence the Complexity of an algorithm refers to the measure of the time that it will need to
execute and get the expected output, and the Space it will need to store all the data (input,
temporary data, and output). Hence these two factors define the efficiency of an algorithm.
The two factors of Algorithm Complexity are:
• Time Factor: Time is measured by counting the number of key operations such as
comparisons in the sorting algorithm.
• Space Factor: Space is measured by counting the maximum memory space required
by the algorithm to run/execute.

Therefore the complexity of an algorithm can be divided into two types:

1. Space Complexity: The space complexity of an algorithm refers to the amount of memory
required by the algorithm to store the variables and get the result. This can be for inputs,
temporary operations, or outputs.
How to calculate Space Complexity?
The space complexity of an algorithm is calculated by determining the following 2
components:

• Fixed Part: This refers to the space that is required by the algorithm. For example,
input variables, output variables, program size, etc.
• Variable Part: This refers to the space that can be different based on the
implementation of the algorithm. For example, temporary variables, dynamic
memory allocation, recursion stack space, etc.
Therefore Space complexity S(P) of any algorithm P is S(P) = C + SP(I), where C is the
 fixed part and S(I) is the variable part of the algorithm, which depends on instance
characteristic I.

• Example: Consider the below algorithm for Linear Search

• Step 1: START
Step 2: Get n elements of the array in arr and the number to be
searched in x
Step 3: Start from the leftmost element of arr[] and one by one
compare x with each element of arr[]
Step 4: If x matches with an element, Print True.
Step 5: If x doesn’t match with any of the elements, Print False.
Step 6: END
Here, There are 2 variables arr[], and x, where the arr[] is the
variable part of n elements and x is the fixed part. Hence S(P) =
1+n. So, the space complexity depends on n(number of
elements). Now, space depends on data types of given variables
and constant types and it will be multiplied accordingly.

2. Time Complexity: The time complexity of an algorithm refers to the amount of time
required by the algorithm to execute and get the result. This can be for normal operations,
conditional if-else statements, loop statements, etc.
How to Calculate, Time Complexity?
The time complexity of an algorithm is also calculated by determining the following 2
components:
• Constant time part: Any instruction that is executed just once comes in this part. For
example, input, output, if-else, switch, arithmetic operations, etc.
• Variable Time Part: Any instruction that is executed more than once, say n times,
comes in this part. For example, loops, recursion, etc.
Therefore Time complexity T(P) T(P) of any algorithm P
is T(P) = C + TP(I), where C is the constant time part and TP(I) is the variable part of
the algorithm, which depends on the instance characteristic I.
Example: In the algorithm of Linear Search above, the time complexity is calculated as
follows:

Step 1: --Constant Time

Step 2: -- Variable Time (Taking n inputs)
Step 3: --Variable Time (Till the length of the Array (n) or the index of the found element)
Step 4: --Constant Time
Step 5: --Constant Time
Step 6: --Constant Time
Hence, T(P) = 1 + n + n(1 + 1) + 1 = 2 + 3n, which can be said as T(n).
How to express an Algorithm?

1. Natural Language:- Here we express the Algorithm in the natural English language. It
is too hard to understand the algorithm from it.
2. Flowchart:- Here we express the Algorithm by making agraphical/pictorial
representation of it. It is easier to understand than Natural Language.

3. Pseudo Code:- Here we express the Algorithm in the form of annotations and
informative text written in plain English which is very much similar to the real code
but as it has no syntax like any of the programming languages, it can’t be compiled
or interpreted by the computer. It is the best way to express an algorithm because it
can be understood by even a layman with some school-level knowledge.

Runtime Analysis of an Algorithm:

It involves determining how the time taken by an algorithm grows with the size of the input.
Runtime analysis is the process of predicting how long an algorithm takes to run, based on:

• The input size (usually denoted by n)

• The steps the algorithm performs

Three types of analysis are generally performed:

• Worst-Case Analysis: The worst-case consists of the input for which the algorithm
takes the longest time to complete its execution.
• Best Case Analysis: The best case consists of the input for which the algorithm takes
the least time to complete its execution.

• Average case: The average case gives an idea about the average running time of the
given algorithm.

Example: Linear Search

int linearSearch(int arr[], int n, int key) {
for (int i = 0; i < n; i++) {
if (arr[i] == key) return i;
}
return -1;
}
Time Analysis:
• Best Case: O(1) → key is at the first position
• Worst Case: O(n) → key is at the last position or not found
• Average Case: O(n)

Asymptotic Notations:
• Asymptotic Notations are mathematical tools used to analyze the performance of
algorithms by understanding how their efficiency changes as the input size grows.
• These notations provide a concise way to express the behavior of an algorithm's time
or space complexity as the input size approaches infinity.

• Rather than comparing algorithms directly, asymptotic analysis focuses on

understanding the relative growth rates of algorithms' complexities.

There are mainly three asymptotic notations:

1. Big-O Notation (O-notation)
2. Omega Notation (Ω-notation)
3. Theta Notation (Θ-notation)

1. Big O Notation – O(f(n))

➤ Describes the worst-case time or space.

It gives the upper bound on the running time.

It tells us the maximum time an algorithm will take for input size n.
Example:
for(int i = 0; i < n; i++) {
// constant time work

➡ Time Complexity: O(n)

Meaning:
"The algorithm will not take more than f(n) time."
2. Omega Notation – Ω(f(n))

➤ Describes the best-case time or space.

It gives the lower bound.

It tells us the minimum time the algorithm takes in the best-case scenario.

Example:
In Linear Search, if the key is the first element: Ω(1)
Meaning:
"The algorithm will take at least f(n) time."

3. Theta Notation – Θ(f(n))

➤ Describes the tight bound.

It means both upper and lower bounds are the same.
It tells us the exact asymptotic behavior.
Example:
Merge Sort takes Θ(n log n) in all cases.
Meaning:
"The algorithm will take exactly around f(n) time for large n."

1. Theta Notation (Θ-Notation):

Theta notation encloses the function from above and below. Since it represents the upper
and the lower bound of the running time of an algorithm, it is used for analyzing the
average-case complexity of an algorithm.
.Theta (Average Case) You add the running times for each possible input combination and
take the average in the average case.
Let g and f be the function from the set of natural numbers to itself. The function f is said to
be Θ(g), if there are constants c1, c2 > 0 and a natural number n0 such that c1* g(n) ≤ f(n) ≤
c2 * g(n) for all n ≥ n0
 Theta notation
Mathematical Representation of Theta notation:
Θ (g(n)) = {f(n): there exist positive constants c1, c2 and n0 such that 0 ≤ c1 * g(n) ≤ f(n) ≤ c2
* g(n) for all n ≥ n0}
Note: Θ(g) is a set
The above expression can be described as if f(n) is theta of g(n), then the value f(n) is always
between c1 * g(n) and c2 * g(n) for large values of n (n ≥ n0). The definition of theta also
requires that f(n) must be non-negative for values of n greater than n0.
The execution time serves as both a lower and upper bound on the algorithm's time
complexity.
It exist as both, most, and least boundaries for a given input value.
A simple way to get the Theta notation of an expression is to drop low-order terms and
ignore leading constants. For example, Consider the expression 3n3 + 6n2 + 6000 =
Θ(n3), the dropping lower order terms is always fine because there will always be a
number(n) after which Θ(n3) has higher values than Θ(n2) irrespective of the constants
involved. For a given function g(n), we denote Θ(g(n)) is following set of functions.
Examples :
{ 100 , log (2000) , 10^4 } belongs to Θ(1)
{ (n/4) , (2n+3) , (n/100 + log(n)) } belongs to Θ(n)
{ (n^2+n) , (2n^2) , (n^2+log(n))} belongs to Θ( n2)
Note: Θ provides exact bounds.

2. Big-O Notation (O-notation):

Big-O notation represents the upper bound of the running time of an algorithm. Therefore, it
gives the worst-case complexity of an algorithm.
.It is the most widely used notation for Asymptotic analysis.
.It specifies the upper bound of a function.
.The maximum time required by an algorithm or the worst-case time complexity.
.It returns the highest possible output value(big-O) for a given input.
.Big-O(Worst Case) It is defined as the condition that allows an algorithm to complete
statement execution in the longest amount of time possible.

If f(n) describes the running time of an algorithm, f(n) is O(g(n)) if there exist a positive
constant C and n0 such that, 0 ≤ f(n) ≤ cg(n) for all n ≥ n0
It returns the highest possible output value (big-O)for a given input.

The execution time serves as an upper bound on the algorithm's time complexity.

Mathematical Representation of Big-O Notation:

O(g(n)) = { f(n): there exist positive constants c and n0 such that 0 ≤ f(n) ≤ cg(n) for all n ≥ n0
}
For example, Consider the case of Insertion Sort. It takes linear time in the best case and
quadratic time in the worst case. We can safely say that the time complexity of the Insertion
sort is O(n2).
Note: O(n2) also covers linear time.

If we use Θ notation to represent the time complexity of Insertion sort, we have to use two
statements for best and worst cases:
• The worst-case time complexity of Insertion Sort is Θ(n2).
• The best case time complexity of Insertion Sort is Θ(n).
The Big-O notation is useful when we only have an upper bound on the time complexity of
an algorithm. Many times we easily find an upper bound by simply looking at the
algorithm.
Examples :
{ 100 , log (2000) , 10^4 } belongs to O(1)
U { (n/4) , (2n+3) , (n/100 + log(n)) } belongs to O(n)
U { (n^2+n) , (2n^2) , (n^2+log(n))} belongs to O( n^2)

Note: Here, U represents union, we can write it in these manner because O provides exact
or upper bounds .
3. Omega Notation (Ω-Notation):
Omega notation represents the lower bound of the running time of an algorithm. Thus, it
provides the best case complexity of an algorithm.
The execution time serves as a lower bound on the algorithm's time complexity.
It is defined as the condition that allows an algorithm to complete statement execution in
the shortest amount of time.

Let g and f be the function from the set of natural numbers to itself. The function f is said to
be Ω(g), if there is a constant c > 0 and a natural number n0 such that c*g(n) ≤ f(n) for all n ≥
n0

Mathematical Representation of Omega notation :

Ω(g(n)) = { f(n): there exist positive constants c and n0 such that 0 ≤ cg(n) ≤ f(n) for all n ≥ n0
}
Let us consider the same Insertion sort example here. The time complexity of Insertion Sort
can be written as Ω(n), but it is not very useful information about insertion sort, as we are
generally interested in worst-case and sometimes in the average case.
Examples :
{ (n^2+n) , (2n^2) , (n^2+log(n))} belongs to Ω( n^2)
U { (n/4) , (2n+3) , (n/100 + log(n)) } belongs to Ω(n)
U { 100 , log (2000) , 10^4 } belongs to Ω(1)
Note: Here, U represents union, we can write it in these manner because Ω provides exact
or lower bounds.

Growth of Functions in DAA:

The growth of functions refers to how an algorithm's running time or space requirement
increases with the input size n.
This concept helps us compare algorithms by understanding how fast their time or space
usage grows as the input becomes very large.

Common Growth Rates (From Fastest to Slowest)

Complexity Name Example Function Growth Behavior (as n increases)

O(1) Constant f(n) = 5 No growth

O(log n) Logarithmic f(n) = log n Grows slowly

O(n) Linear f(n) = n Grows proportionally

O(n log n) Linearithmic f(n) = n log n Grows faster than linear

O(n²) Quadratic f(n) = n² Grows much faster

O(n³) Cubic f(n) = n³ Very rapid growth

O(2ⁿ) Exponential f(n) = 2ⁿ Extremely fast growth

O(n!) Factorial f(n) = n! Grows faster than exponential

How do we compare two order of growths?

The following are some standard terms that we must remember for comparison.
c < Log Log n < Log n < n1/3 < n1/2 < n < n Log n < n2 < n2 Log n < n3 < n4 < 2n < nn
Here c is a constant

Master’s Theorem in DAA:

The Master Theorem provides a direct way to determine the time complexity of recursive
algorithms, especially divide-and-conquer algorithms (like Merge Sort, Binary Search, etc.).

It avoids solving recurrence relations manually by using a standard form.

1. Standard Form of Recurrence
The Master Theorem applies to recurrences of the form:
T(n)=a⋅T(n/b)+f(n)
Where:

Symbol Meaning

a Number of subproblems

n/b Size of each subproblem

f(n) Cost of dividing and combining subproblems

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

where, T(n) has the following asymptotic bounds:

1. If f(n) = O(nlogb a-ϵ), then T(n) = Θ(nlogb a).
2. If f(n) = Θ(nlogb a), then T(n) = Θ(nlogb a * log n).
3. If f(n) = Ω(nlogb a+ϵ), then T(n) = Θ(f(n)).
ϵ > 0 is a constant.

Each of the above conditions can be interpreted as:

1. If the cost of solving the sub-problems at each level increases by a certain factor, the
value of f(n) will become polynomially smaller than nlogb a. Thus, the time complexity
is oppressed by the cost of the last level ie. nlogb a

2. If the cost of solving the sub-problem at each level is nearly equal, then the value
of f(n) will be nlogb a. Thus, the time complexity will be f(n) times the total number of
levels ie. nlogb a * log n
3. If the cost of solving the subproblems at each level decreases by a certain factor, the
value of f(n) will become polynomially larger than nlogb a. Thus, the time complexity
is oppressed by the cost of f(n).
(Unit – 2)
Searching and Sorting:
Introduction to Divide and Conquer Algorithm
Divide and Conquer Algorithm is a problem-solving technique used to solve problems by
dividing the main problem into subproblems, solving them individually and then merging
them to find solution to the original problem. Divide and Conquer is mainly useful when we
divide a problem into independent subproblems. If we have overlapping subproblems, then
we use Dynamic Programming.
Working of Divide and Conquer Algorithm
Divide and Conquer Algorithm can be divided into three steps: Divide, Conquer and Merge.

The above diagram shows working with the example of Merge Sort which is used for sorting

1. Divide:
• Break down the original problem into smaller subproblems.
• Each subproblem should represent a part of the overall problem.

• The goal is to divide the problem until no further division is possible.

2. Conquer:
• Solve each of the smaller subproblems individually.
• If a subproblem is small enough (often referred to as the “base case”), we solve it
directly without further recursion.
• The goal is to find solutions for these subproblems independently.
3. Merge:
• Combine the sub-problems to get the final solution of the whole problem.
• Once the smaller subproblems are solved, we recursively combine their solutions to
get the solution of larger problem.
• The goal is to formulate a solution for the original problem by merging the results
from the subproblems.
Characteristics of Divide and Conquer Algorithm
Divide and Conquer Algorithm involves breaking down a problem into smaller, more
manageable parts, solving each part individually, and then combining the solutions to solve
the original problem. The characteristics of Divide and Conquer Algorithm are:
• Dividing the Problem: The first step is to break the problem into smaller, more
manageable subproblems. This division can be done recursively until the
subproblems become simple enough to solve directly.
• Independence of Subproblems: Each subproblem should be independent of the
others, meaning that solving one subproblem does not depend on the solution of
another. This allows for parallel processing or concurrent execution of subproblems,
which can lead to efficiency gains.
• Conquering Each Subproblem: Once divided, the subproblems are solved
individually. This may involve applying the same divide and conquer approach
recursively until the subproblems become simple enough to solve directly, or it may
involve applying a different algorithm or technique.
• Combining Solutions: After solving the subproblems, their solutions are combined to
obtain the solution to the original problem. This combination step should be
relatively efficient and straightforward, as the solutions to the subproblems should
be designed to fit together seamlessly.
Applications of Divide and Conquer Algorithm
The following are some standard algorithms that follow Divide and Conquer algorithm:
• Binary Search is an efficient algorithm for finding an element in a sorted array by
repeatedly dividing the search interval in half. It works by comparing the target value
with the middle element and narrowing the search to either the left or right half,
depending on the comparison.
 • Quicksort is a sorting algorithm that picks a pivot element and rearranges the array
elements so that all elements smaller than the picked pivot element move to the left
side of the pivot, and all greater elements move to the right side. Finally, the
algorithm recursively sorts the subarrays on the left and right of the pivot element.
• Merge Sort is also a sorting algorithm. The algorithm divides the array into two
halves, recursively sorts them, and finally merges the two sorted halves.
• Closest Pair of Points The problem is to find the closest pair of points in a set of
points in the x-y plane. The problem can be solved in O(n^2) time by calculating the
distances of every pair of points and comparing the distances to find the minimum.
The Divide and Conquer algorithm solves the problem in O(N log N) time.
• Strassen's Algorithm is an efficient algorithm to multiply two matrices. A simple
method to multiply two matrices needs 3 nested loops and is O(n^3). Strassen's
algorithm multiplies two matrices in O(n^2.8974) time.
Advantages of Divide and Conquer Algorithm
• Solving difficult problems: Divide and conquer technique is a tool for solving difficult
problems conceptually. e.g. Tower of Hanoi puzzle. It requires a way of breaking the
problem into sub-problems, and solving all of them as an individual cases and then
combining sub- problems to the original problem.
• Algorithm efficiency: The divide-and-conquer algorithm often helps in the discovery
of efficient algorithms. It is the key to algorithms like Quick Sort and Merge Sort, and
fast Fourier transforms.
• Parallelism: Normally Divide and Conquer algorithms are used in multi-processor
machines having shared-memory systems where the communication of data
between processors does not need to be planned in advance, because distinct sub-
problems can be executed on different processors.
• Memory access: These algorithms naturally make an efficient use of memory caches.
Since the subproblems are small enough to be solved in cache without using the
main memory that is slower one. Any algorithm that uses cache efficiently is called
cache oblivious.
Disadvantages of Divide and Conquer Algorithm
• Overhead: The process of dividing the problem into subproblems and then
combining the solutions can require additional time and resources. This overhead
can be significant for problems that are already relatively small or that have a simple
solution.
• Complexity: Dividing a problem into smaller subproblems can increase the
complexity of the overall solution. This is particularly true when the subproblems are
interdependent and must be solved in a specific order.
 • Difficulty of implementation: Some problems are difficult to divide into smaller
subproblems or require a complex algorithm to do so. In these cases, it can be
challenging to implement a divide and conquer solution.

• Memory limitations: When working with large data sets, the memory requirements
for storing the intermediate results of the subproblems can become a limiting factor.

Example:

1.Binary Search Algorithm:

Binary Search Algorithm is a searching algorithm used in a sorted array by repeatedly
dividing the search interval in half. The idea of binary search is to use the information that
the array is sorted and reduce the time complexity to O(log N).

Conditions to apply Binary Search Algorithm in a Data Structure

To apply Binary Search algorithm:
• The data structure must be sorted.
• Access to any element of the data structure should take constant time.
Binary Search Algorithm
Below is the step-by-step algorithm for Binary Search:
• Divide the search space into two halves by finding the middle index "mid".
• Compare the middle element of the search space with the key.
• If the key is found at middle element, the process is terminated.
• If the key is not found at middle element, choose which half will be used as the next
search space.
o If the key is smaller than the middle element, then the left side is used for
next search.
o If the key is larger than the middle element, then the right side is used for
next search.
• This process is continued until the key is found or the total search space is
exhausted.

How does Binary Search Algorithm work?

To understand the working of binary search, consider the following illustration:
Consider an array arr[] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91}, and the target = 23.
How to Implement Binary Search Algorithm?
The Binary Search Algorithm can be implemented in the following two ways
• Iterative Binary Search Algorithm
• Recursive Binary Search Algorithm
Iterative Binary Search Algorithm:
Here we use a while loop to continue the process of comparing the key and splitting the
search space in two halves.
// C++ program to implement iterative Binary Search
#include <bits/stdc++.h>
using namespace std;

// An iterative binary search function.

int binarySearch(int arr[], int low, int high, int x)
{
while (low <= high) {
int mid = low + (high - low) / 2;

// Check if x is present at mid

if (arr[mid] == x)
return mid;

// If x greater, ignore left half

if (arr[mid] < x)
low = mid + 1;

// If x is smaller, ignore right half

else
high = mid - 1;
}

// If we reach here, then element was not present

return -1;
}

// Driver code
int main(void)
{
int arr[] = { 2, 3, 4, 10, 40 };
int x = 10;
int n = sizeof(arr) / sizeof(arr[0]);
 int result = binarySearch(arr, 0, n - 1, x);
if(result == -1) cout << "Element is not present in array";
else cout << "Element is present at index " << result;
return 0;
}

Output

Element is present at index 3

Time Complexity: O(log N)
Auxiliary Space: O(1)
Recursive Binary Search Algorithm:
Create a recursive function and compare the mid of the search space with the key. And
based on the result either return the index where the key is found or call the recursive
function for the next search space.
#include <bits/stdc++.h>
using namespace std;

// A recursive binary search function. It returns

// location of x in given array arr[low..high] is present,
// otherwise -1
int binarySearch(int arr[], int low, int high, int x)
{
if (high >= low) {
int mid = low + (high - low) / 2;

// If the element is present at the middle

// itself
if (arr[mid] == x)
return mid;

// If element is smaller than mid, then

// it can only be present in left subarray
if (arr[mid] > x)
return binarySearch(arr, low, mid - 1, x);

// Else the element can only be present

// in right subarray
return binarySearch(arr, mid + 1, high, x);
}
return -1;
}
// Driver code
int main()
{
int arr[] = { 2, 3, 4, 10, 40 };
int query = 10;
int n = sizeof(arr) / sizeof(arr[0]);
int result = binarySearch(arr, 0, n - 1, query);
if (result == -1) cout << "Element is not present in array";
else cout << "Element is present at index " << result;
return 0;
}

Output
Element is present at index 3
Complexity Analysis of Binary Search Algorithm
• Time Complexity:
o Best Case: O(1)
o Average Case: O(log N)
o Worst Case: O(log N)

• Auxiliary Space: O(1), If the recursive call stack is considered then the auxiliary space
will be O(log N).

2.Merge Sort:

Merge sort is a popular sorting algorithm known for its efficiency and stability. It follows
the divide-and-conquer approach. It works by recursively dividing the input array into two
halves, recursively sorting the two halves and finally merging them back together to obtain
the sorted array.
How does Merge Sort work?
Here's a step-by-step explanation of how merge sort works:
1. Divide: Divide the list or array recursively into two halves until it can no more be
divided.
2. Conquer: Each subarray is sorted individually using the merge sort algorithm.
3. Merge: The sorted subarrays are merged back together in sorted order. The process
continues until all elements from both subarrays have been merged.

#include <bits/stdc++.h>
using namespace std;

// Merges two subarrays of arr[].

// First subarray is arr[left..mid]

// Second subarray is arr[mid+1..right]
void merge(vector<int>& arr, int left,
int mid, int right){

int n1 = mid - left + 1;

int n2 = right - mid;

// Create temp vectors

vector<int> L(n1), R(n2);

// Copy data to temp vectors L[] and R[]

for (int i = 0; i < n1; i++)

L[i] = arr[left + i];

for (int j = 0; j < n2; j++)
R[j] = arr[mid + 1 + j];

int i = 0, j = 0;
int k = left;
// Merge the temp vectors back
// into arr[left..right]
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
}
else {
arr[k] = R[j];
j++;
}
k++;
}

// Copy the remaining elements of L[],

// if there are any
while (i < n1) {
arr[k] = L[i];
i++;

k++;
}

// Copy the remaining elements of R[],

// if there are any

while (j < n2) {
arr[k] = R[j];
j++;

k++;
 }
}

// begin is for left index and end is right index

// of the sub-array of arr to be sorted
void mergeSort(vector<int>& arr, int left, int right){

if (left >= right)

return;

int mid = left + (right - left) / 2;

mergeSort(arr, left, mid);
mergeSort(arr, mid + 1, right);
merge(arr, left, mid, right);
}

// Driver code
int main(){

vector<int> arr = {38, 27, 43, 10};

int n = arr.size();

mergeSort(arr, 0, n - 1);
for (int i = 0; i < arr.size(); i++)

cout << arr[i] << " ";

cout << endl;

return 0;

}
Output
10 27 38 43
Complexity Analysis of Merge Sort
• Time Complexity:
o Best Case: O(n log n), When the array is already sorted or nearly sorted.
o Average Case: O(n log n), When the array is randomly ordered.
o Worst Case: O(n log n), When the array is sorted in reverse order.
• Auxiliary Space: O(n), Additional space is required for the temporary array used
during merging.
Applications of Merge Sort:
• Sorting large datasets
• External sorting (when the dataset is too large to fit in memory)
• Inversion counting
• Merge Sort and its variations are used in library methods of programming languages.
o Its variation TimSort is used in Python, Java Android and Swift. The main
reason why it is preferred to sort non-primitive types is stability which is not
there in QuickSort.
o Arrays.sort in Java uses QuickSort while Collections.sort uses MergeSort.
• It is a preferred algorithm for sorting Linked lists.
• It can be easily parallelized as we can independently sort subarrays and then merge.

Advantages and Disadvantages of Merge Sort

Advantages
• Stability : Merge sort is a stable sorting algorithm, which means it maintains the
relative order of equal elements in the input array.

• Guaranteed worst-case performance: Merge sort has a worst-case time complexity

of O(N logN) , which means it performs well even on large datasets.
• Simple to implement: The divide-and-conquer approach is straightforward.
• Naturally Parallel : We independently merge subarrays that makes it suitable for
parallel processing.
Disadvantages
• Space complexity: Merge sort requires additional memory to store the merged sub-
arrays during the sorting process.

• Not in-place: Merge sort is not an in-place sorting algorithm, which means it requires
additional memory to store the sorted data. This can be a disadvantage in
applications where memory usage is a concern.
• Merge Sort is Slower than QuickSort in general as QuickSort is more cache friendly
because it works in-place.

3.Quick Sort:
QuickSort is a sorting algorithm based on the Divide and Conquer that picks an element as a
pivot and partitions the given array around the picked pivot by placing the pivot in its
correct position in the sorted array.
It works on the principle of divide and conquer, breaking down the problem into smaller
sub-problems.
There are mainly three steps in the algorithm:

1. Choose a Pivot: Select an element from the array as the pivot. The choice of pivot
can vary (e.g., first element, last element, random element, or median).
2. Partition the Array: Rearrange the array around the pivot. After partitioning, all
elements smaller than the pivot will be on its left, and all elements greater than the
pivot will be on its right. The pivot is then in its correct position, and we obtain the
index of the pivot.
3. Recursively Call: Recursively apply the same process to the two partitioned sub-
arrays (left and right of the pivot).

4. Base Case: The recursion stops when there is only one element left in the sub-array,
as a single element is already sorted.
Here’s a basic overview of how the QuickSort algorithm works.
Choice of Pivot
There are many different choices for picking pivots.
• Always pick the first (or last) element as a pivot. The below implementation picks the
last element as pivot. The problem with this approach is it ends up in the worst case
when array is already sorted.
• Pick a random element as a pivot. This is a preferred approach because it does not
have a pattern for which the worst case happens.

• Pick the median element is pivot. This is an ideal approach in terms of time
complexity as we can find median in linear time and the partition function will
always divide the input array into two halves. But it takes more time on average as
median finding has high constants.

Working of Lomuto Partition Algorithm with Illustration

The logic is simple, we start from the leftmost element and keep track of the index of smaller
(or equal) elements as i . While traversing, if we find a smaller element, we swap the current
element with arr[i]. Otherwise, we ignore the current element.
Let us understand the working of partition algorithm with the help of the following example:

Illustration of QuickSort Algorithm

In the previous step, we looked at how the partitioning process rearranges the array based
on the chosen pivot. Next, we apply the same method recursively to the smaller sub-arrays
on the left and right of the pivot. Each time, we select new pivots and partition the arrays
again. This process continues until only one element is left, which is always sorted. Once
every element is in its correct position, the entire array is sorted.
Below image illustrates, how the recursive method calls for the smaller sub-arrays on
the left and right of the pivot:
Quick Sort is a crucial algorithm in the industry, but there are other sorting algorithms that
may be more optimal in different cases.

#include <bits/stdc++.h>
using namespace std;

int partition(vector<int>& arr, int low, int high) {

// Choose the pivot

int pivot = arr[high];

// Index of smaller element and indicates

// the right position of pivot found so far
int i = low - 1;

// Traverse arr[low..high] and move all smaller

// elements on left side. Elements from low to
// i are smaller after every iteration
for (int j = low; j <= high - 1; j++) {
if (arr[j] < pivot) {
i++;
swap(arr[i], arr[j]);
}
}

// Move pivot after smaller elements and

// return its position
swap(arr[i + 1], arr[high]);
return i + 1;
}

// The QuickSort function implementation

void quickSort(vector<int>& arr, int low, int high) {

if (low < high) {

// pi is the partition return index of pivot

int pi = partition(arr, low, high);

// Recursion calls for smaller elements

// and greater or equals elements
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
 }
}

int main() {
vector<int> arr = {10, 7, 8, 9, 1, 5};
int n = arr.size();
quickSort(arr, 0, n - 1);

for (int i = 0; i < n; i++) {

cout << arr[i] << " ";
}
return 0;
}

Output
Sorted Array
1 5 7 8 9 10

Complexity Analysis of Quick Sort

Time Complexity:
• Best Case: (Ω(n log n)), Occurs when the pivot element divides the array into two
equal halves.
• Average Case (θ(n log n)), On average, the pivot divides the array into two parts, but
not necessarily equal.
• Worst Case: (O(n²)), Occurs when the smallest or largest element is always chosen as
the pivot (e.g., sorted arrays).
Auxiliary Space: O(n), due to recursive call stack
Advantages of Quick Sort

• It is a divide-and-conquer algorithm that makes it easier to solve problems.

• It is efficient on large data sets.
• It has a low overhead, as it only requires a small amount of memory to function.
• It is Cache Friendly as we work on the same array to sort and do not copy data to any
auxiliary array.
• Fastest general purpose algorithm for large data when stability is not required.
• It is tail recursive and hence all the tail call optimization can be done.
Disadvantages of Quick Sort
• It has a worst-case time complexity of O(n2), which occurs when the pivot is chosen
poorly.

• It is not a good choice for small data sets.

• It is not a stable sort, meaning that if two elements have the same key, their relative
order will not be preserved in the sorted output in case of quick sort, because here
we are swapping elements according to the pivot's position (without considering
their original positions).

Matrix Multiplication:
Given two matrices mat1[][] of size n × m and mat2[][] of size m × q, find their matrix
product, where the resulting matrix has dimensions n × q
Examples:
Input: mat1[][] = [[1, 2, 3], mat2[][] = [[7, 8],
[4, 5, 6]] [9, 10],
[11, 12]]
Output: [[58, 64],
[139, 154]]
Explanation: Matrix mat1[ ][ ] (2×3) is multiplied with Matrix mat2[ ][ ] (3×2) by computing
the dot product of a's rows with b's columns. This results in a new matrix of size 2×2
containing the summed products for each position.

Input: mat1[][] = [[17, 4], mat2[][] = [[9, 2],

[17, 16]] [7, 1]]
Output: [[181, 38],
[265, 50]]
Explanation: Matrix mat1[ ][ ] (2×2) is multiplied with Matrix mat2[ ][ ] (2×2) by computing
the dot product of a's rows with b's columns. This results in a new matrix of size 2×2
containing the summed products for each position.
[Approach 1] - Using Nested Loops - O(n * m * q) Time and O(n * q) Space
The main idea is to initializes the result matrix with zeros and fills each cell by computing the
dot product of the corresponding row from a and column from . This is done using three
nested loops: the outer two iterate over the result matrix cells, and the innermost loop
performs the multiplication and addition.
#include <iostream>
#include <vector>
using namespace std;

vector<vector<int>> multiply(vector<vector<int>> &mat1,

vector<vector<int>> &mat2) {

int n = mat1.size(), m = mat1[0].size(),

q = mat2[0].size();

// Initialize the result matrix with

// dimensions n×q, filled with 0s
vector<vector<int>> res(n, vector<int>(q, 0));

// Loop through each row of mat1

for (int i = 0; i < n; i++) {

// Loop through each column of mat2

for (int j = 0; j < q; j++) {

// Compute the dot product of

// row mat1[i] and column mat2[][j]
for (int k = 0; k < m; k++) {
res[i][j] += mat1[i][k] * mat2[k][j];
}
}
}

return res;
}

int main() {
vector<vector<int>> mat1 = {
{1, 2, 3},
{4, 5, 6}
};

vector<vector<int>> mat2 = {
 {7, 8},
{9, 10},
{11, 12}
};

vector<vector<int>> res = multiply(mat1, mat2);

// Print the resulting matrix

for (int i = 0; i < res.size(); i++) {
for (int j = 0; j < res[i].size(); j++) {
cout << res[i][j] << " ";
}
cout << endl;
}

return 0;
}

Output
58 64
139 154

[Approach 2] - Using Divide and Conquer - O(n * m * q) Time and O(n * q) Space
The main idea is to multiply two matrices by following the standard row-by-column
multiplication method. For each element in the result matrix, it takes a row from the first
matrix and a column from the second matrix, multiplies their corresponding elements, and
adds them up to get a single value. This process is repeated for every position in the result
matrix.
#include <iostream>
#include <vector>
using namespace std;

// Function to add two matrices of same dimensions r×c

vector<vector<int>> add(vector<vector<int>> &mat1,
vector<vector<int>> &mat2) {
int r = mat1.size();
int c = mat1[0].size();

// Initialize result matrix with dimensions r×c

vector<vector<int>> res(r, vector<int>(c, 0));

// Perform element-wise addition

for (int i = 0; i < r; ++i) {
for (int j = 0; j < c; ++j) {
res[i][j] = mat1[i][j] + mat2[i][j];
}
}

return res;
}

// Function to multiply mat1 (n×m)

// with mat2 (m×q)
vector<vector<int>> multiply(vector<vector<int>> &mat1,
vector<vector<int>> &mat2) {
int n = mat1.size();
int m = mat1[0].size();
int q = mat2[0].size();

// Initialize result matrix with dimensions n×q

vector<vector<int>> res(n, vector<int>(q, 0));

// Matrix multiplication logic

for (int i = 0; i < n; ++i) {
for (int j = 0; j < q; ++j) {
for (int k = 0; k < m; ++k) {
res[i][j] += mat1[i][k] * mat2[k][j];
}
}
}

return res;
}

int main() {
vector<vector<int>> mat1 = {
{1, 2, 3},
{4, 5, 6}
};

vector<vector<int>> mat2 = {
{7, 8},
{9, 10},
{11, 12}
};

vector<vector<int>> res = multiply(mat1, mat2);

for (auto &row : res) {

for (int val : row) {
cout << val << " ";
}
cout << endl;
}

return 0;
}

Output
58 64
139 154
[Approach 3] - Using Strassen's Method
Strassen’s algorithm originally applies to square matrices, but when adapted for multiplying
an n*m matrix with an m*q matrix, the matrices are padded to form square matrices of size
s*s where s = next power of two ≥ max(n, m, q). The algorithm then performs 7 recursive
multiplications on these square blocks.

Note: Strass en's Method is often not preferred in practice due to its high constant
factors, making the naive method faster for typical applications. It performs poorly with
sparse matrices, where specialized algorithms work better. The recursive submatrix
divisions require extra memory. Additionally, due to limited precision in floating-point
arithmetic, Strassen’s algorithm tends to accumulate more errors than the naive approach.
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

// Return the next power of two greater than or equal to n

int nextPowerOfTwo(int n) {
return pow(2, ceil(log2(n)));
}

// Resize a matrix to newR x newC and

// fill extra space with zeros
vector<vector<int>> resizeMatrix(vector<vector<int>> &mat,
int newR, int newC) {

vector<vector<int>> resized(newR, vector<int>(newC, 0));

for (int i = 0; i < mat.size(); ++i)
for (int j = 0; j < mat[0].size(); ++j)
resized[i][j] = mat[i][j];

return resized;
}

// Perform matrix addition or subtraction

// of size×size matrices
// sign = 1 for addition, -1 for subtraction
vector<vector<int>> add(vector<vector<int>> a,
vector<vector<int>> b, int size, int sign = 1) {
vector<vector<int>> res(size, vector<int>(size));
for (int i = 0; i < size; i++)
for (int j = 0; j < size; j++)
res[i][j] = a[i][j] + sign * b[i][j];
return res;
}

// Recursive implementation of Strassen's

// matrix multiplication
// Assumes both matrices are size×size
// and size is a power of 2
vector<vector<int>> strassen(vector<vector<int>> mat1,
vector<vector<int>> mat2) {
int n = mat1.size();

// Base case: 1×1 matrix multiplication

vector<vector<int>> res(n, vector<int>(n, 0));
if (n == 1) {
res[0][0] = mat1[0][0] * mat2[0][0];
return res;
}

// Split matrices into 4 submatrices

int newSize = n / 2;
vector<vector<int>> a11(newSize, vector<int>(newSize));
vector<vector<int>> a12(newSize, vector<int>(newSize));
vector<vector<int>> a21(newSize, vector<int>(newSize));
vector<vector<int>> a22(newSize, vector<int>(newSize));
 vector<vector<int>> b11(newSize, vector<int>(newSize));
vector<vector<int>> b12(newSize, vector<int>(newSize));
vector<vector<int>> b21(newSize, vector<int>(newSize));
vector<vector<int>> b22(newSize, vector<int>(newSize));

// Fill the submatrices

for (int i = 0; i < newSize; i++)
for (int j = 0; j < newSize; j++) {
a11[i][j] = mat1[i][j];
a12[i][j] = mat1[i][j + newSize];
a21[i][j] = mat1[i + newSize][j];
a22[i][j] = mat1[i + newSize][j + newSize];
b11[i][j] = mat2[i][j];
b12[i][j] = mat2[i][j + newSize];
b21[i][j] = mat2[i + newSize][j];
b22[i][j] = mat2[i + newSize][j + newSize];
}

// Compute the 7 products using Strassen’s formulas

auto m1 = strassen(add(a11, a22, newSize), add(b11, b22, newSize));
auto m2 = strassen(add(a21, a22, newSize), b11);
auto m3 = strassen(a11, add(b12, b22, newSize, -1));
auto m4 = strassen(a22, add(b21, b11, newSize, -1));
auto m5 = strassen(add(a11, a12, newSize), b22);
auto m6 = strassen(add(a21, a11, newSize, -1), add(b11, b12, newSize));
auto m7 = strassen(add(a12, a22, newSize, -1), add(b21, b22, newSize));

// Calculate result quadrants from m1...m7

auto c11 = add(add(m1, m4, newSize), add(m7, m5, newSize, -1), newSize);
auto c12 = add(m3, m5, newSize);
auto c21 = add(m2, m4, newSize);
auto c22 = add(add(m1, m3, newSize), add(m6, m2, newSize, -1), newSize);

// Combine result quadrants into final matrix

for (int i = 0; i < newSize; i++)
for (int j = 0; j < newSize; j++) {
res[i][j] = c11[i][j];
res[i][j + newSize] = c12[i][j];
res[i + newSize][j] = c21[i][j];
res[i + newSize][j + newSize] = c22[i][j];
}

return res;
}
// Multiply mat1 (n×m) and mat2 (m×q)
// using Strassen’s method
vector<vector<int>> multiply(vector<vector<int>> &mat1,
vector<vector<int>> &mat2) {
// Compute size of the smallest power of 2 ≥ max(n, m, q)
int n = mat1.size(), m = mat1[0].size(), q = mat2[0].size() ;
int size = nextPowerOfTwo(max(n, max(m, q)));

// Pad both matrices to size×size with zeros

vector<vector<int>> aPad = resizeMatrix(mat1, size, size);
vector<vector<int>> bPad = resizeMatrix(mat2, size, size);

// Perform Strassen multiplication on padded matrices

vector<vector<int>> cPad = strassen(aPad, bPad);

// Extract the valid n×q result from the padded result

vector<vector<int>> C(n, vector<int>(q));
for (int i = 0; i < n; i++)
for (int j = 0; j < q; j++)
C[i][j] = cPad[i][j];

return C ;
}

int main() {
vector<vector<int>> mat1 = {{1, 2, 3}, {4, 5, 6}};
vector<vector<int>> mat2 = {{7, 8}, {9, 10}, {11, 12}};

vector<vector<int>> res = multiply(mat1, mat2);

for (auto &row : res) {

for (int val : row) {
cout << val << " " ;
}
cout << endl;
}

return 0;
}

Output
58 64
139 154
Time Complexity: O(s³) to O(s^log₂7) ≈ O(s^2.807), where s is the next power of two greater
than max(n, m, q), due to only 7 recursive multiplications.
Auxiliary Space: O(s²) because of the padding and the creation of intermediate submatrices
during recursion.

Heap Sort :
Heap sort is a comparison-based sorting technique based on Binary Heap Data Structure. It
can be seen as an optimization over selection sort where we first find the max (or min)
element and swap it with the last (or first). We repeat the same process for the remaining
elements. In Heap Sort, we use Binary Heap so that we can quickly find and move the max
element in O(Log n) instead of O(n) and hence achieve the O(n Log n) time complexity.

Heap Sort Algorithm

First convert the array into a max heap using heapify, Please note that this happens in-
place. The array elements are re-arranged to follow heap properties. Then one by one
delete the root node of the Max-heap and replace it with the last node and heapify. Repeat
this process while size of heap is greater than 1.
• Rearrange array elements so that they form a Max Heap.
• Repeat the following steps until the heap contains only one element:
 o Swap the root element of the heap (which is the largest element in current
heap) with the last element of the heap.
o Remove the last element of the heap (which is now in the correct position).
We mainly reduce heap size and do not remove element from the actual
array.
o Heapify the remaining elements of the heap.
• Finally we get sorted array.

Detailed Working of Heap Sort

Step 1: Treat the Array as a Complete Binary Tree
We first need to visualize the array as a complete binary tree. For an array of size n, the
root is at index 0, the left child of an element at index i is at 2i + 1, and the right child is at 2i
+ 2.

Step 2: Build a Max Heap

Step 3: Sort the array by placing largest element at end of unsorted array.
Implementation of Heap Sort
// C++ program for implementation of Heap Sort using vector

#include <bits/stdc++.h>
using namespace std;

// To heapify a subtree rooted with node i

// which is an index in arr[].
void heapify(vector<int>& arr, int n, int i){

// Initialize largest as root

int largest = i;

// left index = 2*i + 1

int l = 2 * i + 1;

// right index = 2*i + 2

int r = 2 * i + 2;

// If left child is larger than root

if (l < n && arr[l] > arr[largest])
largest = l;

// If right child is larger than largest so far

if (r < n && arr[r] > arr[largest])
largest = r;

// If largest is not root

if (largest != i) {
swap(arr[i], arr[largest]);

// Recursively heapify the affected sub-tree

heapify(arr, n, largest);
}
}

// Main function to do heap sort

void heapSort(vector<int>& arr){
int n = arr.size();

// Build heap (rearrange vector)

for (int i = n / 2 - 1; i >= 0; i--)
 heapify(arr, n, i);

// One by one extract an element from heap

for (int i = n - 1; i > 0; i--) {

// Move current root to end

swap(arr[0], arr[i]);

// Call max heapify on the reduced heap

heapify(arr, i, 0);
}
}

// A utility function to print vector of size n

void printArray(vector<int>& arr){
for (int i = 0; i < arr.size(); ++i)
cout << arr[i] << " ";
cout << "\n";
}

// Driver's code
int main(){
vector<int> arr = { 9, 4, 3, 8, 10, 2, 5 };

// Function call
heapSort(arr);

cout << "Sorted array is \n";

printArray(arr);
}

Output
Sorted array is
2 3 4 5 8 9 10

Complexity Analysis of Heap Sort

Time Complexity: O(n log n)
Auxiliary Space: O(log n), due to the recursive call stack. However, auxiliary space can be
O(1) for iterative implementation.
Important points about Heap Sort
• Heap sort is an in-place algorithm.
• Its typical implementation is not stable but can be made stable (See this)
• Typically 2-3 times slower than well-implemented QuickSort. The reason for
slowness is a lack of locality of reference.
Advantages of Heap Sort
• Efficient Time Complexity: Heap Sort has a time complexity of O(n log n) in all cases.
This makes it efficient for sorting large datasets. The log n factor comes from the
height of the binary heap, and it ensures that the algorithm maintains good
performance even with a large number of elements.
• Memory Usage: Memory usage can be minimal (by writing an iterative heapify()
instead of a recursive one). So apart from what is necessary to hold the initial list of
items to be sorted, it needs no additional memory space to work
• Simplicity: It is simpler to understand than other equally efficient sorting algorithms
because it does not use advanced computer science concepts such as recursion.
Disadvantages of Heap Sort
• Costly: Heap sort is costly as the constants are higher compared to merge sort even
if the time complexity is O(n Log n) for both.
• Unstable: Heap sort is unstable. It might rearrange the relative order.
• Inefficient: Heap Sort is not very efficient because of the high constants in the time
complexity.

Runtime Analysis of Divide and Conquer Algorithms

Divide and Conquer is an algorithmic paradigm that solves a problem by:
1. Dividing it into smaller subproblems,
2. Conquering (solving) the subproblems recursively,
3. Combining their solutions to solve the original problem.
Recurrence relation:
What is Recurrence Relation?
A recurrence relation is a mathematical expression that defines a sequence in terms of its
previous terms. In the context of algorithmic analysis, it is often used to model the time
complexity of recursive algorithms.
General form of a Recurrence Relation:
an=f(an−1,an−2,....,an−k)an=f(an−1,an−2,....,an−k)
where f is a function that defines the relationship between the current term and the
previous terms

There are mainly three ways of solving recurrences:

1. Substitution Method
2. Recurrence Tree Method
3. Master Method

1. Substitution Method:
We make a guess for the solution and then we use mathematical induction to prove the
guess is correct or incorrect.
For example, consider the recurrence T(n) = 2T(n/2) + n
We guess the solution as T(n) = O(nLogn). Now we use induction to prove our guess.
We need to prove that T(n) <= cnLogn. We can assume that it is true for values smaller than
n.
T(n) = 2T(n/2) + n
<= 2cn/2Log(n/2) + n
= cnLogn – cnLog2 + n
= cnLogn – cn + n
<= cnLogn
2. Recurrence Tree Method:
In this method, we draw a recurrence tree and calculate the time taken by every level of the
tree. Finally, we sum the work done at all levels. To draw the recurrence tree, we start from
the given recurrence and keep drawing till we find a pattern among levels. The pattern is
typically arithmetic or geometric series.
Consider the recurrence relation, T(n) = T(n/4) + T(n/2) + cn2n2
cn2n2
/ \
T(nn/4) T(nn/2)
If we further break down the expression T(nn/4) and T(nn/2), we get the following recursion
tree.
cn2n2
/ \
c(n2n2)/16 c(n2n2)/4
/ \ / \
T(nn/16) T(nn/8) T(nn/8) T(nn/4)
Breaking down further gives us following
cn2n2
/ \
c(n2n2)/16 c(n2n2)/4
/ \ / \
c(n2n2)/256 c(n2n2)/64 c(n2n2)/64 c(n2n2)/16
/ \ / \ / \ / \
To know the value of T(n), we need to calculate the sum of tree nodes level by level. If we
sum the above tree level by level, we get the following series T(n) =
cn2(1+5/16+25/256)cn2(1+5/16+25/256) + ….
The above series is a geometrical progression with a ratio of 5/16.
To get an upper bound, we can sum the infinite series. We get the sum as (cn2cn2)/(1 –
5/16) which is O(n2n2)

3. Master Method:
Master Method is a direct way to get the solution. The master method works only for the
following type of recurrences or for recurrences that can be transformed into the following
type.

T(n) = aT(n/b) + f(n) where a >= 1 and b > 1

There are the following three cases:
• Iff(n)=O(nc)wherec<LogbathenT(n)=Θ(nLogba) Iff(n)=Θ(nc)wherec=LogbathenT(n)=Θ
(ncLogn) Iff(n)=Ω(nc)wherec>LogbathenT(n)=Θ(f(n)) Iff(n)=O(nc)wherec<Logb
athenT(n)=Θ(nLogba) Iff(n)=Θ(nc)wherec=Logba
thenT(n)=Θ(ncLogn) Iff(n)=Ω(nc)wherec>LogbathenT(n)=Θ(f(n))
How does this work?
The master method is mainly derived from the recurrence tree method. If we draw the
recurrence tree of T(n) = aT(n/b) + f(n), we can see that the work done at the root is f(n),
and work done at all leaves is Θ(nc) where c is LogbaLogba. And the height of the
recurrence tree is LogbnLogbn

In the Recurrence Tree Method, we calculate the total work done. If the work done at
leaves is polynomial more, then leaves are the dominant part, and our result becomes the
work done at leaves (Case 1). If work done at leaves and root is asymptotically the same,
then our result becomes height multiplied by work done at any level (Case 2). If work done
at the root is asymptotically more, then our result becomes work done at the root (Case 3).
UNIT-3:
Greedy Algorithm:
The Greedy Paradigm is a problem-solving strategy where you:
Make the locally optimal choice at each step with the hope that it leads to a globally
optimal solution.
It doesn’t always guarantee an optimal solution, but for many problems with the right
structure, it does.

Greedy is an algorithmic paradigm that builds up a solution piece by piece, always choosing
the next piece that offers the most obvious and immediate benefit. Greedy algorithms are
used for optimization problems.

Key Features of Greedy Algorithms:

• Makes greedy choice: picks the best available option without reconsidering previous
choices.
• Builds solution step-by-step.
• No backtracking or recursion (unlike DP or divide and conquer).
• Works when problem has Greedy-Choice Property and Optimal Substructure.

However, it's important to note that not all problems are suitable for greedy algorithms.
They work best when the problem exhibits the following properties:
• Greedy Choice Property: The optimal solution can be constructed by making
the best local choice at each step.
• Optimal Substructure: The optimal solution to the problem contains the optimal
solutions to its subproblems.

Characteristics of Greedy Algorithm

Here are the characteristics of a greedy algorithm:
• Greedy algorithms are simple and easy to implement.
• They are efficient in terms of time complexity, often providing quick solutions.
Greedy Algorithms are typically preferred over Dynamic Programming for the
problems where both are applied. For example, Jump Game problem and Single
Source Shortest Path Problem (Dijkstra is preferred over Bellman Ford where we do
not have negative weights).
• These algorithms do not reconsider previous choices, as they make decisions based
on current information without looking ahead.

How does the Greedy Algorithm works?

Greedy Algorithm solve optimization problems by making the best local choice at each step
in the hope of finding the global optimum. It's like taking the best option available at each
moment, hoping it will lead to the best overall outcome.
Here's how it works:
1. Start with the initial state of the problem. This is the starting point from where you
begin making choices.
2. Evaluate all possible choices you can make from the current state. Consider all the
options available at that specific moment.
3. Choose the option that seems best at that moment, regardless of future
consequences. This is the "greedy" part - you take the best option available now,
even if it might not be the best in the long run.
4. Move to the new state based on your chosen option. This becomes your new
starting point for the next iteration.
5. Repeat steps 2-4 until you reach the goal state or no further progress is possible.
Keep making the best local choices until you reach the end of the problem or get
stuck.

Example:
Let's say you have a set of coins with values [1, 2, 5, 10] and you need to give minimum
number of coin to someone change for 39.
The greedy algorithm for making change would work as follows:
• Step-1: Start with the largest coin value that is less than or equal to the amount to
be changed. In this case, the largest coin less than or equal to 39 is 10.
• Step- 2: Subtract the largest coin value from the amount to be changed, and add the
coin to the solution. In this case, subtracting 10 from 39 gives 29, and we add one
10-coin to the solution.
Repeat steps 1 and 2 until the amount to be changed becomes 0.

Minimum Cost Spanning Tree (MST):

A Minimum Cost Spanning Tree (MST) is a spanning tree of a connected, undirected graph
that has the minimum possible total edge weight.

Definitions
• Spanning Tree: A subgraph that is a tree and connects all vertices of the original
graph.
• Minimum Cost Spanning Tree: A spanning tree with the smallest sum of edge
weights among all possible spanning trees of the graph.

Properties of MST
1. Has V - 1 edges, where V is the number of vertices.
2. No cycles.
3. Connects all vertices.
4. Minimizes total edge weight.
Example
In the following graph, the highlighted edges form a spanning tree.

Minimum Spanning Tree

A Minimum Spanning Tree (MST) is a subset of edges of a connected weighted undirected
graph that connects all the vertices together with the minimum possible total edge weight.
To derive an MST, Prims algorithm or Kruskals algorithm can be used.

Kruskal’s Minimum Spanning Tree (MST) Algorithm

A minimum spanning tree (MST) or minimum weight spanning tree for a weighted,
connected, and undirected graph is a spanning tree (no cycles and connects all vertices) that
has minimum weight. The weight of a spanning tree is the sum of all edges in the tree.
In Kruskal's algorithm, we sort all edges of the given graph in increasing order. Then it keeps
on adding new edges and nodes in the MST if the newly added edge does not form a cycle.
It picks the minimum weighted edge at first and the maximum weighted edge at last. Thus
we can say that it makes a locally optimal choice in each step in order to find the optimal
solution. Hence this is a Greedy Algorithm.

How to find MST using Kruskal's algorithm?

Below are the steps for finding MST using Kruskal's algorithm:
• Sort all the edges in a non-decreasing order of their weight.
• Pick the smallest edge. Check if it forms a cycle with the spanning tree formed so far.
If the cycle is not formed, include this edge. Else, discard it.
• Repeat step 2 until there are (V-1) edges in the spanning tree.
Kruskal's Algorithm uses the Disjoint Set Data Structure to detect cycles.

Time Complexity: O(E * log E) or O(E * log V)

• Sorting of edges takes O(E*logE) time.
• After sorting, we iterate through all edges and apply the find-union algorithm. The
find and union operations can take at most O(logV) time.
• So overall complexity is O(E*logE + E*logV) time.
 • The value of E can be at most O(V2), so O(logV) and O(logE) are the same. Therefore,
the overall time complexity is O(E * logE) or O(E*logV)

Auxiliary Space: O(E+V), where V is the number of vertices and E is the number of edges in
the graph.

Prim’s Algorithm for Minimum Spanning Tree (MST):

Prim’s algorithm is a Greedy algorithm like Kruskal's algorithm. This algorithm always starts
with a single node and moves through several adjacent nodes, in order to explore all of the
connected edges along the way.
• The algorithm starts with an empty spanning tree.
• The idea is to maintain two sets of vertices. The first set contains the vertices already
included in the MST, and the other set contains the vertices not yet included.
• At every step, it considers all the edges that connect the two sets and picks the
minimum weight edge from these edges. After picking the edge, it moves the other
endpoint of the edge to the set containing MST.

How to implement Prim's Algorithm?

Follow the given steps to utilize the Prim's Algorithm mentioned above for finding MST of a
graph:
• Create a set mstSet that keeps track of vertices already included in MST.
• Assign a key value to all vertices in the input graph. Initialize all key values as
INFINITE. Assign the key value as 0 for the first vertex so that it is picked first.
• While mstSet doesn't include all vertices
o Pick a vertex u that is not there in mstSet and has a minimum key value.
o Include u in the mstSet.
o Update the key value of all adjacent vertices of u. To update the key values,
iterate through all adjacent vertices. For every adjacent vertex v, if the weight
of edge u-v is less than the previous key value of v, update the key value as
the weight of u-v.
The idea of using key values is to pick the minimum weight edge from the cut. The key
values are used only for vertices that are not yet included in MST, the key value for these
vertices indicates the minimum weight edges connecting them to the set of vertices
included in MS

Advantages and Disadvantages of Prim's algorithm

Advantages:
• Prim's algorithm is guaranteed to find the MST in a connected, weighted graph.
• It has a time complexity of O((E+V)*log(V)) using a binary heap or Fibonacci heap,
where E is the number of edges and V is the number of vertices.
• It is a relatively simple algorithm to understand and implement compared to some
other MST algorithms.
Disadvantages:
• Like Kruskal's algorithm, Prim's algorithm can be slow on dense graphs with many
edges, as it requires iterating over all edges at least once.
• Prim's algorithm relies on a priority queue, which can take up extra memory and
slow down the algorithm on very large graphs.
• The choice of starting node can affect the MST output, which may not be desirable in
some applications.

Knapsack Problem — D
The Knapsack Problem is a classic optimization problem used in Greedy, Dynamic
Programming, and Backtracking approaches.

Problem Statement
Given n items, each with a weight w[i] and value v[i], find the maximum value that can be
obtained by selecting items such that the total weight does not exceed a given limit W
(knapsack capacity).

Types of Knapsack Problems

Type Description
0/1 Knapsack Each item can either be selected (1) or not (0).
Fractional Knapsack Items can be broken into smaller parts (greedy solution possible).
Unbounded Knapsack You can take any item multiple times.

0/1 Knapsack Problem:

Given n items where each item has some weight and profit associated with it and also given
a bag with capacity W, [i.e., the bag can hold at most W weight in it]. The task is to put the
items into the bag such that the sum of profits associated with them is the maximum
possible.
Note: The constraint here is we can either put an item completely into the bag or cannot
put it at all [It is not possible to put a part of an item into the bag].
Input: W = 4, profit[] = [1, 2, 3], weight[] = [4, 5, 1]
Output: 3
Explanation: There are two items which have weight less than or equal to 4. If we select the
item with weight 4, the possible profit is 1. And if we select the item with weight 1, the
possible profit is 3. So the maximum possible profit is 3. Note that we cannot put both the
items with weight 4 and 1 together as the capacity of the bag is 4.
Input: W = 3, profit[] = [1, 2, 3], weight[] = [4, 5, 6]
Output: 0

2. Fractional Knapsack Problem(Greedy)

Given two arrays, val[] and wt[], representing the values and weights of items, and an
integer capacity representing the maximum weight a knapsack can hold, the task is to
determine the maximum total value that can be achieved by putting items in the knapsack.
You are allowed to break items into fractions if necessary.
Approach:
1. Calculate value/weight ratio for each item.
2. Sort by this ratio.
3. Take item fully until full or partially if remaining capacity is less.

Examples:
Input: val[] = [60, 100, 120], wt[] = [10, 20, 30], capacity = 50
Output: 240
Explanation: By taking items of weight 10 and 20 kg and 2/3 fraction of 30 kg.
Hence total price will be 60+100+(2/3)(120) = 240
Input: val[] = [500], wt[] = [30], capacity = 10
Output: 166.667

Approach:
An efficient solution is to use the Greedy approach.
The basic idea of the greedy approach is to calculate the ratio profit/weight for each item
and sort the item on the basis of this ratio. Then take the item with the highest ratio and add
them as much as we can (can be the whole element or a fraction of it).
This will always give the maximum profit because, in each step it adds an element such that
this is the maximum possible profit for that much weight.

Illustration:
Check the below illustration for a better understanding:
Consider the example: val[] = [60, 100, 120], wt[] = [10, 20, 30], capacity = 50. Store the
value and weight of each item in form {value, weight}. items[] = {{60, 10}, {100, 20}, {120,
30}}.
Sorting: Initially sort the array based on the profit/weight ratio. The sorted array will be
{{60, 10}, {100, 20}, {120, 30}}.
Iteration:
 • For i = 0, weight = 10 which is less than capacity. So add this element in the knapsack.
profit = 60 and remaining capacity = 50 - 10 = 40.
• For i = 1, weight = 20 which is less than capacity. So add this element too. profit = 60
+ 100 = 160 and remaining capacity = 40 - 20 = 20.
• For i = 2, weight = 30 is greater than capacity. So add 20/30 fraction = 2/3 fraction of
the element. Therefore profit = 2/3 * 120 + 160 = 80 + 160 = 240 and remaining
capacity becomes 0.
So the final profit becomes 240 for capacity = 50.
Step by step approach:
1. Calculate the ratio (profit/weight) for each item.
2. Sort all the items in decreasing order of the ratio.
3. Initialize res = 0, current capacity= given capacity.
4. Do the following for every item i in the sorted order:
• If the weight of the current item is less than or equal to the remaining
capacity then add the value of that item into the result
• Else add the current item as much as we can and break out of the loop.
5. Return res.

Time Complexity:
O(n log n) (due to sorting)
Auxiliary Space:
O(n)
Suitable for:
• When items can be divided (e.g., gold, grains, etc.)
Dijkstra's Algorithm to find Shortest Paths from a Source to all:

Given a weighted undirected graph represented as an edge list and a source vertex src, find
the shortest path distances from the source vertex to all other vertices in the graph. The
graph contains V vertices, numbered from 0 to V - 1.

Note: The given graph does not contain any negative edge.

Algorithm Steps:
1. Set distance of source as 0, and all others as ∞.
2. Use a priority queue (or min-heap) to pick the vertex with the minimum distance.
3. For each neighbor of the current vertex, relax the edge:
markdown
Copy code
if (dist[u] + weight(u, v) < dist[v])
dist[v] = dist[u] + weight(u, v)
4. Repeat until all nodes are visited.

Time Complexity:
Data Structure Used Time Complexity
Min-Heap / Priority Queue O((V + E) log V)
Array (inefficient) O(V^2)

Limitation:
Does not work with negative edge weights.
Bellman-Ford Algorithm:
Used For:
• Works for graphs with negative weights
• Can detect negative weight cycles

Algorithm Steps:
1. Set all distances to ∞ except the source = 0.
2. Repeat (V - 1) times:
o For each edge (u, v), perform:
markdown
Copy code
if (dist[u] + weight(u, v) < dist[v])
dist[v] = dist[u] + weight(u, v)
3. After (V - 1) iterations, do one more iteration to check for negative weight cycles.
If any edge can be relaxed again → cycle exists.

Time Complexity:
scss
Copy code
O(V × E)

Approach: Bellman-Ford Algorithm - O(V*E) Time and O(V) Space

Negative weight cycle:
A negative weight cycle is a cycle in a graph, whose sum of edge weights is negative. If you
traverse the cycle, the total weight accumulated would be less than zero.
In the presence of negative weight cycle in the graph, the shortest path doesn't
exist because with each traversal of the cycle shortest path keeps decreasing.
Limitation of Dijkstra's Algorithm:
Since, we need to find the single source shortest path, we might initially think of
using Dijkstra's algorithm. However, Dijkstra is not suitable when the graph consists
of negative edges. The reason is, it doesn't revisit those nodes which have already been
marked as visited. If a shorter path exists through a longer route with negative edges,
Dijkstra's algorithm will fail to handle it.
Principle of Relaxation of Edges
• Relaxation means updating the shortest distance to a node if a shorter path is found
through another node. For an edge (u, v) with weight w:
o If going through u gives a shorter path to v from the source node
(i.e., distance[v] > distance[u] + w), we update the distance[v] as distance[u]
+ w.
• In the bellman-ford algorithm, this process is repeated (V - 1) times for all the edges.
Why Relaxing Edges (V - 1) times gives us Single Source Shortest Path?
A shortest path between two vertices can have at most (V - 1) edges. It is not possible to
have a simple path with more than (V - 1) edges (otherwise it would form a cycle).
Therefore, repeating the relaxation process (V - 1) times ensures that all possible paths
between source and any other node have been covered.
Assuming node 0 as the source vertex, let's see how we can relax the edges to find the
shortest paths:

• n the first relaxation, since the shortest paths for vertices 1 and 2 are unknown
(infinite, i.e., 108), the shortest paths for vertices 2 and 3 will also remain infinite
(108) . And, for vertex 1, the distance will be updated to 4, as dist[0] + 4 <
dist[1] (i.e., 0 + 4 < 108).
 • In the second relaxation, the shortest path for vertex 2 is still infinite (e.g. 108),
which means the shortest path for vertex 3 will also remain infinite. For vertex 2, the
distance can be updated to 3, as dist[1] + (-1) = 3.
• In the third relaxation, the shortest path for vertex 3 will be updated to 5, as dist[2]
+ 2 = 5.
So, in above example, dist[1] is updated in 1st relaxation, dist[2] is updated in second
relaxation, so the dist for the last node (V - 1), will be updated in (V - 1) th relaxation.

Detection of a Negative Weight Cycle

• As we have discussed earlier that, we need (V - 1) relaxations of all the edges to
achieve single source shortest path. If one additional relaxation (Vth) for any edge is
possible, it indicates that some edges with overall negative weight has been
traversed once more. This indicates the presence of a negative weight cycle in the
graph.
Bellman-Ford is a single source shortest path algorithm. It effectively works in the cases of
negative edges and is able to detect negative cycles as well. It works on the principle of
relaxation of the edges.
Huffman Coding:
Huffman Coding is a lossless data compression algorithm. It assigns variable-length codes
to input characters — shorter codes to more frequent characters and longer codes to less
frequent ones — to minimize the overall size of the encoded data.

There are mainly two major parts in Huffman Coding

1. Build a Huffman Tree from input characters.
2. Traverse the Huffman Tree and assign codes to characters.

Steps in Huffman Coding Algorithm:

1. Input: A list of characters and their frequencies.
2. Create a priority queue (min-heap) of all characters based on their frequency.
3. While there is more than one node in the queue:
o Extract the two nodes with the lowest frequencies.
o Create a new internal node with these two as children.
Frequency = sum of the two.
o Insert this new node back into the queue.
4. The remaining node is the root of the Huffman Tree.
5. Traverse the tree:
o Left → add 0, Right → add 1 to code.
o Store the code for each charac

Steps to build Huffman Tree

Input is an array of unique characters along with their frequency of occurrences and output
is Huffman Tree.
1. Create a leaf node for each unique character and build a min heap of all leaf nodes
(Min Heap is used as a priority queue. The value of frequency field is used to
compare two nodes in min heap. Initially, the least frequent character is at root)
2. Extract two nodes with the minimum frequency from the min heap.
3. Create a new internal node with a frequency equal to the sum of the two nodes
frequencies. Make the first extracted node as its left child and the other extracted
node as its right child. Add this node to the min heap.
4. Repeat steps#2 and #3 until the heap contains only one node. The remaining node is
the root node and the tree is complete.
Let us understand the algorithm with an example:
character Frequency
a5
b9
c 12
d 13
e 16
f 45
Step 1. Build a min heap that contains 6 nodes where each node represents root of a tree
with single node.
Step 2 Extract two minimum frequency nodes from min heap. Add a new internal node with
frequency 5 + 9 = 14.

Illustration of step 2

Now min heap contains 5 nodes where 4 nodes are roots of trees with single element each,
and one heap node is root of tree with 3 elements
character Frequency
c 12
d 13
Internal Node 14
e 16
f 45
Step 3: Extract two minimum frequency nodes from heap. Add a new internal node with
frequency 12 + 13 = 25
Illustration of step 3

Now min heap contains 4 nodes where 2 nodes are roots of trees with single element each,
and two heap nodes are root of tree with more than one nodes
character Frequency
Internal Node 14
e 16
Internal Node 25
f 45
Step 4: Extract two minimum frequency nodes. Add a new internal node with frequency 14
+ 16 = 30

Illustration of step 4

Now min heap contains 3 nodes.

character Frequency
Internal Node 25
Internal Node 30
f 45
Step 5: Extract two minimum frequency nodes. Add a new internal node with frequency 25
+ 30 = 55

Illustration of step 5

Now min heap contains 2 nodes.

character Frequency
f 45
Internal Node 55
Step 6: Extract two minimum frequency nodes. Add a new internal node with frequency 45
+ 55 = 100

Illustration of step 6
Now min heap contains only one node.
character Frequency
Internal Node 100
Since the heap contains only one node, the algorithm stops here.
Steps to print codes from Huffman Tree:
Traverse the tree formed starting from the root. Maintain an auxiliary array. While moving
to the left child, write 0 to the array. While moving to the right child, write 1 to the array.
Print the array when a leaf node is encountered.

Steps to print code from HuffmanTree

The codes are as follows:

character code-word
f0
c 100
d 101
a 1100
b 1101
e 111
Activity Selection Problem:
Given n activities with start times in start[] and finish times in finish[], find the maximum
number of activities a single person can perform without overlap. A person can only do one
activity at a time.
Each activity i has:
• Start time: s[i]
• End time: f[i]

Examples:
Input: start[] = [1, 3, 0, 5, 8, 5], finish[] = [2, 4, 6, 7, 9, 9]
Output: 4
Explanation: A person can perform at most four activities. The maximum set of activities
that can be performed is {0, 1, 3, 4} (these are the indexes in the start[] and finish[] arrays).
Input: start[] = [10, 12, 20], finish[] = [20, 25, 30]
Output: 1
Explanation: A person can perform at most one activity.

Generate All Subsets - O(n^2 * 2^n) Time and O(n) Space

Generates all possible subsets of activities, where each subset represents a potential
selection. For each subset, we check if the activities are mutually non-overlapping by
comparing their time intervals pairwise. If a subset is valid and contains more activities than
our current maximum, we update the maximum count. In the end, we get the size of the
largest valid subset.
Greedy Strategy:
Always select the activity that finishes earliest (i.e., has the minimum finishing time) and is
compatible with the previously selected activity.

Algorithm Steps:
1. Sort all activities by their finishing times (f[i]).
2. Select the first activity (it has the earliest finish time).
3. For the rest of the activities:
o If the start time of the current activity ≥ finish time of the last selected
activity, then select it.
4. Repeat until all activities are checked.

Example:
Given:
text
Copy code
Activities: A1 A2 A3 A4 A5 A6
Start Time: 1 3 0 5 8 5
Finish Time: 2 4 6 7 9 9
Step 1: Sort by Finish Time
Activity Start Finish
A1 1 2
A2 3 4
A4 5 7
A5 8 9
A6 5 9
A3 0 6
Step 2: Select A1 (first activity)
• A2: start=3 ≥ 2 → select
• A4: start=5 ≥ 4 → select
• A5: start=8 ≥ 7 → select
• A6: start=5 < 7 → skip
• A3: start=0 < 2 → skip
Selected Activities: A1, A2, A4, A5

⏱ Time Complexity:
• Sorting: O(n log n)
• Selection: O(n)
• Total: O(n log n)
Applications:
• CPU scheduling
• Meeting room scheduling
• Task selection in embedded systems
Unit – 4(Dynamic Programming):
Dynamic Programming (DP) Introduction:
Dynamic Programming is a commonly used algorithmic technique used to optimize recursive
solutions when same subproblems are called again.
• The core idea behind DP is to store solutions to subproblems so that each is solved
only once.
• To solve DP problems, we first write a recursive solution in a way that there are
overlapping subproblems in the recursion tree (the recursive function is called with
the same parameters multiple times)
• To make sure that a recursive value is computed only once (to improve time taken
by algorithm), we store results of the recursive calls.
• There are two ways to store the results, one is top down (or memoization) and other
is bottom up (or tabulation).

When to Use Dynamic Programming (DP)?

Dynamic programming is used for solving problems that consists of the following
characteristics:
1. Optimal Substructure
If an optimal solution to the problem contains optimal solutions to its subproblems, then
the problem has an optimal substructure.

Example:
In the Fibonacci sequence,
Fib(n) = Fib(n-1) + Fib(n-2)
Optimal result Fib(n) is formed using the optimal results of subproblems Fib(n-1) and Fib(n-
2).

2. Overlapping Subproblems
A problem has overlapping subproblems if it can be broken down into smaller subproblems
that are reused multiple times.
Example:
In naive recursion, Fib(5) calls Fib(4) and Fib(3),
but Fib(4) again calls Fib(3), and so on. These repeat — thus overlapping.

Approaches of Dynamic Programming (DP)

Dynamic programming can be achieved using two approaches:
1. Top-Down Approach (Memoization):
In the top-down approach, also known as memoization, we keep the solution recursive and
add a memoization table to avoid repeated calls of same subproblems.
• Before making any recursive call, we first check if the memoization table already has
solution for it.
• After the recursive call is over, we store the solution in the memoization table.
2. Bottom-Up Approach (Tabulation):
In the bottom-up approach, also known as tabulation, we start with the smallest
subproblems and gradually build up to the final solution.
• We write an iterative solution (avoid recursion overhead) and build the solution in
bottom-up manner.
• We use a dp table where we first fill the solution for base cases and then fill the
remaining entries of the table using recursive formula.
• We only use recursive formula on table entries and do not make recursive calls.

Below is the recursion tree of the above recursive solution.

The time complexity of the above approach is exponential and upper bounded by O(2n) as
we make two recursive calls in every function.

How will Dynamic Programming (DP) Work?

Let’s us now see the above recursion tree with overlapping subproblems highlighted with
same color. We can clearly see that that recursive solution is doing a lot work again and
again which is causing the time complexity to be exponential. Imagine time taken for
computing a large Fibonacci number.

• Identify Subproblems: Divide the main problem into smaller, independent

subproblems, i.e., F(n-1) and F(n-2)
• Store Solutions: Solve each subproblem and store the solution in a table or array so
that we do not have to recompute the same again.
• Build Up Solutions: Use the stored solutions to build up the solution to the main
problem. For F(n), look up F(n-1) and F(n-2) in the table and add them.
• Avoid Recomputation: By storing solutions, DP ensures that each subproblem (for
example, F(2)) is solved only once, reducing computation time.

Using Memoization Approach - O(n) Time and O(n) Space

To achieve this in our example we simply take an memo array initialized to -1. As we make a
recursive call, we first check if the value stored in the memo array corresponding to that
position is -1. The value -1 indicates that we haven't calculated it yet and have to recursively
compute it. The output must be stored in the memo array so that, next time, if the same
value is encountered, it can be directly used from the memo array.

Advantages of Dynamic Programming (DP):

Dynamic programming has a wide range of advantages, including:
• Avoids recomputing the same subproblems multiple times, leading to significant
time savings.
• Ensures that the optimal solution is found by considering all possible combinations.

Applications of Dynamic Programming (DP):

Dynamic programming has a wide range of applications, including:
• Optimization: Knapsack problem, shortest path problem, maximum subarray
problem
• Computer Science: Longest common subsequence, edit distance, string matching
• Operations Research: Inventory management, scheduling, resource allocation
Application: Rod cutting problem:
Given a rod of length n inches and an array price[]. price[i] denotes the value of a piece of
length i. The task is to determine the maximum value obtainable by cutting up the rod and
selling the pieces.
Note: price[] is 1-indexed array.

Input: price[] = [1, 5, 8, 9, 10, 17, 17, 20]

Output: 22
Explanation: The maximum obtainable value is 22 by cutting in two pieces of lengths 2
and 6, i.e., 5 + 17 = 22.
Input : price[] = [3, 5, 8, 9, 10, 17, 17, 20]
Output : 24
Explanation : The maximum obtainable value is 24 by cutting the rod into 8 pieces of length
1, i.e, 8*price[1]= 8*3 = 24.
Input : price[] = [3]
Output : 3
Explanation: There is only 1 way to pick a piece of length 1.

Using Recursion - O(n^n) Time and O(n) Space

The recursive approach involves solving the problem by considering all possible ways to cut
the rod into two pieces at every length j (where 1<=j<=i), calculating the profit for each cut,
and finding the maximum profit among these options. At each step, the rod of length i is
divided into two parts: j and i - j. The profit from this cut is the sum of the price of the piece
of length j (given as price[j-1]) and the maximum profit obtainable from the remaining rod
of length i-j (computed recursively). The base case for this recursion is when i equals 0,
where the maximum profit is simply 0.
The recurrence relation will be:
• cutRod(i) = max(price[j-1] + cutRod(i-j)) for (1<=j<=i)
Base Case:
If i == 0, return 0.

Using Top-Down DP (Memoization) - O(n^2) Time and O(n) Space

If we notice carefully, we can observe that the above recursive solution holds the following
two properties of Dynamic Programming:
1. Optimal Substructure: Maximum profit at index i, i.e., cutRod(i), depends on the optimal
solutions of the subproblems cutRod(i-1) , cutRod(i-2), ..., cutRod(0) . By comparing these
optimal substructures, we can efficiently calculate the maximum profit at index i.
2. Overlapping Subproblems: While applying a recursive approach in this problem, we notice
that certain subproblems are computed multiple times.
• There is only 1 parameter: i that changes in the recursive solution. So we create a 1D
array of size n for memoization.
• We initialize this array as -1 to indicate nothing is computed initially.
• Now we modify our recursive solution to first check if the value is -1, then only make
recursive calls. This way, we avoid re-computations of the same subproblems.

Using Bottom-Up DP (Tabulation) - O(n^2) Time and O(n) Space

The idea is to fill the dp table from bottom to up. For each rod of length i, starting from i = 1
to i = n, find the maximum value that can obtained by cutting it into two pieces of length j
and (i-j).
Floyd Warshall Algorithm:

Given a matrix dist[][] of size n x n, where dist[i][j] represents the weight of the edge from
node i to node j. If there is no direct edge, dist[i][j] is set to a large value (e.g., 10⁸) to
represent infinity. The diagonal entries dist[i][i] are 0, since the distance from a node to
itself is zero. The graph may contain negative edge weights, but it does not contain any
negative weight cycles.

Your task is to determine the shortest path distance between all pair of nodes i and j in the
graph.

Example:
Input: dist[][] = [[0, 4, 10⁸, 5, 10⁸],
[10⁸, 0, 1, 10⁸, 6],
[2, 10⁸, 0, 3, 10⁸],
[10⁸, 10⁸, 1, 0, 2],
[1, 10⁸, 10⁸, 4, 0]]
Output:[[0, 4, 5, 5, 7],
[3, 0, 1, 4, 6],
[2, 6, 0, 3, 5],
[3, 7, 1, 0, 2],
[1, 5, 5, 4, 0]]
Explanation:

Each cell dist[i][j] in the output shows the shortest distance from node i to node j, computed
by considering all possible intermediate nodes using the Floyd-Warshall algorithm.
Floyd Warshall Algorithm:
The Floyd–Warshall algorithm works by maintaining a two-dimensional array that
represents the distances between nodes. Initially, this array is filled using only the direct
edges between nodes. Then, the algorithm gradually updates these distances by checking if
shorter paths exist through intermediate nodes.
This algorithm works for both the directed and undirected weighted graphs and can handle
graphs with both positive and negative weight edges.
Note: It does not work for the graphs with negative cycles (where the sum of the edges in a
cycle is negative)

Idea Behind Floyd Warshall Algorithm:

Suppose we have a graph dist[][] with V vertices from 0 to V-1. Now we have to evaluate a
dist[][] where dist[i][j] represents the shortest path between vertex i to j.
Let us assume that vertices i to j have intermediate nodes. The idea behind Floyd Warshall
algorithm is to treat each and every vertex k from 0 to V-1 as an intermediate node one by
one. When we consider the vertex k, we must have considered vertices from 0 to k-1 already.
So we use the shortest paths built by previous vertices to build shorter paths with vertex k
included.
The following figure shows the above optimal substructure property in Floyd Warshall
algorithm:

Step-by-step implementation
 • Start by updating the distance matrix by treating each vertex as a possible
intermediate node between all pairs of vertices.
• Iterate through each vertex, one at a time. For each selected vertex k, attempt to
improve the shortest paths that pass through it.
• When we pick vertex number k as an intermediate vertex, we already have
considered vertices {0, 1, 2, .. k-1} as intermediate vertices.
• For every pair (i, j) of the source and destination vertices respectively, there are two
possible cases.
o k is not an intermediate vertex in shortest path from i to j. We keep the value
of dist[i][j] as it is.
o k is an intermediate vertex in shortest path from i to j. We update the value
of dist[i][j] as dist[i][k] + dist[k][j], if dist[i][j] > dist[i][k] + dist[k][j]
• Repeat this process for each vertex k until all intermediate possibilities have been
considered.

Time Complexity: O(V3), where V is the number of vertices in the graph and we run three
nested loops each of size V.
Auxiliary Space: O(1).

Matrix Chain Multiplication:

Given the dimension of a sequence of matrices in an array arr[], where the dimension of
the ith matrix is (arr[i-1] * arr[i]), the task is to find the most efficient way to multiply these
matrices together such that the total number of element multiplications is minimum. When
two matrices of size m*n and n*p when multiplied, they generate a matrix of size m*p and
the number of multiplications performed is m*n*p.

Examples:
Input: arr[] = [2, 1, 3, 4]
Output: 20
Explanation: There are 3 matrices of dimensions 2x1, 1x3, and 3x4,
Let the input 3 matrices be M1, M2, and M3. There are two ways to multiply ((M1 x M2) x
M3) and (M1 x (M2 x M3)),
Please note that the result of M1 x M2 is a 2 x 3 matrix and result of (M2 x M3) is a 1 x 4
matrix.
((M1 x M2) x M3) requires (2 x 1 x 3) + (2 x 3 x 4) = 30
(M1 x (M2 x M3)) requires (1 x 3 x 4) + (2 x 1 x 4) = 20
The minimum of these two is 20.
Input: arr[] = [1, 2, 3, 4, 3]
Output: 30
Explanation: There are 4 matrices of dimensions 1×2, 2×3, 3×4, 4×3. Let the input 4 matrices
be M1, M2, M3 and M4. The minimum number of multiplications are obtained by
((M1M2)M3)M4. The minimum number is 1*2*3 + 1*3*4 + 1*4*3 = 30
Input: arr[] = [3, 4]
Output: 0
Explanation: As there is only one matrix so, there is no cost of multiplication.

[Better Approach 1 ] Using Top-Down DP (Memoization) - O(n*n*n) and O(n*n) Space

Let's suppose we have four matrices (M1, M2, M3, M4). Based on the recursive approach
described above, we can construct a recursion tree. However, we can observe that some
problems are computed multiple times. To avoid this redundant computation, we can
implement memoization to store the results of previously computed inputs.

If observed carefully you can find the following two properties:

1) Optimal Substructure: In the above case, we are breaking the bigger groups into smaller
subgroups and solving them to finally find the minimum number of multiplications.
Therefore, it can be said that the problem has optimal substructure property.
2) Overlapping Subproblems: We can see in the recursion tree that the same subproblems
are called again and again and this problem has the Overlapping Subproblems property.
So Matrix Chain Multiplication problem has both properties of a dynamic programming
problem. So recomputations of same subproblems can be avoided by constructing a
temporary array memo[][] in a bottom up manner.

Follow the below steps to solve the problem:

• Build a matrix memo[][] of size n*n for memoization purposes.
• Use the same recursive call as done in the above approach:
o When we find a range (i, j) for which the value is already calculated, return
the minimum value for that range (i.e., memo[i][j]).
o Otherwise, perform the recursive calls as mentioned earlier.
• The value stored at memo[0][n-1] is the required answer.
Travelling Salesman Problem using Dynamic Programming:
Given a 2d matrix cost[][] of size n where cost[i][j] denotes the cost of moving from city i to
city j. The task is to complete a tour from city 0 (0-based index) to all other cities such that
we visit each city exactly once and then at the end come back to city 0 at minimum cost.

Examples:
Input: cost[][] = [[0, 111], [112, 0]]
Output: 223
Explanation: We can visit 0->1->0 and cost = 111 + 112 = 223.
Input: cost[][] = [[0, 1000, 5000], [5000, 0, 1000], [1000, 5000, 0]]
Output: 3000
Explanation: We can visit 0->1->2->0 and cost = 1000 + 1000 + 1000 = 3000.

Exploring All Permutations - O(n!) Time and O(n) Space

The given graph is a complete graph, meaning there is an edge between every pair of nodes.
A naive approach to solve this problem is to generate all permutations of the nodes, and
calculate the cost for each permutation, and select the minimum cost among them. Please
refer to Traveling Salesman Problem (TSP) Implementation.

Using Top-Down DP (Memoization) - O(n*n*2^n) Time and O(n*2^n) Space

If we observe closely, we can see that the recursive relation tsp() in the Traveling Salesman
Problem (TSP) exhibits the overlapping subproblems, where the same subproblems are
recalculated multiple times in different recursion paths. To optimize this, we can use
memoization to store the results of previously computed subproblems, thus avoiding
redundant calculations.
In this case, there are two parameters that change: mask, which represents the cities visited
so far, and curr, which represents the current city. Since both parameters have a finite range
(i.e., mask can have up to 2^n distinct values and curr can take n possible values), we can
use a 2D array of size n x (1<<n) to store the results for each combination of mask and curr
and initialize it as -1 to indicate that the values are not computed.
Longest Common Subsequence (LCS):
Given two strings, s1 and s2, the task is to find the length of the Longest Common
Subsequence. If there is no common subsequence, return 0. A subsequence is a string
generated from the original string by deleting 0 or more characters, without changing the
relative order of the remaining characters.
For example, subsequences of "ABC" are "", "A", "B", "C", "AB", "AC", "BC" and "ABC". In
general, a string of length n has 2n subsequences.

Examples:
Input: s1 = "ABC", s2 = "ACD"
Output: 2
Explanation: The longest subsequence which is present in both strings is "AC".
Input: s1 = "AGGTAB", s2 = "GXTXAYB"
Output: 4
Explanation: The longest common subsequence is "GTAB".
Input: s1 = "ABC", s2 = "CBA"
Output: 1
Explanation: There are three longest common subsequences of length 1, "A", "B" and "C".

[Naive Approach] Using Recursion - O(2 ^ min(m, n)) Time and O(min(m, n)) Space
The idea is to compare the last characters of s1 and s2. While comparing the strings s1 and
s2 two cases arise:
 1. Match : Make the recursion call for the remaining strings (strings of lengths m-1 and
n-1) and add 1 to result.
2. Do not Match : Make two recursive calls. First for lengths m-1 and n, and second for
m and n-1. Take the maximum of two results.
Base case : If any of the strings become empty, we return 0.

Dynamic Programming Approach

We solve using 2D DP.

State Definition
Let:
dp[i][j]=length of LCS of X[0..i−1] and Y[0..j−1]dp[i][j] = \text{length of LCS of } X[0..i-1] \text{
and } Y[0..j-1]dp[i][j]=length of LCS of X[0..i−1] and Y[0..j−1]

Recurrence Relation
1. If characters match:
dp[i][j]=1+dp[i−1][j−1]
2. If characters don’t match:
dp[i][j]=max⁡(dp[i−1][j],dp[i][j−1])

Base Case
• dp[0][j] = 0 (if X is empty)
• dp[i][0] = 0 (if Y is empty)

Time and Space Complexity

• Time Complexity: O(m × n)
• Space Complexity: O(m × n)
Backtracking Algorithm:
Backtracking algorithms are like problem-solving strategies that help explore different
options to find the best solution. They work by trying out different paths and if one doesn't
work, they backtrack and try another until they find the right one. It's like solving a puzzle by
testing different pieces until they fit together perfectly.

What is Backtracking Algorithm?

Backtracking is a problem-solving algorithmic technique that involves finding a solution
incrementally by trying different options and undoing them if they lead to a dead end.
It is commonly used in situations where you need to explore multiple possibilities to solve a
problem, like searching for a path in a maze or solving puzzles like Sudoku. When a dead
end is reached, the algorithm backtracks to the previous decision point and explores a
different path until a solution is found or all possibilities have been exhausted.

How Does a Backtracking Algorithm Work?

A backtracking algorithm works by recursively exploring all possible solutions to a problem.
It starts by choosing an initial solution, and then it explores all possible extensions of that
solution. If an extension leads to a solution, the algorithm returns that solution. If an
extension does not lead to a solution, the algorithm backtracks to the previous solution and
tries a different extension.
The following is a general outline of how a backtracking algorithm works:
1. Choose an initial solution.
2. Explore all possible extensions of the current solution.
3. If an extension leads to a solution, return that solution.
4. If an extension does not lead to a solution, backtrack to the previous solution and try
a different extension.
5. Repeat steps 2-4 until all possible solutions have been explored.

Example of Backtracking Algorithm

Example: Finding the shortest path through a maze
Input: A maze represented as a 2D array, where 0 represents an open space
and 1 represents a wall.
Algorithm:
1. Start at the starting point.
2. For each of the four possible directions (up, down, left, right), try moving in that
direction.
3. If moving in that direction leads to the ending point, return the path taken.
4. If moving in that direction does not lead to the ending point, backtrack to the
previous position and try a different direction.
5. Repeat steps 2-4 until the ending point is reached or all possible paths have been
explored.
When to Use a Backtracking Algorithm?
Backtracking algorithms are best used to solve problems that have the following
characteristics:
• There are multiple possible solutions to the problem.
• The problem can be broken down into smaller subproblems.
• The subproblems can be solved independently.

Applications of Backtracking Algorithm

Backtracking algorithms are used in a wide variety of applications, including:
• Solving puzzles (e.g., Sudoku, crossword puzzles)
• Finding the shortest path through a maze
• Scheduling problems
• Resource allocation problems
• Network optimization problems
• Combinatorial problems, such as generating permutations, combinations, or subsets.
8 queen problem:
Given an 8x8 chessboard, the task is to place 8 queens on the board such that no 2 queens
threaten each other. Return a matrix of size 8x8, where 1 represents queen and 0
represents an empty position.

Approach:
The idea is to use backtracking to place the queens one by one on the board. Starting from
the first row, we try placing queens in different columns and check if it's safe (not under
attack from previously placed queens). If a safe position is found, we move to the next row. If
at any point no safe position exists in a row, we backtrack to the previous row and try a
different column placement. This recursive approach systematically explores all possible
configurations until a valid solution is found.

Step by step approach:

1. Initialize an empty 8×8 chessboard with all positions set to 0.
2. Start with the first row (row 0) and try placing a queen in each column.
 3. For each placement, check if the position is safe (not attacked by any previously
placed queen). A position is unsafe if another queen is in the same column or on the
same diagonal.
4. If a safe position is found, place the queen (set position to 1) and recursively try to
place queens in subsequent rows. Otherwise, backtrack by removing the queen and
trying the next column.
5. If all rows are successfully filled (8 queens placed), a valid solution is found.

Knapsack Problem using Backtracking:

The Backtracking approach tries all possible combinations of items to find the maximum
value without exceeding the knapsack capacity.
Problem Statement
Given:
• n items with weights and values
• Knapsack with capacity W
Find: The maximum total value of items that can be included without exceeding the
capacity.
Backtracking Approach Idea
1. Explore all subsets of items (choose or skip each item).
2. Maintain running weight and value.
3. Prune the search when:
o Current weight exceeds W (capacity).
o Current path cannot lead to a better solution.
Time Complexity
• Worst case: O(2ⁿ) (all subsets)

Travelling Salesman Problem (TSP) using Backtracking:

The Travelling Salesman Problem (TSP) is a combinatorial optimization problem where a

salesman must:
1. Start from a city
2. Visit all cities exactly once
3. Return to the starting city
4. Minimize the total travel cost

Backtracking Approach
Backtracking tries all possible paths (permutations of cities) and prunes the search when
the cost already exceeds the best known path.
Algorithm Steps
1. Start at a source city (usually city 0).
2. Maintain:
o Visited[] array to track visited cities.
o Current path cost.
3. Recursively visit unvisited cities, updating cost.
4. Prune the path if current cost > best solution so far.
5. Update minimum cost when all cities are visited and you return to the start.
UNIT-5 (Branch And Bound):

Introduction to Branch and Bound:

LC Branch and Bound method is a powerful technique used to solve complex optimization
problems.
This method is particularly useful in solving NP-hard problems, which are notoriously
difficult to solve using traditional methods.
The Branch and Bound Algorithm is a method used in combinatorial optimization problems
to systematically search for the best solution. It works by dividing the problem into smaller
subproblems, or branches, and then eliminating certain branches based on bounds on the
optimal solution. This process continues until the best solution is found or all branches have
been explored. Branch and Bound is commonly used in problems like the traveling
salesman and job scheduling.

Branch and bound algorithms are used to find the optimal solution for combinatory, discrete,
and general mathematical optimization problems.

What is LC Branch and Bound?

In LC (Least Cost) Branch and Bound, we search using a priority on least cost nodes and
bound the search space to avoid unnecessary exploration.

Branch and Bound Technique

Concept
Branch and Bound is a systematic search technique used for optimization problems.
• Branching: Split the problem into smaller subproblems (states).
• Bounding: Calculate a bound (upper or lower cost) for each subproblem.
• Prune: If a subproblem cannot lead to a better solution, we discard it.

LC Branch and Bound (Least Cost)

In this technique, nodes are explored based on their costs, the cost of the node can be
defined using the problem and with the help of the given problem, we can define the cost
function. Once the cost function is defined, we can define the cost of the node.
Now, Consider a node whose cost has been determined. If this value is greater than U0, this
node or its children will not be able to give a solution. As a result, we can kill this node and
not explore its further branches. As a result, this method prevents us from exploring cases
that are not worth it, which makes it more efficient for us.
LC Search means we always expand the node with the least cost (priority queue) first.
• Used in Shortest Path, TSP, Job Scheduling.
• Ensures we explore most promising paths first.
Classification of Branch and Bound Problems:
The Branch and Bound method can be classified into three types based on the order in
which the state space tree is searched.
1. FIFO Branch and Bound
2. LIFO Branch and Bound
3. Least Cost-Branch and Bound
We will now discuss each of these methods in more detail. To denote the solutions in these
methods, we will use the variable solution method.
1. FIFO Branch and Bound
First-In-First-Out is an approach to the branch and bound problem that uses the queue
approach to create a state-space tree. In this case, the breadth-first search is performed,
that is, the elements at a certain level are all searched, and then the elements at the next
level are searched, starting with the first child of the first node at the previous level.
For a given set {A, B, C, D}, the state space tree will be constructed as follows :

State Space tree

for set {A, B, C, D}
The above diagram shows that we first consider element A, then element B, then element C
and finally we'll consider the last element which is D. We are performing BFS while exploring
the nodes.
So, once the first level is completed. We'll consider the first element, then we can consider
either B, C, or D. If we follow the route then it says that we are doing elements A and D so
we will not consider elements B and C. If we select the elements A and D only, then it says
that we are selecting elements A and D and we are not considering elements B and C.
 Selecting element A
Now, we will expand node 3, as we have considered element B and not considered element
A, so, we have two options to explore that is elements C and D. Let's create nodes 9 and 10
for elements C and D respectively.

Considered element B and not considered element A

Now, we will expand node 4 as we have only considered elements C and not considered
elements A and B, so, we have only one option to explore which is element D. Let's create
node 11 for D.
Considered elements C and not considered elements A and B

Till node 5, we have only considered elements D, and not selected elements A, B, and C. So,
We have no more elements to explore, Therefore on node 5, there won't be any expansion.
Now, we will expand node 6 as we have considered elements A and B, so, we have only two
option to explore that is element C and D. Let's create node 12 and 13 for C and D
respectively.

Expand node 6

Now, we will expand node 7 as we have considered elements A and C and not consider
element B, so, we have only one option to explore which is element D. Let's create node 14
for D.
Expand node 7

Till node 8, we have considered elements A and D, and not selected elements B and C, So,
We have no more elements to explore, Therefore on node 8, there won't be any expansion.
Now, we will expand node 9 as we have considered elements B and C and not considered
element A, so, we have only one option to explore which is element D. Let's create node 15
for D.

Expand node 9

2. LIFO Branch and Bound

The Last-In-First-Out approach for this problem uses stack in creating the state space tree.
When nodes are added to a state space tree, they are added to a stack. After all nodes of a
level have been added, we pop the topmost element from the stack and explore it.
For a given set {A, B, C, D}, the state space tree will be constructed as follows :
State space tree for element {A, B, C, D}

Now the expansion would be based on the node that appears on the top of the stack. Since
node 5 appears on the top of the stack, so we will expand node 5. We will pop out node 5
from the stack. Since node 5 is in the last element, i.e., D so there is no further scope for
expansion.
The next node that appears on the top of the stack is node 4. Pop-out node 4 and expand.
On expansion, element D will be considered and node 6 will be added to the stack shown
below:

Expand node 4

The next node is 6 which is to be expanded. Pop-out node 6 and expand. Since node 6 is in
the last element, i.e., D so there is no further scope for expansion.
The next node to be expanded is node 3. Since node 3 works on element B so node 3 will be
expanded to two nodes, i.e., 7 and 8 working on elements C and D respectively. Nodes 7 and
8 will be pushed into the stack.
The next node that appears on the top of the stack is node 8. Pop-out node 8 and expand.
Since node 8 works on element D so there is no further scope for the expansion.
Expand node 3
The next node that appears on the top of the stack is node 7. Pop-out node 7 and expand.
Since node 7 works on element C so node 7 will be further expanded to node 9 which works
on element D and node 9 will be pushed into the stack.
The next node is 6 which is to be expanded. Pop-out node 6 and expand. Since node 6 is in
the last element, i.e., D so there is no further scope for expansion.

Expand node 7
The next node that appears on the top of the stack is node 9. Since node 9 works on
element D, there is no further scope for expansion.
The next node that appears on the top of the stack is node 2. Since node 2 works on the
element A so it means that node 2 can be further expanded. It can be expanded up to three
nodes named 10, 11, 12 working on elements B, C, and D respectively. There new nodes will
be pushed into the stack shown as below:
Expand node 2
In the above method, we explored all the nodes using the stack that follows the LIFO
principle.
3. Least Cost-Branch and Bound
To explore the state space tree, this method uses the cost function. The previous two
methods also calculate the cost function at each node but the cost is not been used for
further exploration.
In this technique, nodes are explored based on their costs, the cost of the node can be
defined using the problem and with the help of the given problem, we can define the cost
function. Once the cost function is defined, we can define the cost of the node.
Now, Consider a node whose cost has been determined. If this value is greater than U0, this
node or its children will not be able to give a solution. As a result, we can kill this node and
not explore its further branches. As a result, this method prevents us from exploring cases
that are not worth it, which makes it more efficient for us.
Let's first consider node 1 having cost infinity shown below:
In the following diagram, node 1 is expanded into four nodes named 2, 3, 4, and 5.

Node 1 is expanded into four nodes named 2, 3, 4, and 5

Assume that cost of the nodes 2, 3, 4, and 5 are 12, 16, 10, and 315 respectively.
In this method, we will explore the node which is having the least cost. In the above figure,
we can observe that the node with a minimum cost is node 4. So, we will explore node 4
having a cost of 10.
During exploring node 4 which is element C, we can notice that there is only one possible
element that remains unexplored which is D (i.e, we already decided not to select elements
A, and B). So, it will get expanded to one single element D, let's say this node number is 6.

Exploring node 4 which is element C

Now, Node 6 has no element left to explore. So, there is no further scope for expansion.
Hence the element {C, D} is the optimal way to choose for the least cost.

Advantages of Branch and Bound Algorithm:

• We don't explore all the nodes in a branch and bound algorithm. Due to this, the
branch and the bound algorithm have a lower time complexity than other
algorithms.
• Whenever the problem is small and the branching can be completed in a reasonable
amount of time, the algorithm finds an optimal solution.
• By using the branch and bound algorithm, the optimal solution is reached in a
minimal amount of time. When exploring a tree, it does not repeat nodes.

Disadvantages of Branch and Bound Algorithm:

• It takes a long time to run the branch and bound algorithm.
• In the worst-case scenario, the number of nodes in the tree may be too large based
on the size of the problem.
0/1 Knapsack using Branch and Bound:
The backtracking based solution works better than brute force by ignoring infeasible
solutions. We can do better (than backtracking) if we know a bound on best possible solution
subtree rooted with every node. If the best in subtree is worse than current best, we can
simply ignore this node and its subtrees. So we compute bound (best solution) for every node
and compare the bound with current best solution before exploring the node.

How to find bound for every node for 0/1 Knapsack?

The idea is to use the fact that the Greedy approach provides the best solution for Fractional
Knapsack problem. To check if a particular node can give us a better solution or not, we
compute the optimal solution (through the node) using Greedy approach. If the solution
computed by Greedy approach itself is more than the best so far, then we can’t get a better
solution through the node.
Follow the steps to implement the above idea:
• Sort all items in decreasing order of ratio of value per unit weight so that an upper
bound can be computed using Greedy Approach.
• Initialize maximum profit, maxProfit = 0, create an empty queue, Q, and create a
dummy node of decision tree and enqueue it to Q. Profit and weight of dummy node
are 0.
• Do following while Q is not empty.
o Extract an item from Q. Let the extracted item be u.
o Compute profit of next level node. If the profit is more than maxProfit, then
update maxProfit.
o Compute bound of next level node. If bound is more than maxProfit, then
add next level node to Q.
o Consider the case when next level node is not considered as part of solution
and add a node to queue with level as next, but weight and profit without
considering next level nodes.
UNIT-4(Computational Complexity):
Polynomial vs Non-Polynomial Time Complexity:
In computer science, problems are divided into classes known as Complexity Classes. In
complexity theory, a Complexity Class is a set of problems with related complexity. With the
help of complexity theory, we try to cover the following.

• Problems that cannot be solved by computers.

• Problems that can be efficiently solved (solved in Polynomial time) by computers.
• Problems for which no efficient solution (only exponential time algorithms) exist.
The common resources required by a solution are are time and space, meaning how much
time the algorithm takes to solve a problem and the corresponding memory usage.
• The time complexity of an algorithm is used to describe the number of steps
required to solve a problem, but it can also be used to describe how long it takes to
verify the answer.
• The space complexity of an algorithm describes how much memory is required for
the algorithm to operate.
• An algorithm having time complexity of the form O(nk) for input n and constant k is
called polynomial time solution. These solutions scale well. On the other hand, time
complexity of the form O(kn) is exponential time.

Types of Complexity Classes

This article discusses the following complexity classes:
P Class
The P in the P class stands for Polynomial Time. It is the collection of decision
problems(problems with a "yes" or "no" answer) that can be solved by a deterministic
machine (our computers) in polynomial time.
Features:
• The solution to P problems is easy to find.
• P is often a class of computational problems that are solvable and tractable.
Tractable means that the problems can be solved in theory as well as in practice. But
the problems that can be solved in theory but not in practice are known as
intractable.

Most of the coding problems that we solve fall in this category like the below.
1. Calculating the greatest common divisor.
2. Finding a maximum matching.
3. Merge Sort

NP Class
The NP in NP class stands for Non-deterministic Polynomial Time. It is the collection of
decision problems that can be solved by a non-deterministic machine (note that our
computers are deterministic) in polynomial time.
Features:
• The solutions of the NP class might be hard to find since they are being solved by a
non-deterministic machine but the solutions are easy to verify.
• Problems of NP can be verified by a deterministic machine in polynomial time.

Example:
Let us consider an example to better understand the NP class. Suppose there is a company
having a total of 1000 employees having unique employee IDs. Assume that there
are 200 rooms available for them. A selection of 200 employees must be paired together,
but the CEO of the company has the data of some employees who can't work in the same
room due to personal reasons.
This is an example of an NP problem. Since it is easy to check if the given choice
of 200 employees proposed by a coworker is satisfactory or not i.e. no pair taken from the
coworker list appears on the list given by the CEO. But generating such a list from scratch
seems to be so hard as to be completely impractical.
It indicates that if someone can provide us with the solution to the problem, we can find the
correct and incorrect pair in polynomial time. Thus for the NP class problem, the answer is
possible, which can be calculated in polynomial time.
This class contains many problems that one would like to be able to solve effectively:
1. Boolean Satisfiability Problem (SAT).
2. Hamiltonian Path Problem.
3. Graph coloring.

NP-hard class
An NP-hard problem is at least as hard as the hardest problem in NP and it is a class of
problems such that every problem in NP reduces to NP-hard.
Features:
• All NP-hard problems are not in NP.
• It takes a long time to check them. This means if a solution for an NP-hard problem is
given then it takes a long time to check whether it is right or not.
• A problem A is in NP-hard if, for every problem L in NP, there exists a polynomial-
time reduction from L to A.
Some of the examples of problems in Np-hard are:
1. Halting problem.
2. Qualified Boolean formulas.
3. No Hamiltonian cycle.

NP-complete class
A problem is NP-complete if it is both NP and NP-hard. NP-complete problems are the hard
problems in NP.
Features:
• NP-complete problems are special as any problem in NP class can be transformed or
reduced into NP-complete problems in polynomial time.
 •If one could solve an NP-complete problem in polynomial time, then one could also
solve any NP problem in polynomial time.
Some example problems include:
1. Hamiltonian Cycle.
2. Satisfiability.
3. Vertex cover.

Complexity
Characteristic feature
Class

P Easily solvable in polynomial time.

NP Yes, answers can be checked in polynomial time.

Co-NP No, answers can be checked in polynomial time.

All NP-hard problems are not in NP and it takes a long time to check
NP-hard
them.

NP-complete A problem that is NP and NP-hard is NP-complete.