Course Information

Dr. Mohammed N. M. Ali

Design and Analysis of Algorithms School of Computer Science and Technology, Xiamen University
• ali.mohammed@xmu.edu.my
Lecture (8) - week (4) • Office: A1-363
September Intake 2023 • Consultation hours:
✓Tuesday 12 PM – 2 PM
✓Wednesday 11 AM – 1 PM
1
 Chapter 4 (i)

Divide and Conquer Algorithms

2
 Outlines
Divide and Conquer Algorithms.
Linear Search.
Binary Search.
→Definition.
→Pros and cons.
→Time complexity
→Examples.
Merge Sort algorithm.
→Definition.
→Pros and cons.
→Time complexity
→Examples.
3
 Divide and Conquer Algorithms
Divide and conquer is a strategy to solve a problem, there are many
strategies such as greedy algorithms. Dynamic algorithms etc. P

Strategy is the approach or design of solving a problem.

If you have a problem (𝑝) with size (𝑛), the problem will be divided
into small problems (sub-problems) and each sub-problem will have a
solution; these solutions will be merged and provide the last solution P1 P2 P3 … PK

for the big problem.

In this approach, we solve a problem recursively by applying 3 steps:
S1 S2 S3 … SK
1. DIVIDE-break the problem into several sub-problems of smaller
size.
2. CONQUER-solve the problem recursively.
3. COMBINE-combine these solutions to create a solution to the
original problem.
S
4
 Divide and Conquer Algorithms
The divide-and-conquer algorithm divides an instance of a problem
into two or smaller instances.
The smaller instance is the same problem as the original instance.
Assume that the smaller instance is easy to solve.
Combine solutions to the smaller instances to solve the original
instance.
If the smaller instance is still difficult, divide again until it is easy.
The divide-and-conquer is a top-down approach.
Recursion is usually adopted.

5
 Divide and Conquer Algorithm - Pseudocode
DAC (P)
{
if small(P)
then return S(P)
else
{
divide P into smaller instances P1, P2 .....Pk
Apply DAC to each subproblem DAC(P1), DAC(P2), ……
Return combine (DAC(P1)+ D AC(P2)+.......+D AC(Pk))
}
} 6
 Algorithms using Divide and conquer Technique

1.Binary Search
2.Merge Sort
3.Quick Sort
4.Finding maximum and Minimum.
5.Strassen’s Matrix Multiplication.
7
 Linear (Sequential) Search
Before starting with the binary search which is a divide-and-conquer search algorithm, we
will briefly describe the linear search.
Linear search is not a divide-and-conquer algorithm.
The searching algorithms are used to search or find one or more than one elements from a
dataset.
 There are 3 popular search algorithms:
→Linear search.
→Binary search.
→Jump search.
Linear search is a very simple search algorithm.
In this type of search, a sequential search is made over all items one by one.
Every item is checked and if a match is found then that item is returned, otherwise, the
search continues till the end of the data collection. 8
 Linear (Sequential) Search

Inputs of this search:

Search value. (Key)
Data Set. General Algorithm for linear
0 1 2 3 … i
search:
Array(A) Def Search(A, key):
for 𝑖 in range (len(A)):
We compare the key with the first element, if it is equal, we return the if A[𝑖]==key:
Key
index of this element. If not, we compare the key to the next element return 𝑖
until we find the key or consume all items in the array without finding
the key. return -1

→Best case of linear search is O(1).

→Worst case of liner search is O(n).
→The average case is O(n/2).
9
Divide and Conquer Algorithms
Binary Search

10
 Binary Search
Binary search method is very fast and
efficient.
This method requires that the list of
elements be in sorted order.
Binary search cannot be applied to an
unsorted list.
11
 Binary Search: Principle
The data item to be searched is compared with the approximate middle entry of
the list.
 If it matches with the middle entry, then the position will be displayed.
If the data item to be searched is lesser than the middle entry, then it is
compared with the middle entry of the first half of the list and the procedure is
repeated on the first half until the required item is found.
If the data item is greater than the middle entry, then it is compared with the
middle entry of the second half of the list and the procedure is repeated on the
second half until the required item is found.
This process continues until the desired number is found or the search interval
becomes empty.

12
 The description of the algorithm
 In Binary Search algorithm, K is the list of data items containing N data items.
 X is the data item, which is to be searched in K.
 If the data item to be searched is found, then the position where it is found will be printed.
If the data item to be searched is not found then the “Element Not Found” message will be printed.
 Initially lower is assumed as 0 to point to the first element in the list and upper is assumed as N-1 to
point to the last element in the list because the range of any array is 0 to N-1.
 The mid position of the list is calculated by finding the average between lower and upper and X is
compared with K[mid].
 If X is found equal to K[mid] then the value mid will gets printed, the control comes out of the loop and
the procedure comes to the end.
If X is found lesser than K[mid], then upper is assigned mid – 1, to search only in the first half of the list.
 If X is found greater than K[mid], then lower is assigned mid + 1, to search only in the second half of the
list.
This process is continued until the element searched is found or the collection becomes empty.
13
Binary Search Algorithm

14
Binary search algorithm - Pseudocode

15
Advantage and Disadvantage of Binary Search
Advantage:
1. Searches several times faster than the linear
search.
2. In each iteration, it reduces the number of
elements to be searched from 𝑛 to 𝑛/2.
Disadvantage:
1. Binary search can be applied only on a sorted list .

16
Example 1: Use the binary search algorithm to find x; where x=40
𝑋 = 40, the number to be searched.
𝑈 → 𝑈𝑝𝑝𝑒𝑟
𝐿 → 𝐿𝑜𝑤𝑒𝑟
𝑀 → 𝑀𝑖𝑑𝑑𝑙𝑒

Lower Upper 𝐿+𝑈

Mid= 2
0 9 4
0 3 1
2 3 2
3 3 3

17
 Example 2: Use the binary search algorithm to find key value; where k=42

A 3 6 8 12 14 17 25 29 31 36 42 47 53 55 62

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
Low → 𝑙

high → ℎ

Low =0 Mid Mid Mid

high → ℎ
High=14
𝑙+ℎ Low → 𝑙
Mid= 2 high → ℎ

Key (k) = 42 Low → 𝑙

l h 𝑙+ℎ Color
Mid= 2 Low → 𝑙 Mid high → ℎ

0 14 7 Blue
8 14 11 Red • Exercise:
From this, in 4
• Use the same array to search for:
8 10 9 Green comparisons we found
• Key=12.
the search value (K).
10 10 10 Purple • Key=30.
18
 Analysis of the recursive binary search algorithm
if 𝑛 = 0, i.e., the array is empty, then the algorithm does not perform any
element comparisons.
 If 𝑛 = 1, then exactly one comparison is performed.
 If 𝑛 > 1, then there are two possibilities: If 𝑥 = 𝐴[𝑚𝑖𝑑], then only one
comparison is performed; otherwise, the number of comparisons required
by the algorithm is one plus the number of comparisons done by the
recursive call on either the first or second half of the array.
If we let 𝑇(𝑛) denote the number of comparisons performed by Algorithm
binary-search in the worst case on an array of size 𝑛, then 𝑇(𝑛) can be
expressed by the recurrence:
𝟏 𝒏=𝟏
𝑻 𝒏 =ቐ 𝒏
𝑻 +𝟏 𝒏 >𝟏
𝟐
19
 The time complexity of BS - using a while loop
Int BinSearch (A, n, key)
{ 7 20
𝒍 = 𝟎; 𝒉 = 𝒏;
while (𝒍 <= 𝒉)
3 11 21
{
mid= (𝒍 + 𝒉)/𝟐;
if(key==A[mid] 22
1 5 9 13
return mid;
if (key<A[mid])
𝒉 = 𝒎𝒊𝒅 − 𝟏;
else 0 2 4 6 8 10 12 14 23
𝒍 = 𝒎𝒊𝒅 + 𝟏;
}
(𝑘)𝑙𝑒𝑣𝑒𝑙 = 2𝑘
return 0; 𝑛 = 2𝑘
} The best case is if the key was the
𝑙𝑜𝑔𝑛 = 𝑙𝑜𝑔2𝑘 first mid, thus T(n)=O(1).
𝑘 = 𝑙𝑜𝑔𝑛
(worst case) 𝑇 𝑛 = 𝑂 𝑙𝑜𝑔𝑛

20
Binary Search with divide-and-Conquer-Time Complexity

Algorithm RBinSearch(𝒍, 𝒉, 𝒌𝒆𝒚) T(n)

{
if(𝒍 == 𝒉)
{
Time complexity:
if(𝑨[𝒍] == 𝒌𝒆𝒚) 1
The problem is small – only 1 item
return 𝒍; 1 𝑛=1
else 𝑇 𝑛 = ቐ𝑇 𝑛
return 0; +1 𝑛>1
2
}
else
{ • Apply Master Theorem:
mid= (𝒍 + 𝒉)/𝟐; 1
• 𝑇 𝑛 = Θ(𝑙𝑜𝑔𝑛)
if (key==A[mid])
1
return mid;
If (key < A[mid]) 1
return RBinSearch(𝒍,mid-1,key);
The problem is big, and it will be divided to smaller problems
Else
Return RBinSearch(mid+1,𝒉,key); These two divided the problem into parts
} 𝑛
either left or right; thus, the T(n)=
2
}

21
Analysis of the recursive binary search algorithm

22
Rewrite the following binary search algorithm and check the
results (Use C or C ++)

23
Merge Sort

24
 Merge Sort Algorithm
Merge Sort follows the rule of Divide and Conquer to sort a given set of numbers/elements,
recursively, hence consuming less time.
The name “divide and conquer” has been given to a powerful algorithm design technique that is
used to solve a variety of problems.
In its simplest form, a divide-and-conquer algorithm divides the problem instance into a number
of sub instances (in most cases 2), recursively solves each sub instance separately, and then
combines the solutions to the sub instances to obtain the solution to the original problem
instance.
The concept of Divide and Conquer involves three steps:
→Divide the problem into multiple small problems.
→Conquer the subproblems by solving them. The idea is to break down the problem into
atomic subproblems, where they are solved.
→Combine the solutions of the subproblems to find the solution to the actual problem.
Principle: The given list is divided into two roughly equal parts called the left and the right
subfiles. These subfiles are sorted using the algorithm recursively and then the two subfiles are
merged to obtain the sorted file. 25
 Merge Sort Algorithm-Principles
Given a sequence of N elements K[0], K[1] ….K[N-1], the general idea is to imagine
them split into various sub-tables of size equal to 1.
 Each set will have individually sorted items with it, and then the resulting sorted
sequences are merged to produce a single sorted sequence of N elements.
A sorting algorithm is an algorithm that puts items of a list in a certain order.
Efficient sorting is important for optimizing the efficiency of other algorithms(such
as search and merge algorithms)that require input data to be in sorted lists.
The output of any sorting algorithm must satisfy two conditions:
1. The output is in nondecreasing order(each item is no smaller than the previous
item).
2. The output is a permutation(a reordering yet retaining all the original items)of
the input.
26
 Merge Sort Algorithm-Principles
 Merge sort is a top-down approach.
For example, In the beginning, we have the input array:

We divide this array into two 4-element arrays as

 Next, we sort these two arrays individually, and then simply merge them to
obtain the desired sorted array. Call this algorithm sort.
As to the sorting method used for each half, we are free to make use of any
sorting algorithm to sort the two subarrays.

27
 Merge Sort Algorithm-Principles
 MergeSort algorithm is a well-known and efficient algorithm.
A precise description of this algorithm is given in Algorithm MergeSort.

28
 How the algorithm works
Consider the figure below illustrates the behavior of Algorithm mergesort on the input array

29
 How the algorithm works
As shown in the figure, the main call mergesort(A, 1, 8) induces a
series of recursive calls represented by an implicit binary tree.
Each node of the tree consists of two arrays. The top array is the
input to the call represented by that node, whereas the bottom array
is its output.
Each edge of the tree is replaced with two anti-directional edges
indicating the flow of control.
 The main call causes the call mergesort(A, 1, 4) to take effect, which,
in turn, produces the call mergesort(A, 1, 2), and so on.
Edge labels indicate the order in which these recursive calls take
place. 30
 How the algorithm works
This chain of calls corresponds to a preorder traversal of the tree:
Visit the root, the left subtree, and then the right subtree.
The computation, however, corresponds to a post-order traversal of
the tree: Visit the left subtree, the right subtree, and then the root.
To implement this traversal, a stack is used to hold the local data of
each active call.
Each pair of numbers are merged to produce two-element sorted
sequences.
These sorted 2-element sequences are then merged to obtain 4-
element sorted sequences, and so on.
31
 Merge Sort-Algorithm Steps
If you have an array, then:
→Left start index, right last index.
(𝒍𝒆𝒇𝒕+𝒓𝒊𝒈𝒉𝒕)
→Find the middle of the array: mid = .
𝟐
→Break the array into two subarrays:
(left to mid) and (mid + 1 to right).
→Continue the process of breaking into halves until
reaching single element.
→Merge the subarrays.
32
 Merge Sort-Algorithm-Pseudocode
 MegreSort(arr[], left, right)
 If right > left
1. Find the middle point to divide the array into two halves:
(𝒍𝒆𝒇𝒕+𝒓𝒊𝒈𝒉𝒕)
→ Middle 𝑚 = .
𝟐
2. Call mergeSort for the first half:
→ Call mergeSort(arr, left, m)
3. Call mergeSort for the second half:
→ Call mergeSort(arr, m+1, right)
4. Merge the two halves sorted in step 2 and 3:
→ Call merge(arr, left, m, right).

33
 Merging Two Sorted Lists

Suppose we have an array A[1..m] and three indices p, q, and

r, with 1 ≤ p ≤ q < r ≤ m, such that both the subarrays A[p..q]
and A[q + 1..r] are individually sorted in nondecreasing order.
We want to rearrange the elements in A so that the elements
in the subarray A[p..r] are sorted in nondecreasing order.
This process is referred to as merging A[p..q] with A[q + 1..r].
An algorithm to merge these two subarrays works as follows:

34
 Merging Two Sorted Lists
We maintain two pointers s and t that initially point to A[p] and A[q + 1],
respectively.
We prepare an empty array B[p..r] which will be used as a temporary storage.
Each time, we compare the elements A[s] and A[t] and append the smaller of the
two to the auxiliary array B; if they are equal, we will choose to append A[s].
Next, we update the pointers: If A[s] ≤ A[t], then we increment s, otherwise we
increment t.
This process ends when s = q + 1 or t = r + 1. In the first case, we append the
remaining elements A[t..r] to B, and in the second case, we append A[s..q] to B.
Finally, the array B[p..r] is copied back to A[p..r].
This procedure is given in Algorithm merge.
35
Merging Two Sorted Lists

36
 Merging process-Example

A B
4 6 9 12 15 3 5 7 13 17 19

i i i i i i j j j j j j

C
3 4 5 6 7 9 12 13 15 17 19

k k k k k k k k k k k

The time complexity of the Merging process is O(m+n).

Where m is the size of the 1st array (A) and n is the size of the second array (B).
37
 Merge Sort Algorithm
Algorithm MergeSort(A, 𝑙𝑜𝑤, ℎ𝑖𝑔ℎ)
{
if(𝑙𝑜𝑤 < ℎ𝑖𝑔ℎ) Then
mid = (𝑙𝑜𝑤 + ℎigh) / 2;
MergeSort (A, 𝑙𝑜𝑤, 𝑚𝑖𝑑);
MergeSort (A, 𝑚𝑖𝑑 + 1, ℎ𝑖𝑔ℎ);
Merge(𝐴, 𝑙𝑜𝑤, 𝑚𝑖𝑑, ℎ𝑖𝑔ℎ);
}
}

38
 Merge Sort Steps- Example
Arrange array = [15, 7, 4, 11, 2, 20, 8, 1, 5] by using merge sort algorithm.
0 1 2 3 4 5 6 7 8

15 7 4 11 2 20 8 1 5 N=9, mid=4

𝑙 ℎ
Divide
15 7 4 11 2
20 8 1 5
𝑙 ℎ
Divide
Divide
15 7 4 11 2
Divide Divide
20 8 1 5
Divide Divide
15 7 4 11 2
Divide 20 8 1 5
Merge Merge Merge
15 7 2 11 8 20 1 5
Merge
Merge
7 15 1 5 8 20
Merge 4 7 15
Merge

2 4 7 11 15
Merge

1 2 4 5 7 8 11 15 20 39
Complexity Analysis of MergeSort Algorithm

40
 Merging Two Sorted Lists – Time Complexity
 Let 𝑛 denote the size of the array A[p..r] in the input to Algorithm
merge, i.e., 𝑛 = r - p + 1.
We want to find the number of comparisons that are needed to
rearrange the entries of A[p..r].
Number of comparisons performed by an algorithm mean element
comparisons. Thus, all other comparisons, e.g., those needed for the
implementation of the while loop, will be excluded.
Let the two subarrays be of sizes n1 and n2, where n1 + n2 = n.
The least number of comparisons happens if each entry in the
smaller subarray is less than all entries in the larger subarray.
41
 Merging Two Sorted Lists – Time Complexity
 For example, to merge the two subarrays

→The algorithm performs only three comparisons.

On the other hand, the number of comparisons may be as high as n -
1.
For example, to merge the two subarrays

→Seven comparisons are needed.

It follows that the number of comparisons done by Algorithm merge
is at least n1 and at most n - 1.
42
 Merging Two Sorted Lists – Time Complexity

 How about the number of element assignments (assignments involving input data)? (while loop,
the if statements, etc. are not involved) to find out how the algorithm works and then compute
the number of element assignments.
It is easy to see that each entry of array B is assigned exactly once.
Similarly, each entry of array A is assigned exactly once, when copying B back into A.
As a result, we have the following observation

43
 MergeSort Algorithm– Time Complexity
As in the binary search algorithm, the basic operation here is
element comparison.
That is, the running time is proportional to the number of element
comparisons performed by the algorithm.
Now, we wish to compute the number of element comparisons
𝐶(𝑛) required by Algorithm mergesort to sort an array of 𝑛 elements.
 For simplicity, we will assume that 𝑛 is a power of 2, i.e., 𝑛 = 2𝑘 for
some integer 𝑘 ≥ 0. If 𝑛 = 1, then the algorithm does not perform
any element comparisons.
If n > 1, then steps 2 through 5 are executed. (Steps of MERGESORT Definition
[Slide 28])
44
 Merging Two Sorted Lists – Time Complexity
 The number of comparisons required to execute steps 3 and 4 is 𝐶(𝑛/2) each.
By Observation 1.1 (Slide 43), the number of comparisons needed to merge the
two subarrays is between 𝑛/2 and 𝑛 − 1.
Thus, the minimum number of comparisons done by the algorithm is given by
the recurrence

45
Merging Two Sorted Lists – Time Complexity

46
 Merging Two Sorted Lists – Time Complexity
 The maximum number of comparisons done by the algorithm is
given by the recurrence

By using the iteration Method we can solve this recurrence.

𝑛
𝐶 𝑛 = 2𝐶 +𝑛−1
2

47
 Merging Two Sorted Lists – Time Complexity
 Solution:
𝑛
𝐶 𝑛 = 2𝐶 +𝑛−1
2
𝑛 𝑛
𝐶 𝑛 = 2 2𝐶 + −1 + 𝑛 − 1 𝑛 𝑛 𝑛
22 2 𝐶 = 2𝐶 + 2-1
2 22
𝑛
𝐶 𝑛 = 22 𝐶 +n−2+𝑛−1
22
𝑛
𝐶 𝑛 = 22 𝐶 + 2n − 2 − 1
22
In Level K which is the latest level:
𝑛
= 2𝑘 𝐶 𝑘 + kn − 2𝑘−1 − 2𝑘−2 − ⋯ − 2 − 1
2 𝑘−1

= 2𝑘 𝐶 1 + kn − ෍ 2 𝑗
𝑗=0

= 2𝑘 × 0 + kn − 2𝑘 − 1 𝑛 = 2𝑘
= kn − 2𝑘 + 1 𝑙𝑜𝑔𝑛 = 𝑙𝑜𝑔2𝑘
= nlogn − 𝑛 + 1 𝑙𝑜𝑔𝑛 = 𝑘 48
 Merging Two Sorted Lists – Time Complexity
As a result we can have the following observation:
→Observation: The total number of element comparisons performed by
Algorithm mergesort to sort an array of size 𝑛, where 𝑛 is a power of 2, is
between (𝑛 log 𝑛)/2 and 𝑛 log 𝑛 − 𝑛 + 1.
If 𝑛 is any arbitrary positive integer (not necessarily a power of 2), the
recurrence relation for 𝐶(𝑛), the number of element comparisons performed
by Algorithm mergesort, becomes:

for some nonnegative constant 𝑏. Using the Master Method the solution to
this recurrence is C(n) = Θ(n logn).
49
 Merging Two Sorted Lists – Time Complexity

 Since the operation of element comparison is a basic

operation in the algorithm, thus, the running time of
Algorithm mergesort is:
𝑇(𝑛) = Θ(𝑛 log 𝑛).
Theorem, the running time of any algorithm for
sorting by comparisons is Ω(n log n). It follows that
Algorithm mergesort is optimal.

50
 The time complexity of the Merge Sort Algorithm
0 1 2 3 4 5 6 7

𝑁=8 𝑛
𝐿𝑜𝑤 (𝑙) = 0
A 9 3 7 5 8 2 6 4 20
𝐻𝑖𝑔ℎ(ℎ) = 7
0+7
𝑀𝑖𝑑 = =2 Splitting 𝑛
Level k = 𝑘 = 1
2 𝑛 2
9 3 7 5 8 2 6 4 21 2𝑘 = 𝑛
𝑙𝑜𝑔2𝑘 = 𝑙𝑜𝑔𝑛
𝑘 = 𝑙𝑜𝑔𝑛
𝑛 Thus, 𝑇 𝑛 = Θ(𝑙𝑜𝑔𝑛)
9 3 7 5 8 2 6 4 22
𝑛
23

9 3 7 5 8 2 6 4 n

3 9 5 7 2 8 4 6 n
𝑇 𝑛 = Θ(𝑛)

Merging

3 5 7 9 2 4 6 8 n
From both operations: T(n)
for merge sort is:
𝑇 𝑛 = Θ(𝑛𝑙𝑜𝑔𝑛)
2 3 4 5 6 7 8 9
51
The time complexity of the Merge Sort Algorithm
Algorithm MergeSort(𝑙, ℎ) 𝑇(𝑛)
{ 1 𝑛=1
if(𝑙 < ℎ) 𝑇(𝑛) = ቐ2𝑇 𝑛 + 𝑛 𝑛>1
2
{ 1
mid = (𝑙 + ℎ) / 2; Applying Master theorem on this recurrence relation:
𝑛 𝑎 = 2, 𝑏 = 2, 𝑓 𝑛 = 𝑛
MergeSort (𝑙, 𝑚𝑖𝑑); 𝑇( ) (𝑎) (2)
2 𝑛 𝑙𝑜𝑔𝑏
= 𝑛𝑙𝑜𝑔2 =𝑛
MergeSort (𝑚𝑖𝑑 + 1, ℎ); 𝑛 (𝑎)
𝑙𝑜𝑔𝑏
𝑇( ) 𝑓 𝑛 =𝑛
Merge(𝑙, 𝑚𝑖𝑑, ℎ); 2 𝑇ℎ𝑢𝑠; T(n) = Θ 𝑛 log 𝑛
} 𝑛
}
𝑛
𝑇 𝑛 = 2𝑇 +n
2
52
 Space complexity of Merge Sort

An in-place sort is a sorting algorithm that does not use any
extra space beyond that needed to store their input.
Merge sort is not an in-place sort because it uses the arrays
𝑈 and 𝑉 besides the input array 𝑆.
New arrays 𝑈 and 𝑉 will be created each time merge sort is
called.
n n
The total number of extra array items is n + + + ⋯=
2 4
2n.
53
 Space complexity of Merge Sort
It is not hard to see that the space needed for the recursive calls is
Θ(𝑛).
It follows that the space complexity of the algorithm is Θ 𝑛 .
 The following theorem summarizes the main results of this section.

54
 Pros and Cons of Merge Sort
Pros:
→Suitable for large-size lists.
→Suitable for linked lists. (Can sort and merge 2 linked lists to create 1 linked list)
→Extended sorting.(Partitioning large data and sort it if the space not enough in
the memory)
→Stable. (Works in case of there is data duplicate in two files, the algorithm will
preserve their order)
Cons
→It needs extra space. (not in place sort).
→No small problem except when we have only one element.
→Recursive.
55
Apply the Merge Sort algorithm using your IDE and check
the results (Use C or C++)

56
 References
• Required References
1. Sandeep Sen (Author), Amit Kumar (Author) , Design and Analysis of Algorithms: A Contemporary
Perspective, Cambridge University Press (May 23, 2019).

• Further Readings
1. Divyansh Pratap Singh Parmar, Data structure and Algorithm: COMPUTER SCIENCE, Independently
published, 2019.
2. Michael Soltys-Kulinicz , Introduction To The Analysis Of Algorithms, World Scientific Publishing Co Pte
Ltd , 3rd edition (March 30, 2018).
3. Rosen, K. H. Discrete Mathematics and Its Applications.
4. Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2022). Introduction to algorithms. MIT press.

57
 Thank you
Any questions?
58