ANALYSIS & DESIGN OF ALGORITHMS

(23PCSCC11)
UNIT – 1
Introduction:
 Algorithm Definition and Specification
 Space complexity
 Time Complexity
 Asymptotic Notations
Elementary Data Structure:
 Stacks and Queues
 Binary Tree
 Binary Search Tree
 Heap
 Heapsort
 Graph
ANALYSIS & DESIGN OF ALGORITHMS (23PCSCC11) UNIT – 1
I M. Sc., Computer Science Semester: 1
ALGORITHM
An Algorithm is a sequence of unambiguous instructions for solving a problem i.e.,
for obtaining a required output for any legitimate input in a finite amount of time.
An Algorithm is a step by step process to perform some actions.

Points to be noted for writing algorithm:-

• The nonambiguity requirement for each step of an algorithm cannot be
compromised
• The range of inputs for which an algorithm works has to be specified carefully
• The same algorithm can be represented in several different ways
• There may exist several algorithms for solving the same problem
• Algorithm for the same problem can be based on very different ideas and can solve
• The problem with dramatically different speeds.
Terms / Terminologies used in Algorithm
(i) Variables
(ii) Data types
(iii) Statements
Variables: A symbolic name associated with a value and whose associated value may
be changed in the program
Data Types: A data type is an attribute of data which tells the compiler or interpreter
how the programmer intends to use the data
Statements: A statement is a command given to the computer that instructs the
computer to perform some action.

DR. R. K. SHANMUGAM COLLEGE OF ARTS AND SCIENCE, KALLAKURICHI 1

ANALYSIS & DESIGN OF ALGORITHMS (23PCSCC11) UNIT – 1
I M. Sc., Computer Science Semester: 1

Algorithm Specification
Algorithm Specification
Name of the Algorithm Every algorithm is given an identifying name written in
capital letters
Introductory Comment The algorithm name is followed by the brief description of
the tasks. Comment begins with // and continuous until
end of lines
Steps Each algorithm is made of a sequence of numbered steps
and each steps has an ordered sequence of statements
Data Types Data type are assumed simple such as integer, char, real,
Boolean and other data structures such as an array, pointer,
structure are used
Expression The basic expressions (Arithmetic Expression, Relational
Expression and Logical Expression) are used in algorithm

DR. R. K. SHANMUGAM COLLEGE OF ARTS AND SCIENCE, KALLAKURICHI 2

ANALYSIS & DESIGN OF ALGORITHMS (23PCSCC11) UNIT – 1
I M. Sc., Computer Science Semester: 1
Assignment Statement The assignment statement is indicated by various symbols,
such as =, , :=
Conditional Statement The statements such as if, if.. else, case are used in
algorithm to perform conditional tasks
Looping Statement The statements such as for, while are used to repeat certain
number of conditions for more than one time
Input & Output For Input, we use “Read” or “Get the values” and for
Output we use “Write” or “Print” in the algorithms
End Statement Terminate the algorithm properly by using the statements
such as stop or end

DR. R. K. SHANMUGAM COLLEGE OF ARTS AND SCIENCE, KALLAKURICHI 3

ANALYSIS & DESIGN OF ALGORITHMS (23PCSCC11) UNIT – 1
I M. Sc., Computer Science Semester: 1

Characteristics of Algorithm
 Correctness: We have to prove that the algorithm yields a required result for
every legitimate input in a finite amount of time
 Efficiency: We have to take efficiency of our algorithm by its time running and
space
 (memory) occupying
 Simplicity: Algorithm must be simple to understand
 Generality: Procedure apply to all problem and not for a special subset
Methods of specifying an algorithm / Notations of an algorithm
Algorithm can be expressed in the following ways.,
 Natural Languages
 Pseudocode
 Flowchart
 Programming Languages

DR. R. K. SHANMUGAM COLLEGE OF ARTS AND SCIENCE, KALLAKURICHI 4

ANALYSIS & DESIGN OF ALGORITHMS (23PCSCC11) UNIT – 1
I M. Sc., Computer Science Semester: 1
Natural Languages: Using a natural language has an obvious appeal; however the
inherent ambiguity of any natural language makes a succinct and clear description of
algorithms surprisingly difficult.
Pseudocode: Pseudocode is a mixture of a natural language and programming
language. Pseudocode is usually more precise than natural language, and its usage
often yields more succinct algorithm descriptions.
Eg:
 denotes assignment operation
// denotes comments
Flowchart: Flowchart is a method of expressing an algorithm by a collection of
connected geometric shapes containing descriptions of the algorithm’s steps.
Programming Languages: Now a day, algorithms are written in the programming
languages itself directly and fed into the computer directly without any interpreter.
Languages like C#, PYTHON and RUBY are well suited for writing algorithms
ANALYSIS OF ALGORITHMS
The term “Analysis of Algorithms” was coined by Donald Knuth. The
analysis of algorithms is the determination of the computational complexity of
algorithms, that is the amount of time, storage and / or other resources necessary to
execute them.
An algorithm is said to be efficient when the function values are small, or
grow slowly compared to a growth in the size of the input. Different inputs of the
same length may cause the algorithm to have different behavior, so best case, worst
case and average case comes into the picture.
Space Complexity: Amount of memory space requested by an algorithm during the
course of execution is called as “Space Complexity”. [How much memory it uses?].
Space Complexity is also called as Space Efficiency. In general, the Space can be
divided into three types.,
Instruction Space: The space (memory) available to store the statements /
instructions

DR. R. K. SHANMUGAM COLLEGE OF ARTS AND SCIENCE, KALLAKURICHI 5

ANALYSIS & DESIGN OF ALGORITHMS (23PCSCC11) UNIT – 1
I M. Sc., Computer Science Semester: 1
Data Space: The space (memory) available to store the data / variables
Environment Space: The space (memory) to resume the suspended function
Constant Space Complexity: Algorithm uses only fixed amount of space for all input
values
Eg: Array, Fixed Size Stack, Fixed Size Queue
Linear Space Complexity:
Eg: Lists, Queue
Time Complexity: The time consumed by algorithm to execute a program is called as
“Time Complexity”. [How fast the algorithm runs?] Time Complexity is also called
as Time Efficiency.

DR. R. K. SHANMUGAM COLLEGE OF ARTS AND SCIENCE, KALLAKURICHI 6

ANALYSIS & DESIGN OF ALGORITHMS (23PCSCC11) UNIT – 1
I M. Sc., Computer Science Semester: 1

ASYMPTOTIC NOTATIONS
 Asymptotic notations are used to make meaningful statements about the
efficiency of algorithms
 Asymptotic notations help us to make approximate but meaningful
assumptions about the time and space complexity
 The commonly used Asymptotic notations are:
1) Big – O (or) Big – Oh
2) Big – Omega
3) Big – Theta

DR. R. K. SHANMUGAM COLLEGE OF ARTS AND SCIENCE, KALLAKURICHI 7

ANALYSIS & DESIGN OF ALGORITHMS (23PCSCC11) UNIT – 1
I M. Sc., Computer Science Semester: 1
Big – Theta (θ):
The theta notation bounds a functions from above and
below, so it defines exact asymptotic behavior. A
simple way to get Theta notation of an expression is to
drop low order terms and ignore leading constants.

Big – O (or) Big – Oh (O):

The Big O notation defines an upper bound of an
algorithm, it bounds a function only from above. The
Big O notation is useful when we only have upper
bound on time complexity of an algorithm. Many
times we easily find an upper bound by simply
looking at the algorithm.

Big – Omega (Ω):

Just as Big O notation provides an asymptotic
upper bound on a function, Ω notation provides
an asymptotic lower bound. Ω Notation can be
useful when we have lower bound on time
complexity of an algorithm.

DR. R. K. SHANMUGAM COLLEGE OF ARTS AND SCIENCE, KALLAKURICHI 8

ANALYSIS & DESIGN OF ALGORITHMS (23PCSCC11) UNIT – 1
I M. Sc., Computer Science Semester: 1

Examples:

DR. R. K. SHANMUGAM COLLEGE OF ARTS AND SCIENCE, KALLAKURICHI 9

ANALYSIS & DESIGN OF ALGORITHMS (23PCSCC11) UNIT – 1
I M. Sc., Computer Science Semester: 1

ELEMENTARY DATA STRUCTURE

The data structure name indicates itself that organizing the data in memory.
The data structure is not any programming language like C, C++, java, etc. It is a set
of algorithms that we can use in any programming language to structure the data in
the memory.
Types of Data Structures:

DR. R. K. SHANMUGAM COLLEGE OF ARTS AND SCIENCE, KALLAKURICHI 10

ANALYSIS & DESIGN OF ALGORITHMS (23PCSCC11) UNIT – 1
I M. Sc., Computer Science Semester: 1

Primitive Data structure: The primitive data structures are primitive data types. The
int, char, float, double, and pointer are the primitive data structures that can hold a
single value.
Non-Primitive Data structure: The non-primitive data structure is divided into two
types:
Linear Data Structure: The arrangement of data in a sequential manner is known as
a linear data structure. The data structures used for this purpose are Arrays, Linked
list, Stacks, and Queues. In these data structures, one element is connected to only
one another element in a linear form.
Non - Linear Data Structure: The arrangement of data in a random manner is
known as a non - linear data structure. The data structures used for this purpose are
Trees and Graphs.

Major Operations
The major or the common operations that can be performed on the data
structures are:
Searching: We can search for any element in a data structure.
Sorting: We can sort the elements of a data structure either in an ascending or
descending order.
Insertion: We can also insert the new element in a data structure.
Updation: We can also update the element, i.e., we can replace the element with
another element.
Deletion: We can also perform the delete operation to remove the element from the
data structure.

DR. R. K. SHANMUGAM COLLEGE OF ARTS AND SCIENCE, KALLAKURICHI 11

ANALYSIS & DESIGN OF ALGORITHMS (23PCSCC11) UNIT – 1
I M. Sc., Computer Science Semester: 1
Advantages of Data Structure
Efficiency: If the choice of a data structure for implementing a particular ADT
(Abstract Data Type) is proper, it makes the program very efficient in terms of time
and space.
Reusability: The data structure provides reusability means that multiple client
programs can use the data structure.
Abstraction: The data structure specified by an ADT also provides the level of
abstraction. The client cannot see the internal working of the data structure, so it
does not have to worry about the implementation part. The client can only see the
interface.
STACK
Stack is a linear data structure that follows the LIFO (Last In-First Out) rule,
where the data that was added most recently will be removed first. It contains only
one pointer top pointer pointing to the topmost element of the stack. Whenever an
element is added in the stack, it is added on the top of the stack, and the element can
be deleted only from the stack. In other words, a stack can be defined as a container
in which insertion and deletion can be done from the one end known as the top of
the stack (ToS).
Operations used in Stack:
push(): A push operation is used to add data elements to a stack
pop(): A pop operation is used to remove data elements from the list
Other Operations:
isEmpty(): It determines whether the stack is empty or not.
isFull(): It determines whether the stack is full or not.'
peek(): It returns the element at the given position.
count(): It returns the total number of elements available in a stack.
change(): It changes the element at the given position.
display(): It prints all the elements available in the stack.

DR. R. K. SHANMUGAM COLLEGE OF ARTS AND SCIENCE, KALLAKURICHI 12

ANALYSIS & DESIGN OF ALGORITHMS (23PCSCC11) UNIT – 1
I M. Sc., Computer Science Semester: 1
Example:

DR. R. K. SHANMUGAM COLLEGE OF ARTS AND SCIENCE, KALLAKURICHI 13

ANALYSIS & DESIGN OF ALGORITHMS (23PCSCC11) UNIT – 1
I M. Sc., Computer Science Semester: 1
Applications of Stack:
• Expression conversion
• Backtracking
• DFS (Depth First Search)
• Memory Management
• Balancing of symbols
• String reversal
• Recursion
QUEUE
Queue is the data structure that is similar to the queue in the real world. A
queue is a data structure in which whatever comes first will go out first, and it
follows the FIFO (First-In-First-Out) policy. Queue can also be defined as the list or
collection in which the insertion is done from one end known as the rear end or the
tail of the queue, whereas the deletion is done from another end known as the front
end or the head of the queue.

DR. R. K. SHANMUGAM COLLEGE OF ARTS AND SCIENCE, KALLAKURICHI 14

ANALYSIS & DESIGN OF ALGORITHMS (23PCSCC11) UNIT – 1
I M. Sc., Computer Science Semester: 1
Example:

Operations used in Queue:

Common Operations:
enqueue(): add (store) an item to the queue.
dequeue():remove (access) an item from the queue.
Other Operations:
peek(): Gets the element at the front of the queue without removing it.
isfull(): Checks if the queue is full.
isempty(): Checks if the queue is empty.

DR. R. K. SHANMUGAM COLLEGE OF ARTS AND SCIENCE, KALLAKURICHI 15

ANALYSIS & DESIGN OF ALGORITHMS (23PCSCC11) UNIT – 1
I M. Sc., Computer Science Semester: 1
Applications of Queue:
• CPU Scheduling
• Disk Scheduling
• BFS (Breadth First Search)
• I/O Buffers
• Routers
• Semaphores
Types of Queues:
There are four different types of queues. They are.,
1. Simple Queue or Linear Queue
2. Circular Queue
3. Priority Queue
4. Double Ended Queue (or Deque)
Simple Queue or Linear Queue: In Linear Queue, an insertion takes place from one
end while the deletion occurs from another end. The end at which the insertion takes
place is known as the rear end, and the end at which the deletion takes place is
known as front end. It strictly follows the FIFO rule.

Circular Queue: In Circular Queue, all the nodes are represented as circular. It is
similar to the linear Queue except that the last element of the queue is connected to
the first element. It is also known as Ring Buffer, as all the ends are connected to
another end.

DR. R. K. SHANMUGAM COLLEGE OF ARTS AND SCIENCE, KALLAKURICHI 16

ANALYSIS & DESIGN OF ALGORITHMS (23PCSCC11) UNIT – 1
I M. Sc., Computer Science Semester: 1
Priority Queue: It is a special type of queue in which the elements are arranged based
on the priority. It is a special type of queue data structure in which every element has
a priority associated with it. Suppose some elements occur with the same priority,
they will be arranged according to the FIFO principle.

Deque (Double Ended Queue): In Deque or Double Ended Queue, insertion and
deletion can be done from both ends of the queue either from the front or rear. It
means that we can insert and delete elements from both front and rear ends of the
queue. Deque can be used as a palindrome checker means that if we read the string
from both ends, then the string would be the same.

DR. R. K. SHANMUGAM COLLEGE OF ARTS AND SCIENCE, KALLAKURICHI 17

ANALYSIS & DESIGN OF ALGORITHMS (23PCSCC11) UNIT – 1
I M. Sc., Computer Science Semester: 1
TREES
• A tree is one of the data structures that represent hierarchical data.
• A tree data structure is defined as a collection of objects or entities known as
nodes that are linked together to represent or simulate hierarchy.
• A tree data structure is a non-linear data structure because it does not store in
a sequential manner. It is a hierarchical structure as elements in a Tree are
arranged in multiple levels.
• In the Tree data structure, the topmost node is known as a root node. Each
node contains some data, and data can be of any type. In the above tree
structure, the node contains the name of the employee, so the type of data
would be a string.
• Each node contains some data and the link or reference of other nodes that
can be called children.
Basic terms used in Tree data structure:-
In the adjacent diagram, each node is labeled with some number.
Each arrow shown in the figure is known as a link between the two nodes.
Root: The root node is the topmost node in the tree hierarchy. In other words, the
root node is the one that doesn't have any parent. In the above structure, node
numbered 1 is the root node of the tree. If a node is directly linked to some other
node, it would be called a parent-child relationship.
Child node: If the node is a descendant of any node, then the node is known as a
child node.
Parent: If the node contains any sub-node, then that node is said to be the parent of
that sub-node.
Sibling: The nodes that have the same parent are known as siblings.
Leaf Node: The node of the tree, which doesn't have any child node, is called a leaf
node. A leaf node is the bottom-most node of the tree. There can be any number of
leaf nodes present in a general tree. Leaf nodes can also be called external nodes.
Internal nodes: A node has atleast one child node known as an internal node.

DR. R. K. SHANMUGAM COLLEGE OF ARTS AND SCIENCE, KALLAKURICHI 18

ANALYSIS & DESIGN OF ALGORITHMS (23PCSCC11) UNIT – 1
I M. Sc., Computer Science Semester: 1

Ancestor node: An ancestor of a node is any predecessor node on a path from the
root to that node. The root node doesn't have any ancestors. In the tree shown in the
above image, nodes 1, 2, and 5 are the ancestors of node 10.
Descendant: The immediate successor of the given node is known as a descendant of
a node. In the above figure, 10 is the descendant of node 5.

DR. R. K. SHANMUGAM COLLEGE OF ARTS AND SCIENCE, KALLAKURICHI 19

ANALYSIS & DESIGN OF ALGORITHMS (23PCSCC11) UNIT – 1
I M. Sc., Computer Science Semester: 1
Applications of trees
 Storing naturally hierarchical data: Trees are used to store the data in the
hierarchical structure. For example, the file system. The file system stored on
the disc drive, the file and folder are in the form of the naturally hierarchical
data and stored in the form of trees.
 Organize data: It is used to organize data for efficient insertion, deletion and
searching. For example, a binary tree has a logN time for searching an
element.
 Trie: It is a special kin
 d of tree that is used to store the dictionary. It is a fast and efficient way for
dynamic spell checking.
 Heap: It is also a tree data structure implemented using arrays. It is used to
implement priority queues.
 B-Tree and B+Tree: B-Tree and B+Tree are the tree data structures used to
implement indexing in databases.
 Routing table: The tree data structure is also used to store the data in routing
tables in the routers.
Types of Binary Tree
1) Binary Tree
2) Binary Search Tree

DR. R. K. SHANMUGAM COLLEGE OF ARTS AND SCIENCE, KALLAKURICHI 20

ANALYSIS & DESIGN OF ALGORITHMS (23PCSCC11) UNIT – 1
I M. Sc., Computer Science Semester: 1
BINARY TREE
The Binary tree means that the node can have maximum two children. Here,
binary name itself suggests that 'two';
therefore, each node can have either 0,
1 or 2 children. The above tree is a
binary tree because each node contains
the utmost two children.
Properties of Binary Tree
 At each level of i, the maximum
number of nodes is 2i.
 The height of the tree is defined
as the longest path from the
 root node to the leaf node. The
tree which is shown above has a
height equal to 3. Therefore, the
maximum number of nodes at height 3 is equal to (1+2+4+8) = 15. In general,
the maximum number of nodes possible at height h is (2 0 + 21 + 22+….2h) =
2h+1 -1.
 The minimum number of nodes possible at height h is equal to h+1.
 If the number of nodes is minimum, then the height of the tree would be
maximum. Conversely, if the number of nodes is maximum, then the height of
the tree would be minimum.
Types of Binary Tree
1) Full/ proper/ strict Binary tree
2) Complete Binary tree
3) Perfect Binary tree
4) Degenerate Binary tree
5) Balanced Binary tree

DR. R. K. SHANMUGAM COLLEGE OF ARTS AND SCIENCE, KALLAKURICHI 21

ANALYSIS & DESIGN OF ALGORITHMS (23PCSCC11) UNIT – 1
I M. Sc., Computer Science Semester: 1
BINARY SEARCH TREE
A binary search tree follows some order to arrange the elements. In a Binary
search tree, the value of left node must be smaller than the parent node, and the
value of right node must be greater than the parent node. This rule is applied
recursively to the left and right subtrees of the root.

In the above figure, we can observe that the root node is 40, and all the nodes
of the left subtree are smaller than the root node, and all the nodes of the right
subtree are greater than the root node.
Similarly, we can see the left child of root node is greater than its left child and
smaller than its right child. So, it also satisfies the property of binary search tree.
Therefore, we can say that the tree in the above image is a binary search tree.

DR. R. K. SHANMUGAM COLLEGE OF ARTS AND SCIENCE, KALLAKURICHI 22

ANALYSIS & DESIGN OF ALGORITHMS (23PCSCC11) UNIT – 1
I M. Sc., Computer Science Semester: 1
Example of creating a binary search tree
Now, let's see the creation of binary search tree using an example.
Suppose the data elements are - 45, 15, 79, 90, 10, 55, 12, 20, 50
➢ First, we have to insert 45 into the tree as the root of the tree.
➢ Then, read the next element; if it is smaller than the root node, insert it as the root
of the left subtree, and move to the next element.
➢ Otherwise, if the element is larger than the root node, then insert it as the root of
the right subtree.

DR. R. K. SHANMUGAM COLLEGE OF ARTS AND SCIENCE, KALLAKURICHI 23

ANALYSIS & DESIGN OF ALGORITHMS (23PCSCC11) UNIT – 1
I M. Sc., Computer Science Semester: 1

BINARY SEARCH TREE

 Each node contains utmost 2 values
 Left subtree value is less than root node
 Right subtree value is greater than root node

Draw a BST for the following:

11, 6, 8, 19, 4, 10, 5
Step 1: 11 as the root node
Step 2: 6 is less than root node, so insert it to the left node
Step 3: 8 is less than root node, so insert it to the left node but to the right of 6, as 8 is
greater than 6.

11 11
11

6 6

DR. R. K. SHANMUGAM COLLEGE OF ARTS AND SCIENCE, KALLAKURICHI 24

ANALYSIS & DESIGN OF ALGORITHMS (23PCSCC11) UNIT – 1
I M. Sc., Computer Science Semester: 1

Step 4: 19 is greater than root node, so insert it to the right node.

11

6 19

Step 5: 4 is lesser than root node, so insert it to the left node.

11

6 19

4
8

DR. R. K. SHANMUGAM COLLEGE OF ARTS AND SCIENCE, KALLAKURICHI 25

ANALYSIS & DESIGN OF ALGORITHMS (23PCSCC11) UNIT – 1
I M. Sc., Computer Science Semester: 1
Step 6: 10 is lesser than root node, so insert to the left; insert to the left of 8 as 10 is
greater than 8
11

6 19

4
8

10

Step 7: 5 is lesser than root node and hence it must be in left subtree

11

6 19

4
8

5
10

DR. R. K. SHANMUGAM COLLEGE OF ARTS AND SCIENCE, KALLAKURICHI 26

ANALYSIS & DESIGN OF ALGORITHMS (23PCSCC11) UNIT – 1
I M. Sc., Computer Science Semester: 1
Algorithm to search an element in Binary search tree

Search (root, item)

if (item = root → data) or (root = NULL)

return root

else if (item < root → data)

return Search(root → left, item)

else

return Search(root → right, item)

END if

End;

Deletion in Binary Search tree

In a binary search tree, we must delete a node from the tree by keeping in
mind that the property of BST is not violated. To delete a node from BST, there are
three possible situations occur -
 The node to be deleted is the leaf node, or,
 The node to be deleted has only one child, and,
 The node to be deleted has two children
When the node to be deleted is the leaf node
It is the simplest case to delete a node in BST. Here, we have to replace the
leaf node with NULL and simply free the allocated space.
We can see the process to delete a leaf node from BST in the below image. In
below image, suppose we have to delete node 90, as the node to be deleted is a leaf
node, so it will be replaced with NULL, and the allocated space will free.

DR. R. K. SHANMUGAM COLLEGE OF ARTS AND SCIENCE, KALLAKURICHI 27

ANALYSIS & DESIGN OF ALGORITHMS (23PCSCC11) UNIT – 1
I M. Sc., Computer Science Semester: 1

When the node to be deleted has only one child

In this case, we have to replace the target node with its child, and then delete
the child node. It means that after replacing the target node with its child node, the
child node will now contain the value to be deleted. So, we simply have to replace
the child node with NULL and free up the allocated space.
We can see the process of deleting a node with one child from BST in the
below image. In the below image, suppose we have to delete the node 79, as the node
to be deleted has only one child, so it will be replaced with its child 55.
So, the replaced node 79 will now be a leaf node that can be easily deleted.

DR. R. K. SHANMUGAM COLLEGE OF ARTS AND SCIENCE, KALLAKURICHI 28

ANALYSIS & DESIGN OF ALGORITHMS (23PCSCC11) UNIT – 1
I M. Sc., Computer Science Semester: 1
When the node to be deleted has two children
This case of deleting a node in BST is a bit complex among other two cases. In
such a case, the steps to be followed are listed as follows -
 First, find the inorder successor of the node to be deleted.
 After that, replace that node with the inorder successor until the target node is
placed at the leaf of tree.
 And at last, replace the node with NULL and free up the allocated space.
The inorder successor is required when the right child of the node is not empty.
We can obtain the inorder successor by finding the minimum element in the right
child of the node.
We can see the process of deleting a node with two children from BST in the
below image. In the below image, suppose we have to delete node 45 that is the root
node, as the node to be deleted has two children, so it will be replaced with its
inorder successor. Now, node 45 will be at the leaf of the tree so that it can be deleted
easily.

Insertion in Binary Search tree

A new key in BST is always inserted at the leaf. To insert an element in BST,
we have to start searching from the root node; if the node to be inserted is less than
the root node, then search for an empty location in the left subtree. Else, search for
the empty location in the right subtree and insert the data. Insert in BST is similar to

DR. R. K. SHANMUGAM COLLEGE OF ARTS AND SCIENCE, KALLAKURICHI 29

ANALYSIS & DESIGN OF ALGORITHMS (23PCSCC11) UNIT – 1
I M. Sc., Computer Science Semester: 1
searching, as we always have to maintain the rule that the left subtree is smaller than
the root, and right subtree is larger than the root.

[For more examples on constructing the BST from Preorder and Postorder, refer to
class notes….]
HEAP
A heap is a complete binary tree, and the binary tree is a tree in which the
node can have utmost two children.
A complete binary tree is a binary tree in which all the levels except the last
level, i.e., leaf node should be completely filled, and all the nodes should be left-
justified.

DR. R. K. SHANMUGAM COLLEGE OF ARTS AND SCIENCE, KALLAKURICHI 30

ANALYSIS & DESIGN OF ALGORITHMS (23PCSCC11) UNIT – 1
I M. Sc., Computer Science Semester: 1


We can observe that all the internal
nodes are completely filled except the
leaf node; therefore, we can say that the
above tree is a complete binary tree.


We can observe that all the internal
nodes are completely filled except
the leaf node, but the leaf nodes are
added at the right part; therefore,
the above tree is not a complete
binary tree.

The heap tree is a special balanced binary tree data structure where the root node is
compared with its children and arrange accordingly.
Types of Heap:
There are two types of the heap:
1. Min Heap
2. Max heap

DR. R. K. SHANMUGAM COLLEGE OF ARTS AND SCIENCE, KALLAKURICHI 31

ANALYSIS & DESIGN OF ALGORITHMS (23PCSCC11) UNIT – 1
I M. Sc., Computer Science Semester: 1
Min Heap: The value of the parent node should be less than or equal to either of its
children. Or In other words, the min-heap can be defined as, for every node i, the
value of node i is greater than or equal to its parent value except the root node.
Mathematically, it can be defined as:
A[Parent(i)] <= A[i]

11 is the root node, and the value of the root node is less than the value of all
the other nodes (left child or a right child).
Max Heap: The value of the parent node is greater than or equal to its children. Or
In other words, the max heap can be defined as for every node i; the value of node i
is less than or equal to its parent value except the root node. Mathematically, it can
be defined as: A[Parent(i)] >= A[i]

 44 is the root node, and the value of

the root node is greater than the value
of all the other nodes (left child or a
right child).

DR. R. K. SHANMUGAM COLLEGE OF ARTS AND SCIENCE, KALLAKURICHI 32

ANALYSIS & DESIGN OF ALGORITHMS (23PCSCC11) UNIT – 1
I M. Sc., Computer Science Semester: 1
Max Heap Construction Algorithm
Step 1 − Create a new node at the end of heap.
Step 2 − Assign new value to the node.
Step 3 − Compare the value of this child node with its parent.
Step 4 − If value of parent is less than child, then swap them.
Step 5 − Repeat step 3 & 4 until Heap property holds.
Min Heap Construction Algorithm
Step 1 − Create a new node at the end of heap.
Step 2 − Assign new value to the node.
Step 3 − Compare the value of this child node with its parent.
Step 4 − If value of parent is greater than child, then swap them.
Step 5 − Repeat step 3 & 4 until Heap property holds.

// Procedure to insert an element in the max heap.

insertHeap(A, n, value)
{
n=n+1; // n is incremented to insert the new element
A[n]=value; // assign new value at the nth position
i = n; // assign the value of n to i
while(i>1)
{
parent= floor value of i/2; // Calculating the floor value of i/2
if(A[parent]<A[i])
{
swap(A[parent], A[i]);
i = parent;
}
else
{
return;
}
}
}

DR. R. K. SHANMUGAM COLLEGE OF ARTS AND SCIENCE, KALLAKURICHI 33

ANALYSIS & DESIGN OF ALGORITHMS (23PCSCC11) UNIT – 1
I M. Sc., Computer Science Semester: 1
Example:
Create a Max Heap Tree for the following
44, 33, 77, 11, 55
Step 1: First we add the 44 element in the tree

Step 2: The next element is 33. As we know that insertion in the binary tree always
starts from the left side so 33 will be added at the left of 44

Step 3: The next element is 77 and it will be added to the right of the 44.

As we can observe in the above tree that it does not satisfy the max heap property,
i.e., parent node 44 is less than the child 77. So, we will swap these two values

DR. R. K. SHANMUGAM COLLEGE OF ARTS AND SCIENCE, KALLAKURICHI 34

ANALYSIS & DESIGN OF ALGORITHMS (23PCSCC11) UNIT – 1
I M. Sc., Computer Science Semester: 1

Step 4: The next element is 11. The node 11 is added to the left of 33.

Step 5: The next element is 55. To make it a complete binary tree, we will add the
node 55 to the right of 33

DR. R. K. SHANMUGAM COLLEGE OF ARTS AND SCIENCE, KALLAKURICHI 35

ANALYSIS & DESIGN OF ALGORITHMS (23PCSCC11) UNIT – 1
I M. Sc., Computer Science Semester: 1
As we can observe in the above figure that it does not satisfy the property of the max
heap because 33<55, so we will swap these two values

Step 6: As there are no elements to be inserted, this is the final max heap tree.

DR. R. K. SHANMUGAM COLLEGE OF ARTS AND SCIENCE, KALLAKURICHI 36

ANALYSIS & DESIGN OF ALGORITHMS (23PCSCC11) UNIT – 1
I M. Sc., Computer Science Semester: 1
Heap Sort
Heap sort processes the elements by creating the min-heap or max-heap using
the elements of the given array. Min-heap or max-heap represents the ordering of
array in which the root element represents the minimum or maximum element of the
array.
Heap sort basically recursively performs two main operations
 Build a heap H, using the elements of array.
 Repeatedly delete the root element of the heap formed in 1st phase.

A heap is a complete binary tree, and the binary tree is a tree in which the node
can have the utmost two children. A complete binary tree is a binary tree in which
all the levels except the last level, i.e., leaf node, should be completely filled, and
all the nodes should be left-justified.

Heap sort is a popular and efficient sorting algorithm. The concept of heap
sort is to eliminate the elements one by one from the heap part of the list, and then
insert them into the sorted part of the list. Heap sort is the in-place sorting algorithm.
Algorithm
HeapSort(arr)
BuildMaxHeap(arr)
for i = length(arr) to 2
swap arr[1] with arr[i]
heap_size[arr] = heap_size[arr] ? 1
MaxHeapify(arr,1)
End

DR. R. K. SHANMUGAM COLLEGE OF ARTS AND SCIENCE, KALLAKURICHI 37

ANALYSIS & DESIGN OF ALGORITHMS (23PCSCC11) UNIT – 1
I M. Sc., Computer Science Semester: 1
BuildMaxHeap(arr)
BuildMaxHeap(arr)
heap_size(arr) = length(arr)
for i = length(arr)/2 to 1
MaxHeapify(arr,i)
End
MaxHeapify(arr,i)
MaxHeapify(arr,i)
L = left(i)
R = right(i)
if L ? heap_size[arr] and arr[L] > arr[i]
largest = L
else
largest = i
if R ? heap_size[arr] and arr[R] > arr[largest]
largest = R
if largest != i
swap arr[i] with arr[largest]
MaxHeapify(arr,largest)
End

DR. R. K. SHANMUGAM COLLEGE OF ARTS AND SCIENCE, KALLAKURICHI 38

ANALYSIS & DESIGN OF ALGORITHMS (23PCSCC11) UNIT – 1
I M. Sc., Computer Science Semester: 1
Example:

First, we have to construct a heap from the given array and convert it into max heap.

After converting the given heap into max heap, the array elements are -

Next, we have to delete the root element (89) from the max heap. To delete this
node, we have to swap it with the last node, i.e. (11). After deleting the root element,
we again have to heapify it to convert it into max heap.

DR. R. K. SHANMUGAM COLLEGE OF ARTS AND SCIENCE, KALLAKURICHI 39

ANALYSIS & DESIGN OF ALGORITHMS (23PCSCC11) UNIT – 1
I M. Sc., Computer Science Semester: 1
After swapping the array element 89 with 11, and converting the heap into max-
heap, the elements of array are -

In the next step, again, we have to delete the root element (81) from the max heap.
To delete this node, we have to swap it with the last node, i.e. (54). After deleting the
root element, we again have to heapify it to convert it into max heap.

After swapping the array element 81 with 54 and converting the heap into max-heap,
the elements of array are –

In the next step, we have to delete the root element (76) from the max heap again. To
delete this node, we have to swap it with the last node, i.e. (9). After deleting the root
element, we again have to heapify it to convert it into max heap.

DR. R. K. SHANMUGAM COLLEGE OF ARTS AND SCIENCE, KALLAKURICHI 40

ANALYSIS & DESIGN OF ALGORITHMS (23PCSCC11) UNIT – 1
I M. Sc., Computer Science Semester: 1
After swapping the array element 76 with 9 and converting the heap into max-heap,
the elements of array are –

In the next step, again we have to delete the root element (54) from the max heap. To
delete this node, we have to swap it with the last node, i.e. (14). After deleting the
root element, we again have to heapify it to convert it into max heap.

In the next step, again we have to delete the root element (22) from the max heap. To
delete this node, we have to swap it with the last node, i.e. (11). After deleting the
root element, we again have to heapify it to convert it into max heap.

DR. R. K. SHANMUGAM COLLEGE OF ARTS AND SCIENCE, KALLAKURICHI 41

ANALYSIS & DESIGN OF ALGORITHMS (23PCSCC11) UNIT – 1
I M. Sc., Computer Science Semester: 1

In the next step, again we have to delete the root element (14) from the max heap. To
delete this node, we have to swap it with the last node, i.e. (9). After deleting the root
element, we again have to heapify it to convert it into max heap.

In the next step, again we have to delete the root element (11) from the max heap. To
delete this node, we have to swap it with the last node, i.e. (9). After deleting the root
element, we again have to heapify it to convert it into max heap.

Now, heap has only one element left. After deleting it, heap will be empty.

DR. R. K. SHANMUGAM COLLEGE OF ARTS AND SCIENCE, KALLAKURICHI 42

ANALYSIS & DESIGN OF ALGORITHMS (23PCSCC11) UNIT – 1
I M. Sc., Computer Science Semester: 1

Now, the array is completely sorted.

Complexity of Heap Sort

Case Time Complexity
Best Case O(n logn)
Average Case O(n logn)
Worst Case O(n logn)

GRAPH
A graph can be defined as group of vertices and edges that are used to connect
these vertices. A graph can be seen as a cyclic tree, where the vertices (Nodes)
maintain any complex relationship among them instead of having parent child
relationship.
Definition
A graph G can be defined as an ordered set G(V, E) where V(G) represents the
set of vertices and E(G) represents the set of edges which are used to connect these
vertices.
A Graph G(V, E) with 5 vertices (A, B, C, D, E) and six edges ((A,B), (B,C),
(C,E), (E,D), (D,B), (D,A)) is shown in the following figure.

DR. R. K. SHANMUGAM COLLEGE OF ARTS AND SCIENCE, KALLAKURICHI 43

ANALYSIS & DESIGN OF ALGORITHMS (23PCSCC11) UNIT – 1
I M. Sc., Computer Science Semester: 1
Directed and Undirected Graph
A graph can be directed or undirected. However, in an undirected graph,
edges are not associated with the directions with them. An undirected graph is
shown in the above figure since its edges are not attached with any of the directions.
If an edge exists between vertex A and B then the vertices can be traversed from B to
A as well as A to B.
In a directed graph, edges form an ordered pair. Edges represent a specific
path from some vertex A to another vertex B. Node A is called initial node while
node B is called terminal node.

Graph Terminology
Path: A path can be defined as the sequence of nodes that are followed in order to
reach some terminal node V from the initial node U.
Closed Path: A path will be called as closed path if the initial node is same as
terminal node. A path will be closed path if V0=VN.
Simple Path: If all the nodes of the graph are distinct with an exception V0=VN,
then such path P is called as closed simple path.
Cycle: A cycle can be defined as the path which has no repeated edges or vertices
except the first and last vertices.

DR. R. K. SHANMUGAM COLLEGE OF ARTS AND SCIENCE, KALLAKURICHI 44

ANALYSIS & DESIGN OF ALGORITHMS (23PCSCC11) UNIT – 1
I M. Sc., Computer Science Semester: 1
Connected Graph: A connected graph is the one in which some path exists between
every two vertices (u, v) in V. There are no isolated nodes in connected graph.
Complete Graph: A complete graph is the one in which every node is connected with
all other nodes. A complete graph contain n(n-1)/2 edges where n is the number of
nodes in the graph.
Weighted Graph: In a weighted graph, each edge is assigned with some data such as
length or weight. The weight of an edge e can be given as w(e) which must be a
positive (+) value indicating the cost of traversing the edge.
Digraph: A digraph is a directed graph in which each edge of the graph is associated
with some direction and the traversing can be done only in the specified direction.
Loop: An edge that is associated with the similar end points can be called as Loop.
Adjacent Nodes: If two nodes u and v are connected via an edge e, then the nodes u
and v are called as neighbours or adjacent nodes.
Degree of the Node: A degree of a node is the number of edges that are connected
with that node. A node with degree 0 is called as isolated node.
Graph representation
A graph is a data structure that consist a sets of vertices (called nodes) and
edges. There are two ways to store Graphs into the computer's memory:
 Sequential representation (or, Adjacency matrix representation)
 Linked list representation (or, Adjacency list representation)
In sequential representation, an adjacency matrix is used to store the graph. Whereas
in linked list representation, there is a use of an adjacency list to store the graph.

DR. R. K. SHANMUGAM COLLEGE OF ARTS AND SCIENCE, KALLAKURICHI 45

ANALYSIS & DESIGN OF ALGORITHMS (23PCSCC11) UNIT – 1
I M. Sc., Computer Science Semester: 1

DR. R. K. SHANMUGAM COLLEGE OF ARTS AND SCIENCE, KALLAKURICHI 46

ANALYSIS & DESIGN OF ALGORITHMS (23PCSCC11) UNIT – 1
I M. Sc., Computer Science Semester: 1

BFS
Breadth-first search is a graph traversal algorithm that starts traversing the
graph from the root node and explores all the neighboring nodes. Then, it selects the
nearest node and explores all the unexplored nodes. While using BFS for traversal,
any node in the graph can be considered as the root node.

DR. R. K. SHANMUGAM COLLEGE OF ARTS AND SCIENCE, KALLAKURICHI 47

ANALYSIS & DESIGN OF ALGORITHMS (23PCSCC11) UNIT – 1
I M. Sc., Computer Science Semester: 1
BFS Algorithm
Step 1: SET STATUS = 1 (ready state) for each node in G
Step 2: Enqueue the starting node A and set its STATUS = 2 (waiting state)
Step 3: Repeat Steps 4 and 5 until QUEUE is empty
Step 4: Dequeue a node N. Process it and set its STATUS = 3 (processed state).
Step 5: Enqueue all the neighbours of N that are in the ready state (whose STATUS
= 1) and set their STATUS = 2
Step 6: Exit
Example:

In the above graph, minimum path 'P' can be found by using the BFS that will start
from Node A and end at Node E. The algorithm uses two queues, namely QUEUE1
and QUEUE2. QUEUE1 holds all the nodes that are to be processed, while
QUEUE2 holds all the nodes that are processed and deleted from QUEUE1.
Now, let's start examining the graph starting from Node A.
Step 1 - First, add A to queue1 and NULL to queue2.
QUEUE1 = {A}
QUEUE2 = {NULL}
Step 2 - Now, delete node A from queue1 and add it into queue2. Insert all neighbors
of node A to queue1.
QUEUE1 = {B, D}
QUEUE2 = {A}
Step 3 - Now, delete node B from queue1 and add it into queue2. Insert all neighbors
of node B to queue1.

DR. R. K. SHANMUGAM COLLEGE OF ARTS AND SCIENCE, KALLAKURICHI 48

ANALYSIS & DESIGN OF ALGORITHMS (23PCSCC11) UNIT – 1
I M. Sc., Computer Science Semester: 1
QUEUE1 = {D, C, F}
QUEUE2 = {A, B}
Step 4 - Now, delete node D from queue1 and add it into queue2. Insert all neighbors
of node D to queue1. The only neighbor of Node D is F since it is already inserted,
so it will not be inserted again.
QUEUE1 = {C, F}
QUEUE2 = {A, B, D}
Step 5 - Delete node C from queue1 and add it into queue2. Insert all neighbors of
node C to queue1.
QUEUE1 = {F, E, G}
QUEUE2 = {A, B, D, C}
Step 5 - Delete node F from queue1 and add it into queue2. Insert all neighbors of
node F to queue1. Since all the neighbors of node F are already present, we will not
insert them again.
QUEUE1 = {E, G}
QUEUE2 = {A, B, D, C, F}
Step 6 - Delete node E from queue1. Since all of its neighbors have already been
added, so we will not insert them again. Now, all the nodes are visited, and the target
node E is encountered into queue2.
QUEUE1 = {G}
QUEUE2 = {A, B, D, C, F, E}
BFS & DFS Algorithm
Time Complexity: O(V+E) Space Complexity: O(V)

DR. R. K. SHANMUGAM COLLEGE OF ARTS AND SCIENCE, KALLAKURICHI 49

ANALYSIS & DESIGN OF ALGORITHMS (23PCSCC11) UNIT – 1
I M. Sc., Computer Science Semester: 1
DFS
DFS is a recursive algorithm to search all the vertices of a tree data structure
or a graph. The depth-first search (DFS) algorithm starts with the initial node of
graph G and goes deeper until we find the goal node or the node with no children.
Because of the recursive nature, stack data structure can be used to implement the
DFS algorithm. The process of implementing the DFS is similar to the BFS
algorithm.
The step by step process to implement the DFS traversal is given as follows -
1. First, create a stack with the total number of vertices in the graph.
2. Now, choose any vertex as the starting point of traversal, and push that vertex
into the stack.
3. After that, push a non-visited vertex (adjacent to the vertex on the top of the
stack) to the top of the stack.
4. Now, repeat steps 3 and 4 until no vertices are left to visit from the vertex on
the stack's top.
5. If no vertex is left, go back and pop a vertex from the stack.
6. Repeat steps 2, 3, and 4 until the stack is empty.
Algorithm
Step 1: SET STATUS = 1 (ready state) for each node in G
Step 2: Push the starting node A on the stack and set its STATUS = 2 (waiting state)
Step 3: Repeat Steps 4 and 5 until STACK is empty
Step 4: Pop the top node N. Process it and set its STATUS = 3 (processed state)
Step 5: Push on the stack all the neighbors of N that are in the ready state (whose
STATUS = 1) and set their STATUS = 2 (waiting state)
Step 6: EXIT

DR. R. K. SHANMUGAM COLLEGE OF ARTS AND SCIENCE, KALLAKURICHI 50

ANALYSIS & DESIGN OF ALGORITHMS (23PCSCC11) UNIT – 1
I M. Sc., Computer Science Semester: 1
Pseudocode
DFS(G,v) ( v is the vertex where the search starts )
Stack S := {}; ( start with an empty stack )
for each vertex u, set visited[u] := false;
push S, v;
while (S is not empty) do
u := pop S;
if (not visited[u]) then
visited[u] := true;
for each unvisited neighbour w of uu
push S, w;
end if
end while
END DFS()
Example:

Step 1 - First, push H onto the stack.

STACK: H
Step 2 - POP the top element from the stack, i.e., H, and print it. Now, PUSH all the
neighbors of H onto the stack that are in ready state.
Print: H]STACK: A

DR. R. K. SHANMUGAM COLLEGE OF ARTS AND SCIENCE, KALLAKURICHI 51

ANALYSIS & DESIGN OF ALGORITHMS (23PCSCC11) UNIT – 1
I M. Sc., Computer Science Semester: 1
Step 3 - POP the top element from the stack, i.e., A, and print it. Now, PUSH all the
neighbors of A onto the stack that are in ready state.
Print: A
STACK: B, D
Step 4 - POP the top element from the stack, i.e., D, and print it. Now, PUSH all the
neighbors of D onto the stack that are in ready state.
Print: D
STACK: B, F
Step 5 - POP the top element from the stack, i.e., F, and print it. Now, PUSH all the
neighbors of F onto the stack that are in ready state.
Print: F
STACK: B
Step 6 - POP the top element from the stack, i.e., B, and print it. Now, PUSH all the
neighbors of B onto the stack that are in ready state.
Print: B
STACK: C
Step 7 - POP the top element from the stack, i.e., C, and print it. Now, PUSH all the
neighbors of C onto the stack that are in ready state.
Print: C
STACK: E, G
Step 8 - POP the top element from the stack, i.e., G and PUSH all the neighbors of G
onto the stack that are in ready state.
Print: G
STACK: E
Step 9 - POP the top element from the stack, i.e., E and PUSH all the neighbors of E
onto the stack that are in ready state.
Print: E
STACK:
Now, all the graph nodes have been traversed, and the stack is empty.

DR. R. K. SHANMUGAM COLLEGE OF ARTS AND SCIENCE, KALLAKURICHI 52

ANALYSIS & DESIGN OF ALGORITHMS (23PCSCC11) UNIT – 1
I M. Sc., Computer Science Semester: 1

DR. R. K. SHANMUGAM COLLEGE OF ARTS AND SCIENCE, KALLAKURICHI 53