UNIT – I ABSTRACT DATA TYPES AND LINEAR DATA STRUCTURES

Abstract Data Types (ADTs) - Stack ADT – Operations – Applications – Balancing Symbols –
Evaluating arithmetic expressions Infix to Postfix conversion – Queue ADT – Operations –
Circular Queue – DeQueue – Applications of Queues.

Data: - Raw information or unprocessed information is called data.

Data Structure: - Data Structure is a mathematical model to store and organize data so that it can
be used efficiently.
Characteristics of a Data Structure:
❖ Correctness − Data structure implementation should implement its interface correctly.
❖ Time Complexity − Running time or the execution time of operations of data structure
must be as small as possible.
❖ Space Complexity − Memory usage of a data structure operation should be as little as
possible.
Need for Data Structure:
As applications are getting complex and data rich, there are three common problems that
applications face now-a-days.
▪ Data Search
▪ Processor speed
▪ Multiple requests
To solve the above-mentioned problems, data structures come to rescue. Data can be organized in
a data structure in such a way that all items may not be required to be searched, and the required
data can be searched almost instantly.
CLASSIFICATION OF DATA STRUCTURES:

Linear Data Structures:

• A data structure is called linear if all of its elements are arranged in the linear order.
• In linear data structures, the elements are stored in non-hierarchical way where each element
has the successors and predecessors except the first and last element.
Non Linear Data Structures:
• This data structure does not form a sequence i.e. each item or element is connected with two or
more other items in a non-linear arrangement.
• The data elements are not arranged in sequential structure.
THE LINEAR LIST DATA STRUCTURE:LIST:
A list is a data structure. It is an ordered set of elements.
In general list is formatted as follows –
A1 A2 A3 ……… An
Where,
A1 is the first element.
An is the last element.
n is the size of the List.
We can implement the list data structure by following three ways –
1. Array implementation.
2. Linked List Implementation.
3. Cursor Implementation.
LIST:
A list is a data structure. It is an ordered set of elements.
In general list is formatted as follows –
A1 A2 A3 ……… An
Where,
A1 is the first element.
An is the last element.
n is the size of the List.
We can implement the list data structure by following three ways –
4. Array implementation.
5. Linked List Implementation.
6. Cursor Implementation.
ADT: Define ADT.
❖ ADT stands for Abstract Data Type.
❖ It mentions what operations are to be performed but not how these operations will
beimplemented.
❖ It does not specify how data will be organized in memory and what algorithms will be
usedfor implementing the operations.
❖ It is called “abstract” because it gives an implementation-independent view.
Stack ADT:
1. Stack is an ordered list in which, insertion and deletion can be performed only at one end
that is called top.
2. Stack is a recursive data structure having pointer to its top element.
3. Stacks are sometimes called as Last-In-First-Out (LIFO) lists i.e. the element which is
inserted first in the stack, will be deleted last from the stack.
Operations on Stack
There are various operations which can be performed on stack.

1. Push: Adding an element onto the stack

2. Pop: Removing an element from the stack

Stack Implementation:

There are several ways to implement stack. They are –

1. Array Implementation
2. Linked List implementation

Array Implementation:
❖ Stack can be implemented using one-dimensional array. One-dimensional array is usedto
hold elements of a stack.
❖ Implementing a stack using array can store fixed number of data values.
❖ In a stack, initially top is set to -1.
❖ Top is used to keep track of the index of the top most elements.
Linked List implementation of Stack:
❖ Instead of using array, we can also use linked list to implement stack.
❖ Linked list allocates the memory dynamically. However, time complexity in both the
scenario is same for all the operations i.e. push, pop and peek.
❖ In linked list implementation of stack, the nodes are maintained non-contiguously in the
memory.
❖ Each node contains a pointer to its immediate successor node in the stack.

Array Based Implementation Of Stack :

top=0
mymax=eval(input("enter maximum size of stack"))
def createstack():
stack=[]
return stack
def isempty(stack):
return len(stack)==0
def push(stack,item):
stack.append(item)
print("pushed to stack",item)
def pop(stack):
if isempty(stack):
return"stack underflow"
return stack.pop()
stack=createstack()
while True:
print("1.push")
print("2.pop")
print("3.display")
print("4.quit")
ch=int(input("enter your choice:"))
if ch==1:
if top<mymax:
item=input("enter any elements:")
push(stack,item)
top+=1
else:
print("stack overflow")
 elif ch==2:
print(pop(stack))
elif ch==3:
print(stack)
else:
print("exit")
break

APPLICATIONS OF STACK :
o Evaluation of Arithmetic Expressions
o Balancing Symbols
o Backtracking
o Delimiter Checking
o Reverse a Data
o Processing Function Calls

Evaluation of Arithmetic Expressions

A stack is a very effective data structure for evaluating arithmetic expressions in programming
languages. An arithmetic expression consists of operands and operators.

Backtracking

Backtracking is another application of Stack. It is a recursive algorithm that is used for solving the
optimization problem

Delimiter Checking

The common application of Stack is delimiter checking, i.e., parsing that involves analyzing a source
program syntactically. It is also called parenthesis checking. Different types of delimiters include the
parenthesis checking (,), curly braces {,} and square brackets [,], and common delimiters /* and */.
Every opening delimiter must match a closing delimiter.

Reverse a Data:

To reverse a given set of data, we need to reorder the data so that the first and last elements are
exchanged, the second and second last element are exchanged, and so on for all other elements.

There are different reversing applications:

o Reversing a string
o Converting Decimal to Binary

Processing Function Calls:

Stack plays an important role in programs that call several functions in succession
Evaluation of Arithmetic Expression requires two steps:
o First, convert the given expression into special notation.
o Evaluate the expression in this new notation.

Notations for Arithmetic Expression

There are three notations to represent an arithmetic expression:

o Infix Notation
o Prefix Notation
o Postfix Notation

Infix Notation

The infix notation is a convenient way of writing an expression in which each operator is placed
between the operands. Infix expressions can be parenthesized or unparenthesized depending upon the
problem requirement.

Example: A + B, (C - D) etc.

All these expressions are in infix notation because the operator comes between the operands.

Prefix Notation

The prefix notation places the operator before the operands. This notation was introduced by the Polish
mathematician and hence often referred to as polish notation.

Example: + A B, -CD etc.

All these expressions are in prefix notation because the operator comes before the operands.

Postfix Notation

The postfix notation places the operator after the operands. This notation is just the reverse of Polish
notation and also known as Reverse Polish notation.

Example: AB +, CD+, etc.

All these expressions are in postfix notation because the operator comes after the operands.

Conversion of Arithmetic Expression into various Notations:

Infix Notation Prefix Notation Postfix Notation

A*B *AB AB*

(A+B)/C /+ ABC AB+C/

(A*B) + (D-C) +*AB – DC AB*DC-+

Conversion of Infix to Postfix
1. Read the characters from left to right.
2. If the character is operand, then insert it into postfix string.
3. If the character if operator, then if the stack is empty or contains a left parenthesis on top,
push the incoming operator onto the stack.
4. If the character is a left parenthesis, push it on the stack.
5. If the character is a right parenthesis, pop the stack and print the operators until you see a
left parenthesis. Discard the pair of parentheses.
6. If the incoming operator has higher precedence than the top of the stack, push it on the
stack.
7. If the incoming operator has lower precedence than the symbol on the top of the stack,
pop the stack and print the top operator. Then test the incoming operator against the new
top of stack.
8. If the incoming operator has equal precedence with the top of the stack, use
association. If the association is left to right, pop and print the top of the stack and then
push the incoming operator. If the association is right to left, push the incoming operator.
9. At the end of the expression, pop and print all operators on the stack. (No parentheses
should remain.)
Converting an infix expression into a postfix expression Example:
Evaluating Postfix expression:

Stack is the ideal data structure to evaluate the postfix expression because the top element is always the
most recent operand. The next element on the Stack is the second most recent operand to be operated
on.

Before evaluating the postfix expression, the following conditions must be checked. If any one of the
conditions fails, the postfix expression is invalid.

o When an operator encounters the scanning process, the Stack must contain a pair of operands or
intermediate results previously calculated.
o When an expression has been completely evaluated, the Stack must contain exactly one value

Example:

Infix expression 2 * (4+3) - 5.

Its equivalent postfix expression is 2 4 3 + * 5.

IMPLEMENTATION OF EVALUATING ARITHMETIC EXPRESSIONS:

def evaluate_postfix(postfix_expr):
stack = []
operators = set(['+', '-', '*', '/', '%', '^'])
for elem in postfix_expr:
if elem not in operators:
stack.append(float(elem))
else:
b = stack.pop()
 a = stack.pop()
if elem == '+':
stack.append(a + b)
elif elem == '-':
stack.append(a - b)
elif elem == '*':
stack.append(a * b)
elif elem == '/':
stack.append(a / b)
elif elem == '%':
stack.append(a % b)
elif elem == '^':
stack.append(a ** b)
return stack.pop()
postfix = '236*+' #Infix: 2 + 3 * 6
evaluate_postfix(postfix)
print('{} \t: {}'.format(postfix, evaluate_postfix(postfix)))
postfix = '23*6+' #Infix: 2 * 3 + 6
evaluate_postfix(postfix)
print('{} \t: {}'.format(postfix, evaluate_postfix(postfix)))
postfix = '23*42/+' #Infix: 2 * 3 + 4 / 2
evaluate_postfix(postfix)
print('{} : {}'.format(postfix, evaluate_postfix(postfix)))

OUTPUT:
236*+ : 20.0
23*6+ : 12.0
23*42/+ : 8.0

BALANCING SYMBOLS:
Suppose we wish to check a text string T to see if the bracket characters it contains are well
formed. We use the term brackets here to include character p tinct opening and closing characters such
as { }, < >, and ( ). The brackets are well formed if the number of openers is the same as the number of
closers and, reading the string from left to right, the number of closers never exceeds the number of
openers.
• A stack can be used to verify whether a program contains balanced braces
▪ An example of balanced braces
abc{defg{ijk}{l{mn}}op}qr
▪ An example of unbalanced braces
abc{def}}{ghij{kl}m
abc{def}{ghij{kl}m
Each time you encounter a “}”, it matches an already encountered “{”. When we reach the end
of the string, you have matched each “{”
 Figure 1.4 Balancing parenthesis
Algorithm for Balancing Symbols:
Step 1: Make an empty stack.
Step 2: Read characters until end of file.
Step3: If (Character= =’(‘ )
Step 4: Push ‘(‘symbol on to the stack
Step 5: Else if (Character= =’)‘ )
Step 6: Pop the stack upto ‘)’
Step 7: else
Step 8: Print the error report
Thus, for example,
()()() is well formed.
(()())) is not well formed.

QUEUE:
❖ Queue is a linear data structure where the element is inserted at one end called REAR and
deleted from the other end called as FRONT.
❖ Front points to the beginning of the queue and Rear points to the end of the queue.
❖ Queue follows the FIFO (First - In - First Out) structure.
❖ According to its FIFO structure, element inserted first will also be removed first.
❖ The enqueue() and dequeue() are two important operations used in a queue.
Operations on Queue:
Following are the basic operations performed on a Queue.

Operations Description
enqueue() This function defines adding an element into queue.
dequeue() This function defines removing an element from queue.
Queue Implementation:
There are several ways to implement queue. They are
1. Array implementation
2. Linked List implementation

Array implementation:
Array is the easiest way to implement a queue.
Array Name: Array_queue[10]
Input Values: 11, 12, 13, 14, 15, 16, 17, 18, 19, 20
Step 1: Initially front and rear value is -1. (Queue is Empty)

Step 2:

Step 3:
Step 4:

Step 5:

Step 6:

Step 7:

Step 8:
Step 9:

Step 10:

Step 11:

Queue Overflow:

DEQUEUE:
Step 1:
Step 2:

Step 3 to Step 9:

Linked List implementation of Queue:

❖ The array implementation cannot be used for the large scale applications where the
queues are implemented.
❖ One of the alternatives of array implementation is linked list implementation of queue.
❖ In a linked queue, each node of the queue consists of two parts i.e. data part and the link
part.
❖ Each element of the queue points to its immediate next element in the memory.

Array Based Implementation Of Queue

mymax = int(input("Enter maximum size of Queue: "))
front = 0
rear = 0
# Function to initialize an empty queue
def initialize_queue():
return []
# Function to check if the queue is empty
def is_empty(queue):
 return front == rear
# Function to check if the queue is full
def is_full(queue):
return rear - front == mymax
# Function to add an item to the queue (enqueue)
def enqueue(queue, item):
global rear
if is_full(queue):
print("Queue Overflow")
else:
queue.append(item)
rear += 1
print(f"Enqueued: {item}")
# Function to remove an item from the queue (dequeue)
def dequeue(queue):
global front
if is_empty(queue):
print("Queue is empty. Cannot dequeue.")
return None
else:
item = queue.pop(0)
front += 1
print(f"Dequeued: {item}")
return item
# Function to display the contents of the queue
def display_queue(queue):
if is_empty(queue):
print("Queue is empty.")
else:
print("Queue:", queue)

# Example usage with runtime input

queue = initialize_queue()
while True:
print("\nQueue Operations:")
print("1. Enqueue")
print("2. Dequeue")
print("3. Display Queue")
print("4. Quit")
choice = input("Enter your choice (1/2/3/4): ")
if choice == '1':
item = int(input("Enter the element to enqueue: "))
enqueue(queue, item)
elif choice == '2':
dequeue(queue)
elif choice == '3':
display_queue(queue)
elif choice == '4':
print("Quitting the program.")
break
else:
print("Invalid choice. Please enter a valid option.")
Double Ended Queues(DEQUE):
The deque stands for Double Ended Queue. Deque is a linear data structure where the
insertionand deletion operations are performed from both ends.

Types of deque

There are two types of deque -

o Input restricted queue

o Output restricted queue

Input restricted Queue

In input restricted queue, insertion operation can be performed at only one end, while deletion can
beperformed from both ends.

Output restricted Queue

In output restricted queue, deletion operation can be performed at only one end, while insertion can
beperformed from both ends.
Operations performed on deque

There are the following operations that can be applied on a deque -

o Insertion at front
o Insertion at rear
o Deletion at front
o Deletion at rear

In addition to the above operations, following operations are also supported in deque -

o Get the front item from the deque

o Get the rear item from the deque
o Check whether the deque is full or not
o Checks whether the deque is empty or not

Insertion at the front end

In this operation, the element is inserted from the front end of the queue. Before implementing the
operation, we first have to check whether the queue is full or not. If the queue is not full, then the
elementcan be inserted from the front end by using the below conditions -

o If the queue is empty, both rear and front are initialized with 0. Now, both will point to the
firstelement.
o Otherwise, check the position of the front if the front is less than 1 (front < 1), then
reinitialize itby front = n - 1, i.e., the last index of the array.
Insertion at the rear end

In this operation, the element is inserted from the rear end of the queue. Before implementing the
operation, we first have to check again whether the queue is full or not. If the queue is not full, then the
element can be inserted from the rear end by using the below conditions -

o If the queue is empty, both rear and front are initialized with 0. Now, both will point to the first
element.
o Otherwise, increment the rear by 1. If the rear is at last index (or size - 1), then instead of increasing
it by 1, we have to make it equal to 0.

Deletion at the front end

In this operation, the element is deleted from the front end of the queue. Before implementing the
operation, we first have to check whether the queue is empty or not.

If the queue is empty, i.e., front = -1, it is the underflow condition, and we cannot perform the deletion.
If the queue is not full, then the element can be inserted from the front end by using the below conditions
-

If the deque has only one element, set rear = -1 and front = -1.

Else if front is at end (that means front = size - 1), set front = 0.

Else increment the front by 1, (i.e., front = front + 1).

Deletion at the rear end

In this operation, the element is deleted from the rear end of the queue. Before implementing the
operation, we first have to check whether the queue is empty or not.

If the queue is empty, i.e., front = -1, it is the underflow condition, and we cannot perform the deletion.

If the deque has only one element, set rear = -1 and front = -1.

If rear = 0 (rear is at front), then set rear = n - 1.

Else, decrement the rear by 1 (or, rear = rear -1).

Check empty

This operation is performed to check whether the deque is empty or not. If front = -1, it means that the
deque is empty.

Check full

This operation is performed to check whether the deque is full or not. If front = rear + 1, or front = 0 and
rear = n - 1 it means that the deque is full.

The time complexity of all of the above operations of the deque is O(1), i.e., constant.

APPLICATIONS OF DEQUE
o Deque can be used as both stack and queue, as it supports both operations.
o Deque can be used as a palindrome checker means that if we read the string from both ends, the
string would be the same.

o Multiprocessor Scheduling: When multiple processes in a system are being carried out by
multiple processors like CPU, or Core, at that time that system uses a multiprocessor scheduling
algorithm. All the processors use our deque data structure to store all the different threads of
processes.

CIRCULAR QUEUE:
❖ In Circular Queue, Enqueue of a new element is performed at the very first location of
the queue if the last location of the queue is full.
❖ In such case the first element comes after the last element.
CIRCULAR QUEUE OPERATIONS

The circular queue work as follows:

• two pointers FRONT and REAR

• FRONT track the first element of the queue
• REAR track the last elements of the queue
• initially, set value of FRONT and REAR to -1
1. Enqueue Operation

• check if the queue is full

• for the first element, set value of FRONT to 0

• circularly increase the REAR index by 1 (i.e. if the rear reaches the end, next it would be at the
start of the queue)
• add the new element in the position pointed to by REAR
2. Dequeue Operation

• check if the queue is empty

• return the value pointed by FRONT
• circularly increase the FRONT index by 1
• for the last element, reset the values of FRONT and REAR to -1
However, the check for full queue has a new additional case:

• Case 1: FRONT = 0 && REAR == SIZE-1

• Case 2: FRONT = REAR+1
The second case happens when REAR starts from 0 due to circular increment and when its value is just
1 less than FRONT, the queue is full.
Applications of Circular Queue
• CPU scheduling
• Memory management
• Traffic Management
APPLICATION OF QUEUE:

1. Task Scheduling: Queues can be used to schedule tasks based on priority or the order in which
they were received.
2. Resource Allocation: Queues can be used to manage and allocate resources, such as printers or
CPU processing time.
3. Batch Processing: Queues can be used to handle batch processing jobs, such as data analysis or
image rendering.
4. Message Buffering: Queues can be used to buffer messages in communication systems, such as
message queues in messaging systems or buffers in computer networks.
5. Event Handling: Queues can be used to handle events in event-driven systems, such as GUI
applications or simulation systems.
6. Traffic Management: Queues can be used to manage traffic flow in transportation systems,
such as airport control systems or road networks.
7. Operating systems: Operating systems often use queues to manage processes and resources.
For example, a process scheduler might use a queue to manage the order in which processes are
executed.
 UNIT II

NON-LINEAR DATA STRUCTURES – TREES

Tree – Binary tree ADT-Tree -Traversals Algorithms –Search Tree – Binary Search Trees-AVL Trees
(Insertion, Deletion) –Splay Trees (Insertion, Deletion, Searching)- Red-Black Trees.

The data structure can be defined as the collection of elements and all the possible operations which
are required for those set of elements. Formally data structure can be defined as a data structure is a
set of domains D, a set of domains F and a set of axioms A. this triple (D,F,A) denotes the data
structure d.

NON-LINEAR DATA STRUCTURES:

The non-linear data structure is the kind of data structure in which the data may be arranged in
hierarchical fashion.

For example- Trees and graphs.

TREES:
A tree is a non-linear data structure that is used to represents hierarchical relationships
between individual data items. A tree is an ideal data structure for representing
hierarchical data. A tree can be theoretically defined as a finite set of one or more data
items (or nodes) such that:
1. There is a special node called the root of the tree.
2.Removing nodes (or data item) are partitioned into number of
mutually exclusive (i.e., Disjoined) subsets each of which is itself a tree
are called sub tree.

Ordinary and Binary Trees Terminology:

Tree: A tree is a finite set of one or more nodes such that, there is a specially designated
nodecalled root. The remaining nodes are partitioned into n>=0 disjoint sets T1, T2...Tn,
where each of these set is a tree T1…Tn are called the subtrees of the root.
Branch: Branch is the link between the parent and its child.
Leaf: A node with no children is called a leaf.
Subtree: A Subtree is a subset of a tree that is itself a tree.
Degree: The number of subtrees of a node is called the degree of the node. Hence nodes
that have degree zero are called leaf or terminal nodes. The other nodes are referred as
non- terminal nodes.
Children: The nodes branching from a particular node X are called children of X and
X is called its parent.
Siblings: Children of the same parent are said to be siblings.
Degree of tree: Degree of the tree is the maximum of the degree of the nodes in the
tree. Ancestors: Ancestors of a node are all the nodes along the path from root to that
node. Henceroot is ancestor of all the nodes in the tree.
Level: Level of a node is defined by letting root at level one. If a node is at level
L, thenits children are at level L + 1.
Height or depth: The height or depth of a tree is defined to be the maximum level
of anynode in the tree.
Climbing: The process of traversing the tree from the leaf to the root is called
climbing thetree.
Descending: The process of traversing the tree from the root to the leaf is called
descendingthe tree.

Fig 1.1: Terminologies of Tree

BINARY TREE
Binary tree has nodes each of which has no more than two child nodes.
Binary tree: A binary tree is a finite set of nodes that either is empty or consists of a
root andtwo disjoint binary trees called the left subtree and right subtree.
Left child: The node present to the left of the parent node is called the left child.
Right child: The node present to the right of the parent node is called the right child.
 Fig 1.2: Types of Binary Tree
Skewed Binary tree: If the new nodes in the tree are added only to one side of the
binary tree, then it is a skewed binary tree.
Strictly binary tree: If the binary tree has each node consisting of either two nodes or
no nodes at all, then it is called a strictly binary tree.
Complete binary tree: If all the nodes of a binary tree consist of two nodes each and
the nodes at the last level does not consist any nodes, then that type of binary tree is
called a complete binary tree. It can be observed that the maximum number of nodes on
level i of a binary tree is 2i - 1, where i ≥ 1. The maximum number of nodes in a binary
tree of depth k is2k – 1, where k ≥ 1.

PROPERTIES OF BINARY TREES

• The number of nodes n in a full binary tree, is at least n= 2h+1 and
at most n = 2h+1-1,where h is the height of the tree.
• A binary tree of n elements has n-1 edges.
• A binary tree of height h has at least h and at most 2h - 1 elements
• A tree consisting of only a root node has a height of 0.
• The number of leaf nodes in a perfect binary tree, is l= (n+1)/2. This
means that a perfectbinary tree with l leaves has n=2l-1 nodes.
• The number of internal nodes in a complete binary tree of n nodes is n/2.

REPRESENTATION OF BINARY TREES

There are two ways in which a binary tree can be represented. They are:
(i) Array representation of binary trees.
(ii) Linked representation of binary trees.
ARRAY REPRESENTATION OF BINARY TREES
When arrays are used to represent the binary trees, then an array of size 2k is
declared where, k is the depth of the tree. For example, if the depth of the binary tree is
3, then maximum 23 - 1 = 7 elements will be present in the node and hence the array
size will be 8. This is because the elements are stored from position one leaving the
position 0 vacant. But generally, an array of bigger size is declared so that later new
nodes can be added to the existing tree. The f following binary tree can be represented
using arrays as shown

50 30 40 10 20
Fig 1.3: Array Representation of Binary Tree

The root element is always stored in position 1. The left child of node i is stored in
position 2iand right child of node is stored in position 2i + 1. Hence the following
formulae can be used to identify the parent, left child and right child of a particular
node.
Parent( i ) = i / 2, if i ≠ 1. If i = 1 then i is the root node and root does not have parent.

Left child( i ) = 2i, if 2i ≤ n, where n is the maximum number of elements

in the tree. If 2i > n, then i has no left child.
Right child( i ) = 2i + 1, if 2i + 1 ≤ n. If 2i + 1 > n, then i has no right child.

The empty positions in the tree where no node is connected are represented in the array using -1,
indicating absence of a node. Using the formula, we can see that for a node 3, the parent is3/ 2 _1.
Referring to the array locations, we find that 50 is the parent of 40. The left child of node 3 is 2*3 _
6. But the position 6 consists of -1 indicating that the left child does not exist for the node 3. Hence
50 does not have a left child. The right child of node 3 is 2*3 + 1 _ 7. The position 7 in the array
consists of 20. Hence, 20 is the right child of 40.

LINKED REPRESENTATION OF BINARY TREES:

In linked representation of binary trees, instead of arrays, pointers are used to connect
the various nodes of the tree. Hence each node of the binary tree consists of three parts
namely, the info, left and right. The info part stores the data, left part stores the address
of the left child and the right part stores the address of the right child. Logically the
binary tree in linkedform can be represented as shown.

Fig 1.4: Linked Representation

The pointers storing NULL value indicates that there is no node attached to it.
Traversing through this type of representation is very easy. The left child of a particular
node can be accessed by following the left link of that node and the right child of a
particular node can beaccessed by following the right link of that node.

BINARY TREE ADT REPRESENTATIONS:

Abstract Data Type (ADT): An Abstract Data Type is a representation in which we
provide a specification of the instances as well as of the operations that are to be
performed. More precisely, An Abstract Data Type is a data type that is organized in
such a way that the specification of the object and the specification of the operation on
the object are separated from the representation of the object and the implementation of
the operation.
Abstract Datatype BinT(node *root)
{
Instances: Binary tree is a non-linear data structure which contains every node except
the leafnodes at most two child nodes.
Operations:
1. Insertion:
This operation is used to insert the nodes in the binary tree.
2. Deletion:
This operation is used to delete any node from the binary
tree. Note that if root node is removed the tree becomes
empty.
}
BINARY TREE TRAVERSALS
There are three standard ways of traversing a binary tree T with root R. They
are:
( i ) Preorder Traversal
(ii ) In order Traversal
 (iii) Post order Traversal

General outline of these three traversal methods can be given as follows:

Preorder Traversal:
(1) Process the root R.
(2) Traverse the left subtree of R in preorder.
(3) Traverse the right subtree of R in preorder.
In order Traversal:
(1) Traverse the left subtree of R in in order.
(2) Process the root R.
(3) Traverse the right subtree of R in in order.
Post order Traversal:
(1) Traverse the left subtree of R in post order.
(2) Traverse the right subtree of R in post order.
(3) Process the root R.

Observe that each algorithm contains the same three steps, and that the left subtree of R
is always traversed before the right subtree. The difference between the algorithms is
the time atwhich the root R is processed. The three algorithms are sometimes called,
respectively, the node-left-right (NLR) traversal, the left-node-right (LNR) traversal
and the left-right-node (LRN) traversal. Now we can present the detailed algorithm for
these traversal methods in both recursive method and iterative method.

Traversal algorithms using recursive approach Preorder

Traversal

In the preorder traversal the node element is visited first and then the right subtree of
the nodeand then the right subtree of the node is visited. Consider the following case
where we have 6nodes in the tree A, B, C, D, E, F. The traversal always starts from the
root of the tree. The node A is the root and hence it is visited first. The value at this
node is processed. The processing can be doing some computation over it or just
printing its value. Now we check if there exists any left child for this node if so apply
the preorder procedure on the left subtree. Now check if there is any right subtree for
the node A, the preorder procedure is applied on the right subtree.
Since there exists a left subtree for node A, B is now considered as the root of the left
subtree of A and preorder procedure is applied. Hence, we find that B is processed next
and then it is checked if B has a left subtree. This recursive method is continued until
all the nodes are visited.

Fig 1.5: Preorder Traversal

The algorithm for the above method is presented in the pseudo-code form below:
Algorithm
PREORDER( ROOT )
Temp = ROOT
If temp = NULL
Return
End if
Print info(temp)
If left(temp) ≠ NULL
PREORDER( left(temp))
End if
If right(temp) ≠ NULL
PREORDER(right(temp))
End if
End PREORDER

In order Traversal
In the In order traversal method, the left subtree of the current node is visited
first and then thecurrent node is processed and at last the right subtree of the current
node is visited. In the following example, the traversal starts with the root of the binary
tree. The node A is the root and it is checked if it has the left subtree. Then the inorder
traversal procedure is applied on the left subtree of the node A. Now we find that node
D does not have left subtree. Hence the node D is processed and then it is checked if
there is a right subtree for node D. Since there isno right subtree, the control returns
back to the previous function which was applied on B. Since left of B is already visited,
now B is processed. It is checked if B has the right subtree. If so apply the inroder
traversal method on the right subtree of the node B. This recursive procedure is followed
till all the nodes are visited.
 Fig 1.6 : In order Traversal

Algorithm

End if
If left(temp) ≠ NU
INORDER(left(tem
End if
Print info(temp)
If right(temp) ≠ NULL
INORDER(right(temp))
End if
End INORDER
Post order Traversal
In the post order traversal method, the left subtree is visited first, then the right
subtree and at last the current node is processed. In the following example, A is the root
node. Since A has the left subtree the post order traversal method is applied recursively
on the left subtree of A. Then when left subtree of A is completely is processed, the post
order traversal method is recursively applied on the right subtree of the node A. If right
subtree is completely processed, then the current node A is processed.
 Fig 1.7: Post order Traversal
ALGORITHM:

POSTORDER( ROOT )

Temp = ROOT

If temp=NULL

Return

End if

If left(temp) ≠NULL
 POSTORDER(left(temp))

End if

If right (temp) ≠NULL

POSTORDER(right(temp))

End if

Print info(temp)

End POSTORDER

BINARY SEARCH TREES

Binary Search Tree:
A Binary tree T is a Binary Search Tree (BST), if each node N of T hasthe
following property : The value at N is greater than every value in the left subtree of N
andis less than every value in the right subtree of N.
Consider the following tree. The root node 60 is greater than all the elements (54, 23,
58) in its left subtree and is less than all elements in its right subtree (78, 95).
Similarly, 54 isgreater than its left child 23 and lesser than its right child 58. Hence
each and every node in a binary search tree satisfies this property. The reason why we
go for a Binary Search tree is to improve the searching efficiency. The average case
time complexity of the search operationin a binary search tree is O( log n ).

Fig 1.10: Binary Search Tree

Consider the following list of numbers. A binary tree can be constructed using this list
of numbers, as shown.
38 14 8 23 18 20 56 45 82 70
Initially 38 is taken and placed as the root node. The next number 14 is taken and
compared with 38. As 14 is lesser than 38, it is placed as the left child of 38. Now the
third number 8 is taken and compared starting from the root node 38. Since is 8 is less
than 38 move towards left of 38. Now 8 is compared with 14, and as it is less that 14
and also 14 does not have any child, 8 is attached as the left child of 14. This process is
repeated until all the numbers are inserted into the tree. Remember that if a number to
be inserted is greater than a particular node element, then we move towards the right of
the node and start comparing again.

Fig 1.1: Construction of Binary Search Tree

Search Operation in a Binary Search Tree

The search operation on a BST returns the address of the node where the element is
found. The pointer LOC is used to store the address of the node where the element is
found. The pointer PAR is used to point to the parent of LOC. Initially the pointer
TEMP is made to point to the root node. Let us search for a value 70 in the following
BST. Let k = 70. The k value is compared with 38. As k is greater than 38, move to the
right child of 38, i.e., 56. k is greater than 56 and hence we move to the right child of
56, which is 82. Now since k is lesserthan 82, temp is moved to the left child of 82.
The k value matches here and hence theaddress of this node is stored in the pointer
LOC.
Every time the temp pointer is moved to the next node, the current node is made pointed
by PAR. Hence, we get the address of that node where the k value is found, and also the
address of its parent node though PAR.

Fig 1.11: Search Operation

 Algorithm
SEARCH( ROOT, k )
Temp = ROOT, par = NULL, loc = NULL
While temp ≠ NULL
If k = info(temp)
Loc = temp
Break
End if
If k < info(temp)
Par = temp
Temp = left(temp)
Else
Par = temp
Temp = right(temp)
End if
End while
End SEARCH

Insert Operation in a Binary Search Tree

The BST itself is constructed using the insert operation described below.
Consider the following list of numbers. A binary tree can be constructed using this
list ofnumbers using the insert operation, as shown.
39 14 8 23 18 20 56 45 82 70
Initially 38 is taken and placed as the root node. The next number 14 is taken and compared with 38.
As 14 is lesser than 38, it is placed as the left child of 38. Now the third number 8 is taken and
compared starting from the root node 38. Since is 8 is less than 38 move towards left of 38. Now 8 is
compared with 14, and as it is less than 14 and also 14 does not have any child, 8 is attached as the
left child of 14. This process is repeated until all the numbers are inserted into the tree. Remember
that if a number to be inserted is greater than a particular node element, then we move towards the
right of the node and start comparing again.
Fig 1.12: Insert Operation
 INSERT( ROOT, k )
Temp = ROOT, par = NULL
While temp ≠ NULL
If k = info(temp)
Print “Item already exists!”
Return
End if
If k < info(temp)
Par = temp
Temp = left(temp)
Else
Par = temp
Temp = right(temp)
End if
End while
Info(R) = k, left(R) = NULL, right(R) = NULL
If par = NULL
ROOT = R
End if
If k < info(par)
Left(par) = R
Else
Right(par) = R
End if
End INSERT

Delete Operation in a Binary Search Tree

The delete operation in a Binary search tree follows two cases. In case A, the node to be deleted has
no children or it has only one child. In case B, the node to be deleted has both left child and the right
child. It is taken care that, even after deletion the binary search tree property holds for all the nodes
in the BST.

Algorithm

DELETE( ROOT, k )
SEARCH( ROOT, k )
If Loc = NULL
Print “Item not
found”Return
End if
If right(Loc) ≠ NULL and left(Loc) ≠
NULLCASEB(Loc, par)
Else
CASEA(Loc,
par)End if
End Delete
Case A:
The search is operation is performed for the key value that has to be deleted. The search
operation, returns the address of the node to be deleted in the pointer LOC and its
parents’ address is returned in a pointer PAR. If the node to be deleted has no children
then, it is checked whether the node pointed by LOC is left child of PAR or is it the
right child of PAR. If it is the left child of PAR, then left of PAR is made NULL else
right of PAR is made NULL.
The sequence of steps followed for deleting 20 from the tree is as shown.

Fig 1.13: Delete Operation

If the node to be deleted has one child, then a new pointer CHILD is made to point to
the child of LOC. If LOC is left child of PAR then left of PAR is pointed to CHILD. If
LOC is right child of PAR then right of PAR is pointed to CHILD.
The sequence of steps for deleting the node 23 is shown.
 Fig 1.14: Delete Operation
Case B:
In this case, the node to be deleted has both the left child and the right child. Here we
introduce two new pointers SUC and PARSUC. The in order successor of the node to
be deleted is found out and is pointed by SUC and its parent node is pointed by the
PARSUC. Inthe following example the node to be deleted is 56 which has both the left
child and the right child. The in order successor of 56 is 70 and hence it is pointed by
SUC. Now the SUC replaces 56 as shown in the following sequence of steps.
Fig 1.14: All cases of Delete Operation
I
Child
Else
If left(temp) ≠
Child = left(temp)
Else
Child = right(temp)
End if
End if
If par ≠ NULL
If temp = left(par)
Left(par) = child
Else
Right(par) = child
End if
Else
ROOT = child
End if
End CASEA
CASEB( Loc, par )
Temp = right(Loc)

Save = Loc
While left(temp) ≠ NULL
Save = temp
Temp = left(temp)
End while
Suc = temp
Parsuc = save
CASEA( suc, parsuc)
If par ≠ NULL
If Loc = left(par)
Left(par) = suc
Else
Right(par) = suc
End if
Else
ROOT = suc
End if
Left(suc) = left(Loc)
Right(suc) = right(Loc)
End CAS
HEIGHT BALANCED TREES ( AVL TREES )
The Height balanced trees were developed by researchers Adelson-Velskii and Landis.
Hence these trees are also called AVL trees. Height balancing attempts to maintain the
balance factor of the nodes within limit.
Height of the tree: Height of a tree is the number of nodes visited in traversing a
branch that leads to a leaf node at the deepest level of the tree.
Balance factor: The balance factor of a node is defined to be the difference
between the height of the node’s left sub tree and the height of the node’s right sub
tree.
Consider the following tree. The left height of the tree is 5, because there are 5 nodes
(45, 40, 35, 37 and 36) visited in traversing the branch that leads to a leaf node at the
deepest level of this tree.
Balance factor = height of left subtree – height of the right subtree
In the following tree the balance factor for each and every node is calculated and shown.
For example, the balance factor of node 35 is (0 – 2 ) = - 2.
The tree which is shown below is a binary search tree. The purpose of going for a binary
search tree is to make the searching efficient. But when the elements are added to the
binary search tree in such a way that one side of the tree becomes heavier, then the
searching becomes inefficient. The very purpose of going for a binary search tree is not
served. Hence we try to adjust this unbalanced tree to have nodes equally distributed on
both sides. This is achieved by rotating the tree using standard algorithms called the
AVL rotations. After applying AVL rotation, the tree becomes balanced and is called
the AVL tree or the height balanced tree.

Fig 2.4: Binary Tree

The tree is said to be balanced if each node consists of a balance factor either -1 or
0 or 1.If even one node has a balance factor deviated from these values, then the
tree is said to be unbalanced. There are four types of rotations. They are:
1. Left-of-Left rotation.
2. Right-of-Right rotation.
3. Right-of-Left rotation.
4. Left-of-Right rotation.
Left-of-Left Rotation:
Consider the following tree. Initially the tree is balanced. Now a new node 5 is added.
This addition of the new node makes the tree unbalanced as the root node has a balance
factor 2. Since this is the node which is disturbing the balance, it is called the pivot node
for our rotation. It is observed that the new node was added as the left child to the left
subtree of the pivot node. The pointers P and Q are created and made to point to the
proper nodes as described by the algorithm. Then the next two steps rotate the tree. The
last two steps in the algorithm calculates the new balance factors for the nodes and is
seen that the tree has become a balanced tree.
 Fig 2.5: Left-of-Left Rotation

LEFT-OF-LEFT(pivot)

P = left(pivot)
Q = right(P)
Root = P
Right(P) = pivot
Left(pivot) = Q
End LEFT-OF-LEFT
Right-of- Right Rotation:
In this case, the pivot element is fixed as before. The new node is found to be added as the right child
to the right subtree of the pivot element. The first two steps in the algorithm sets the pointer P and Q

to the correct positions. The next two steps rotate the tree to balance it. The last two steps calculate
the new balance factor of the nodes

Fig 2.6: Right-of-Right Rotation

Q = left(P)
Root = P
Left(P) = pivot
Right(pivot) = Q
End RIGHT-OF-RIGHT

Right-of-Left Rotation:
In this following tree, a new node 19 is added. This is added as the right child to the left
subtree of the pivot node. The node 20 fixed as the pivot node, as it disturbs the balance
of the tree. In the first two steps the pointers P and Q are positioned. In the next four
steps, tree is rotated. In the remaining steps, the new balance factors are calculated.
 Fig 2.7: Right-of-Left Rotation

Q
Root = Q
Left(Q) = P
Right(Q) = Pivot
Left(pivot) = right(Q)
Right(P) = left(Q)
End RIGHT-OF-LEFT

Left-of-Right:
In the following tree, a new node 21 is added. The tree becomes unbalanced and
the node 20 is the node which has a deviated balance factor and hence fixed as the pivot
node. In the first two steps of the algorithm, the pointers P and Q are positioned. In the
next 4 steps the tree is rotated to make it balanced. The remaining steps calculate the
new balance factors for the nodes in the tree.
 Fig 2.8: Left-of-Right Rotation

LEFT-OF-RIGHT(pivot)
P=
right(pivo
t)Q =
left(P)
Root= Q
Right(Q)
=P
Left(Q) =
Pivot
Right(pivot) =
left(Q)Left(P) =
right(Q)
End LEFT-OF-RIGHT
Red-Black Tree
STRUCTURAL PROPERTIES

A red-black tree is a binary search tree whose height is logarithmic in the number of keys
stored.

1. Every node is colored red or black.(Colors are only examined during insertion and deletion)

2. Every “leaf” (the sentinel) is colored black.

3. Both children of a red node are black.

4. Every simple path from a child of node X to a leaf has the same number of black nodes.

This number is known as the black-height of X(bh(X)).These are not stored.

Example:

=red =black

40
3

20 100
2 3

10 30 60 120
1 1 2 2

0 0 0 0 50 80 110 140
1 2 1 2
0 0 0 0
70 90 130 160
1 1 1 1
0 0 0 0 0 0
150 170
1 1

0 0 0 0
Observations:

1. A red-black tree with n internal nodes(“keys”)has height atmost 2lg(n+1).

2. If a node X is not a leaf and its sibling is a leaf, then X must be red.

3. There may be many ways to color a binary search tree to make it a red-black tree.

4. If the root is colored red, then it may be switched to black without violating structural properties.
 2

ROTATIONS

Technique for rebalancing in most balanced binary search tree schemes. Takes(1)time.

A C

a b c d

Left rotation at B Right rotation at B

(AKArotatingedgeBC (AKArotatingedgeBA
) )

C A

B B

d a
A C

c b

a b c d
 3
INSERTION

1. Startwithunbalancedinsertofa “data leaf”(bothchildrenare thesentinel).

2. Color of new node is .

3. Mayviolatestructuralproperty3.Leadstothreecases,alongwithsymmetricversions.

Thex pointerpointsatared node whoseparentmightalso be red.

Case 1:

= red =black
k+1 k+1

B B
k
x k+1

C A C
A k k
k
k
A’
x A’
k c d k c d

a b
a b

Case 2:

=red = black
k+1 k+1

C C
k k

A D B D
k k-1 k k-1

x B x A
k k
a d e c d e

b c a b
 4
Case 3:

=red = black
k+1 k+1

C B
k k

B D A C
k k-1 k k

x A D
k k-1
c d e a b c

a b d e

Example 1:
=red =black

40

20 60

10 30 50 70

Insert15
40 40

20 60 1 x 20 60

10 30 50 70 10 30 50 70

x 15 15
 5
Insert13
40 40

20 60 2 20 60

10 30 50 70 10 30 50 70

15 13

x 13 x 15

40

3 20 60

13 30 50 70

10 15

Insert75
40 40

20 60 1 20 x 60

13 30 50 70 13 30 50 70

10 15 x 75 10 15 75

Insert14
40 40

20 60 1 20 60

13 30 50 70 x 13 30 50 70

10 15 75 10 15 75

x 14 14

x 40 Resetto black

1 20 60

13 30 50 70

10 15 75

14
 6
Example 2:
140

40 160

20 100 150 170

10 30 60 120

50 80 110 130

70 90

Insert75
140

40 160

20 100 150 170

10 30 60 120

50 80 110 130

70 90

75
x
 7
140

40 160

20 100 150 170

1
10 30 60 120

50 x 80 110 130

70 90

75

140

40 160

20 x 100 150 170

1
10 30 60 120

50 80 110 130

70 90

75
 8
140

100 160

x 40 120 150 170

2
20 60 110 130

10 30 50 80

70 90

75

100

40 140

3 20 60 120 160

10 30 50 80 110 130 150 170

70 90

75

DELETION

Start with one of the unbalanced deletion cases:

1. Deleted node is a “data leaf”.

a. Splice around to sentinel.

b. Colorofdeletednode?

Red  Done

BlackSettemporary“doubleblack”pointer(x)atsentinel.
Determine which of four rebalancing cases
applies.

2. Deleted node is parent of one “data leaf”.

a. Splice around to “data leaf”

b. Color of deleted node?

Red  Not possible

Black “data leaf” must be red. Change its color to black.

 9
3. Node with key-to-delete is parent of two “data nodes”.

a. Steal key and data from successor(but not the color).

b. Delete success or using the appropriate one of the previous two cases.

Case 1:

=red =black

k+1 k+1

B D
k k

x A D B E
k-2 k k k-1

C E x A C
k-1 k-1 k-2 k-1
a b e f

c d e f a b c d

Case 2:

=red=0 =black=1 =either

k+color(B) k+color(B)

B x B
k k-1

x A D A D
k-2 k-1 k-2 k-1

C E C E
k-2 k-2 k-2 k-2
a b a b

c d e f c d e f
 10
Case 3:

=red=0 =black= 1 =either

k+color(B) k+color(B)

B B
k k

x A D x A C
k-2 k-1 k-2 k-1

C E D
k-1 k-2 k-1
a b a b c
E
k-2
c d e f d

e f

Case 4:

=red=0 =black=1 =either

k+color(B)+color(C) k+color(D)+color(C)

B D
k+color(C) k+color(C)

x A D B E
k-2 k-1 k-1 k-1
+color(C) +color(C) +color(C) +color(C)
C E A C
k-1 k-1 k-2 k-1
+color(C) +color(C)
a b e f

c d e f a b c d

80

40 120

20 60 100 140

10 30 50 70 90 110 130 150

Example 3:
 11
Delete50
80

40 120

20 60 100 140

10 30 x 70 90 110 130 150

80

40 120
2

20 x 60 100 140

10 30 70 90 110 130 150

80

2 x 40 120

20 60 100 140

10 30 70 90 110 130 150

x
80

2 40 120

20 60 100 140

10 30 70 90 110 130 150

If x reaches the root, then done. Only place in tree where this happens.

Delete60
 12
80

40 120

20 70 100 140

10 30 90 110 130 150

Delete70
80 80

40 120 1 20 120

20 x 100 140 10 40 100 140

x
10 30 90 110 130 150 30 90 110 130 150

2 80

20 120

10x 40 100 140

30 90 110 130 150

If xreachesa red node,thenchangecolortoblackanddone.

Delete10
80 80

20 120 3 20 120

x 40 100 140 x 30 100 140

30 90 110 130 150 40 150

90 110 130

80

4 30 120

20 40 100 140

90 110 130 150

Delete40
 13

80 80

30 120 2 x 30 120

x
20 100 140 20 100 140

90 110 130 150 90 110 130 150

120 120

1 80 140 2 x 80 140

x 30 100 130 150 30 100 130 150

20 90 110 20 90 110

Delete120
130 130

80 140 2 80 x 140
x
30 100 150 30 100 150

20 90 110 20 90 110

130 100

3 4
100 x 140 80 130

80 110 150 30 90 110 140

30 90 20 150

20

110 110

80 130 4 80 140

x 130
30 90 140 30 90 150

20 150 20
Delete100
 14

SPLAY TREE
A splay tree is a binary search tree in which restructuring is done using a scheme called splay. The splay is
a heuristic method which moves a given vertex v to the root of the splay tree using a sequence of
rotations.

Introduction

Splay Tree is not strictly balanced like the AVL Tree but is intended to work faster for cache applications.
Splaying is an additional operation carried out during the insert, delete, and search operations. The
recently accessed node becomes the root and the tree changes for even read-only search operations.

Splay Tree Representation

• Roughly balanced: Rotations are used to bring the recently accessed node to the root. This helps
the tree be roughly balanced.
• Zig Rotation: Right rotation.
• Zag Rotation: Left rotation.

When we use BSTs for searching the data, the time complexity in an average case is O(log2N). This is
because the average case height of a binary tree is O(log2N). However, the worst case can be a left or a
right-skewed tree i.e. a linear tree. Then the worst-case time complexity of the operations like searching,
insertion, and deletion becomes O(N).

However, what if the trees are made self-balancing such that they never form skewed structures and the
height always remains O(log2N)? This is done in AVL trees and Red-Black trees. These are self-balancing
BSTs; hence, the worst-case time complexity of searching, insertion and deletion is O(log2N).

However, the question is, can we do better than this? The answer is yes. In some practical scenarios, we
can do better than AVL and Red-Black Trees. How? Using splay trees.

The main idea of splay trees is based on the “most frequently used elements”. Basically, a splay tree in
data structure, involves all the operations of a normal Binary Search Tree i.e. searching, insertion,
deletion, etc. However, it also includes one special operation i.e. always performed and it is
called splaying. The idea is to bring the more frequently used elements closer to the root of the BST so
that if they are searched again, they can be found more quickly as compared to the less frequently used
elements.

Consider the BST shown below.

Let us say we want to search for 8. So, we start from the root node. Since the value at the root node is 10
and we are searching for 8 i.e. a smaller element than the current node, we will move toward the left. So,
we go to the next node and we found 8.
 15

This is a normal search operation in BST. However, we will do a little more than this in the splay tree. We
will perform splaying i.e. 8 will now become the root node of the tree. How? We can do this with some
rotations. There are 6 different types of rotations that can be performed in a splay tree. These are as
follows.

• Zig Rotation (Right Rotation)

• Zig Zig Rotation (2 Zig Rotations or 2 right rotations)

• Zag Rotation (Left Rotation)

• Zag Zag Rotation (2 Zag rotations or 2 left rotations)

• Zig Zag Rotation (Right-Left Rotation i.e. first do Zig then Zag)

• Zag Zig Rotation (Left-Right Rotation i.e. first do Zag then Zig)

Let us study these rotations one by one.

Zig Rotation or Right Rotation

Consider the tree shown below.

In this rotation, we move every node to 1 position towards its right. This rotation is used in the case when
the element that we are searching for is either present in the root node of the BST or it is present in the
left child of the root node.

Consider that we are searching for node 9. This means that we are searching for the left child of the root
node. So, we can perform zig rotation.

So, the steps for searching node 9 are the same as we perform the search in BST and have already been
discussed. Now, since this is the zig rotation i.e. we need to rotate each element 1 position to its right. This
rotation is shown below.
 16

So, every element has to go 1 position to its right. Now, we can imagine every element going to 1 position
to its right and we imagine that 9 will become the root node and 11 will; be its right child and the left
child will be 7. What about node 10?

So, node 10 is the right child of node 9 before rotation. So, after rotation, it will remain in the right subtree
of node 9. However, it will now become the left child of node 11 as shown below.

Zig Zig Rotation or Right-Right Rotation

In this rotation, 2 right rotations are performed one after another. This is used in the case when the
element that we are searching for is neither the root node nor the left child of the root node but is present
below in the left subtree of the root node. This means that the node has both, parent and grandparent.
Consider the tree shown below.
 17

So, if we are searching for node 3, we find it at the last level. Now, we will perform the 1st right rotation.

After one rotation, the tree is shown below. Now, we perform the second rotation.
 18

So, after 2 right rotations, node 3 is now the root node of the tree.

Zag Rotation or Left Rotation

Again, consider the tree shown below.

The Zag rotation or the left rotation is performed when the element that we are searching for is either the
root node or the right child of the root node.

So, consider that we are searching for node 13. Since it is the right child of the root node, we perform the
zig rotation. Every element will rotate and reach 1 position to its current left. This is shown below.
 19

So, since after rotation, 14 has to become the right child of 13 and 12 was present as its left child, 12 will
remain in the left subtree but becomes the right child of node 11. Node 13 has become the root node now.

Zag Zag Rotation or Left-Left Rotation

Here, we perform 2 left rotations. Again, it is done when we are searching for an element i.e., not the root
or the right child of the root but present in the right subtree and has both parent and grandparent. So,
consider the tree shown below.

If we are searching 7, the result of the zag zag rotation is shown below.
 20

So, node 7 has now become the root node of the tree.

Zig Zag Rotation or Right Left Rotation

This is a sequence of zig rotations which are then followed by a sequence of zag rotations. The zig-zag
rotation is used when the parent node and the grandparent node of a node are in LR or RL relationship
with each other. Consider the tree shown below.
 21

If we want to search 5, then the parent and grandparent are in an RL relationship with each other. So, we
first perform the Right rotation i.e. Zig rotation about node 6, and then the left rotation i.e. Zag rotation
about the root node i.e. node 4, thus completing the Zig Zag rotation. This is shown below.

Finally, we can see that 5 is the root node of the tree. So, this is Zig Zag rotation.

Zag Zig Rotation or Left-Right Rotation

This rotation is the same as the zig-zag rotation. The only difference is that the left rotation happens first
and then the right rotation. Consider the tree shown below.

So, here if we want to search 5, the zag zig rotation is shown below.
 22

So, we can see that node 5 is at the root of the tree. This is Zag Zig Rotation.

Now that we have studied the splay trees, let us implement these rotations and other BST operations of a
splay tree in the program shown below.
23
UNIT - III DIVIDE AND CONQUER STRATEGY AND GREEDYSTRATEGY
Divide and Conquer Strategy: Quick Sort-Multiplication of large integers and Strassen's Matrix
Multiplication. Greedy Technique: Prim’s Algorithm - Kruskal’s Algorithm- Dijkistra’s
Algorithm - Huffman Trees and Code.
Divide and Conquer strategy:
Divide:
❖ Divide the array into two sub arrays by picking any key value in the array called pivot
element.
❖ Each element in the left sub array is less than or equal to pivot element.
Each element in the right sub-tree is greater than the pivot element

Conquer:
❖ Recursively divide the sub-arrays until the array will contain only one element.
Combine:
❖ Combine all the sorted elements in a group to form a list of sorted elements.
The following are some standard algorithms that follow Divide and Conquer algorithm.
1. Quicksort is a sorting algorithm. The algorithm 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 sub-arrays on the left and right of the pivot element.

2. 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.

3. 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.

QUIICKSORT:
Quick sort is sorting algorithm that uses divide and conquer
methodology.In this method, division is dynamically carried out.
SORTING:
Sorting is a mechanism to arranging the unsorted elements in either ascending or descending
order.
There are two kinds of sorting.
1. InternalSort–Utilizes internal memory
2. ExternalSort–Utilizes external memory or secondary storage devices.

Algorithm:
Step(1):Let take the first element as the‘pivot”element.
Step(2):Set low index of an array to “i”.Set
high index of an array to“j”.
Step(3):if(A[i]<pivot)=>then increment“i”
Step(4):if(A[j]>pivot)=>then decrement“j”.
Step(5):if‘i”cant increment and‘j”cant decrement,then swap(A[i],A[j])
Step(6):if‘i’and‘j’are crossed(or)if(A[j]<pivot)=>then swap(A[j],pivot)

Example:
Consider the list of elements– 50,30, 10, 90,80, 20,40, 70.

Step:1

i j
50 30 10 90 80 20 40 70
pivot

Step:2

i j
50 30 10 90 80 20 40 70
pivot
We will increment‘i’,if(A[i]<pivot),we will continue to increment‘i’until the element the
element of A[i] is greater than pivot.
Step:3

i j
50 30 10 90 80 20 40 70
pivot
Increment‘i’as A[i]<pivot

Step:4

i j
50 30 10 90 80 20 40 70
pivot
A[i]>pivot,So stop incrementing‘i’

Step:5
A[j]>pivot,So decrement‘j’

i j
50 30 10 90 80 20 40 70
pivot

Step:5
A[j]<pivot,So stop decrementing‘j’
 i j
50 30 10 90 80 20 40 70
pivot

Step:6
‘i’cant increment and‘j’cant decrement.Then swap(A[i],A[j])

i j
50 30 10 40 80 20 90 70
pivot

Step:7
A[i]<pivot=>Increment‘i’

i j
50 30 10 40 80 20 90 70
pivot

Step:8
A[i]>pivot=>Stop incrementing‘i’

i j
50 30 10 40 80 20 90 70
pivot

Step:9
A[j]>pivot=>Decrement‘j’

i j
50 30 10 40 80 20 90 70
pivot

Step:10
A[j]<pivot=>Stop Decrementing‘j’

i j
50 30 10 40 80 20 90 70
pivot

Step:11
‘i’cant increment and‘j’cant decrement.Then swap(A[i],A[j])
 i j
50 30 10 40 20 80 90 70
pivot

Step:12
A[i]<pivot=>Increment‘i’

i, j
50 30 10 40 20 80 90 70
pivot

Step:13
A[i]>pivot=>Stop Incrementing‘i’
i, j
50 30 10 40 20 80 90 70
pivot

Step:14
A[j]>pivot=> Decrement‘j’

j i
50 30 10 40 20 80 90 70
pivot

Step:15
A[j]<pivot=>Stop Decrementing‘j’

j i
50 30 10 40 20 80 90 70
pivot
Step:16
‘i’and‘j’are crossed andA[j]<pivot=>swap(A[j],pivot)
i j

20 30 10 40 50 80 90 70
pivot
Left subarray Right SubArray

MERGE SORT:
Merge Sort is a Divide and Conquer algorithm. It divides input array in two halves, calls
itself for the two halves and then merges the two sorted halves. The merge() function is used for
merging two halves
A Algorithm:
A
step 1: start
step 2: declare array and left, right, mid variable

step 3: perform merge function.

if left > right
return
mid= (left+right)/2
mergesort(array, left, mid)
mergesort(array, mid+1, right)
merge(array, left, mid, right)

step 4: Stop

PROGRAM:
def merge(a,b):c=[]
while len(a) != 0 and len(b) != 0:
ifa[0]<b[0]:
c.append(a[0])
a.remove(a[0])else:
c.append(b[0])
b.remove(b[0])iflen(a)==0:
c=c+belse:
c=c+a
returnc
defdivide(x):
if len(x) == 0 or len(x) == 1:return x
else:
middle=len(x)//2
 a = divide(x[:middle])b = divide(x[middle:])
returnmerge(a,b)

x=[89,13,67,34,90,100,103,167,25]

Sorting SpaceCom
Method Worst Case AverageCase Best Case plexity

QuickSort n(n+3)/2= O(n2) O(nlog n) O(nlog n) Constant

MergeSort O(nlog n) O(nlog n) O(nlog n) Depends

Multiplication of large Integers:

There are two ways to perform large integer multiplication using divide and conquer.
1. Dumb method – does not improve the running time.
2. Clever approach – performs better then the traditional approach for integer
multiplication.

Dumb Approach:

Let us represent number D as D = dn-1dn-2. . . d2d1d0. Each digit di is the ith least significant digit
in number D. Value of each position is given by,
d0 = 100 position
d1 = 101 position
d2 = 102 position
.

dn – 1 = 10n – 1 position.
According to position value,

45 = 4*101 + 5*100
23 = 2*101 + 3*100
For any real values a, b, c and d,

(a + b)*(c + d) = (a*c + a*d + b*c + b*d)

So, 45 * 23 = (4*101 + 5*100) * (2*101 + 3*100)

= (4 *2) *102 + (4*3 + 5*2) *101 + (5*3) *100
= 800 + 220 + 15

= 1035

Let’s derive formula to multiply two numbers of two digits each. Consider C = A * B. If we
consider A = a1a0 and B = b1b0, then
C=a1b1102+ a1 b0101+ a0 b1101+ a0 b0100
C= a1b1102+ (a1 b0+ a0 b1 )101+ a0 b0100
C = A * B = c2102 + c1101 + c0100
Where,
c2 = a1 * b1
c1 = a1* b0 + a0* b1
c0 = a0 * b0
Generalization:
If size of integer is n digit, then we can generalize multiplication as,

C = c210n + c110n/2 + c0

Example: Multiply 2345 with 678 using divide and conquer approach.
Solution:
Size of both operands must be even, so pad zero to the multiplier.

A = 2345 and B = 0678

A = a1a0 = 2345, hence a1 = 23 and a0 = 45

B = b1b0 = 0678, hence b1 = 06 and b0 = 78
C = A * B =c2104 + c1102 + c0100
c2 = a1 * b1
= 23 * 06

= 138

c1 = a1*b0 + a0*b1
= (23*78) + (45 * 06)

= 2064

c0 = a0 * b0
=(45 * 78)

= 3510

C = c2102 + c1101 + c0100

= 138*104 + 2064*102 + 3510
= 15, 89, 910

Clever Approach:

Previous DC approach does four multiplications. Let’s reformulate it to reduce numbers of

multiplications to three.

First approach:
According to dumb approach,

c2 = a1 * b1
c1 = a1*b0 + a0*b1 …(1)
c0 = a0*b0
Second approach:
Let us rewrite c1 as,
c1 = (a1 + a0) * (b1 + b0) – (c2 + c0)
= (a1b1 + a1b0 + a0b1 + a0b0) – (a1b1 + a0b0)
= a1*b0 + a0*b1 …(2)
Equation (1) and Equation (2) are the same, but the second approach of computing c1 involves
only one multiplication rather than two as it requires in the first approach.

For A = a1a0 = 2345,

hence, a1 = 23 and a0 = 45 and
B = b1b0 = 0678,
hence, b1 = 06 and b0 = 78
c2 = a1 * b1
= 23 * 06

= 138

c0 = a0*b0
= (45 * 78)

= 3510

c1 = (a1 + a0) * (b1 + b0) – (c2 + c0)

= (23 + 45) * (06 + 78) – (138 + 3510)

= 68 * 84 – 3648

= 2064

It is same as c1 = (a1*b0 + a0*b1) of dumb multiplication approach, but does only one
multiplication rather than two.
C = c2 * 104 + c1 * 102 + c0
= 1380000 + 206400 + 3510 = 15, 89, 910

This formulation leads to same result, with three multiplications only.

Strassen's Matrix Multiplication:

Strassen suggested a divide and conquer strategy-based matrix multiplication technique that
requires fewer multiplications than the traditional method. The multiplication operation is
defined as follows using Strassen’s method:

C11 = P + S – T + V
C12 = R + T
C21 = Q + S
C22 = P + R – Q + U
Where,

P = (A11 + A22) * (B11 + B22)

Q = (A21 + A22) * B11
R = A11 * (B12 – B22)
S = A22 * (B21 – B11)
T = (A11 + A12) * B22
U = (A21 – A11) * (B11 + B12)
V = (A12 – A22) * (B21 + B22)
Example: Multiply the below two matrix using divide and conquer approach:

A11= 1 A12 =3 A21 =5 A22 =7

B11 =8 B12 = 4 B21 =6 B22 =2
P = (A11 + A22) * (B11 + B22)
P=(1+7)*(8+2)
P=80
Q = (A21 + A22) * B11
Q=(5+7)*8
Q=96
R = A11 * (B12 – B22)
R=1*(4-2)
R=2
S = A22 * (B21 – B11)
S=7*(6-8)
S=-14
T = (A11 + A12) * B22
T=(1+3)*2
T=8
U = (A21 – A11) * (B11 + B12)
U=(5-1)*(8+4)
U=48
V = (A12 – A22) * (B21 + B22)
V=(3-7)*(6+2)
V=-32
C11 = P + S – T + V
C11 =80-14-8-32
C11 =26
C12 = R + T
C12 =2+8
C12 =10
C21 = Q + S
C21 =96-14
C21 =82
C22 = P + R – Q + U
C22 =80+2-96+48
C22 =34

Normal Matrix Multiplication

Greedy Approach:
A greedy algorithm is an approach for solving a problem by selecting the best option
available at the moment. It doesn't worry whether the current best result will bring the overall
optimal result. Used to solve an optimization problem.

The general structure of a greedy algorithm

Characteristic components of greedy algorithm:

1. The feasible solution: A subset of given inputs that satisfies all specified
constraints of a problem is known as a “feasible solution”.
 2. Optimal solution: The feasible solution that achieves the desired extremum is
called an “optimal solution”. In other words, the feasible solution that either
minimizes or maximizes the objective function specified in a problem is known as
an “optimal solution”
3. Objective Function: This can be defined as the function that needs to be either
maximized or minimized.
Greedy approach is used to solve many problems, such as
• Finding the shortest path between two vertices using Dijkstra’s algorithm.
• Finding the minimal spanning tree in a graph using Prim’s /Kruskal’s algorithm.
• Finding an optimal solution (Activity selection, Fractional Knapsack, Job
Sequencing, Huffman Coding).
Huffman Coding:
Huffman coding is a lossless data compression algorithm.Huffman Coding is a
technique of compressing data to reduce its size without losing any of the details. It was first
developed by David Huffman.

How Huffman Coding works?

Suppose the string below is to be sent over a network.

Each character occupies 8 bits. There are a total of 15 characters in the above string. Thus, a
total of 8 * 15 = 120 bits are required to send this string.
Using the Huffman Coding technique, we can compress the string to a smaller size.

Huffman coding first creates a tree using the frequencies of the character and then generates
code for each character.

Once the data is encoded, it has to be decoded. Decoding is done using the same tree.

Huffman Coding prevents any ambiguity in the decoding process using the concept of prefix
code ie. a code associated with a character should not be present in the prefix of any other code.
The tree created above helps in maintaining the property.
Huffman coding is done with the help of the following steps.

1. Calculate the frequency of each character in the string.

2. Sort the characters in increasing order of the frequency.

3. Make each unique character as a leaf node.

4. Create an empty node z. Assign the minimum frequency to the left child of z and assign
the second minimum frequency to the right child of z. Set the value of the z as the sum
of the above two minimum frequencies.

5. Remove these two minimum frequencies and add the sum into the list of frequencies (*
denote the internal nodes in the figure above).
6. Insert node z into the tree.
7. Repeat steps 3 to 5 for all the characters
 8. For each non-leaf node, assign 0 to the left edge and 1 to the right edge.

Huffman code for given String:

Shortest path algorithms:

• Shortest path problem is a problem of finding the shortest path(s) between vertices of a
given graph.
• Shortest path between two vertices is a path that has the least cost as compared to all
other existing paths.
Applications-
Shortest path algorithms have a wide range of applications such as in-
• Google Maps
• Road Networks
• Logistics Research
Types of Shortest Path Problem-
1. Single-source shortest path problem
2. All pairs shortest path problem
Single-Source Shortest Path Problem-
• It is a shortest path problem where the shortest path from a given source vertex to all
other remaining vertices is computed.
• Dijkstra’s Algorithm and Bellman Ford Algorithm are the famous algorithms used for
solving single-source shortest path problem.
All Pairs Shortest Path Problem-
• It is a shortest path problem where the shortest path between every pair of vertices is
computed.
• Floyd-Warshall Algorithm and Johnson’s Algorithm are the famous algorithms used for
solving All pairs shortest path problem.
Dijkstra’s Algorithm-
• Dijkstra Algorithm is a very famous greedy algorithm.
• It is used for solving the single source shortest path problem.
• It computes the shortest path from one particular source node to all other remaining
nodes of the graph.
Step by step process of algorithm implementation:
1. The very first step is to mark all nodes as unvisited,
2. Mark the picked starting node with a current distance of 0 and the rest nodes with
infinity,
3. Now, fix the starting node as the current node,
4. For the current node, analyse all of its unvisited neighbours and measure their distances
by adding the current distance of the current node to the weight of the edge that connects
the neighbour node and current node,
5. Compare the recently measured distance with the current distance assigned to the
neighbouring node and make it as the new current distance of the neighbouring node,
6. After that, consider all of the unvisited neighbours of the current node, mark the current
node as visited,
7. If the destination node has been marked visited then stop, an algorithm has ended, and
8. Else, choose the unvisited node that is marked with the least distance, fix it as the new
current node, and repeat the process again from step 4.
Formula to find the Distance :
If(d(x) + c(x, y) < d(y) )
d(x, y) = d(x) + c(x, y)
Example:
Write Dijktra’s algorithm to find the shortest path problem and analyse its time
complexity.Apply the algorithm to find shortest path for the following graph.

Starting vertex:0
Mark vertex 0 as visited
Initial table:
0 1 2 3 4 5 6 7 8
0 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞
Adjacency vertex for 0 is 1 and 7, so find distance between(0,1)and (0,7)
Distance (0,1)
d(x, y) = d(x) + c(x, y) < d(y)
d(0, 1) = d(0) + c(0, 1) < d(1)
= (0 + 4) < ∞
= 4 < ∞ update the table V(0,1)=4
D(0,1)=4
Distance (0,7)
d(x, y) = d(x) + c(x, y) < d(y)
= (0 + 8) < ∞
= 8 < ∞ update the table V(0,7)=8
Now the altered table:
0 1 2 3 4 5 6 7 8
0 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞
1 4 ∞ ∞ ∞ ∞ ∞ 8 ∞
Least value is 4 (vertex 1 is selected)

From the table the vertex 1 and 7, vertex 1 has least cost so we can select vertex 1. Mark 1
vertex as visited.
Adjacency vertex for 1 is 0, 2 and 7. 0 is already visited so find the distance between(1,2)and
(1,7)
Distance (1,2)
d(x, y) = d(x) + c(x, y) < d(y)
d(1,2)=d(1)+c(1,2)<d(2)
= (4 + 8) < ∞
= 12 < ∞ update the table V(1,2)=12
Distance (1,7)
d(x, y) = d(x) + c(x, y) < d(y)
d(1,7)=d(1)+c(1,7)<d(7)
= (4 + 11) < 8
= 15 < 8 table is not updated so V(1,7)=8
Now the altered table:
0 1 2 3 4 5 6 7 8
0 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞
1 4 ∞ ∞ ∞ ∞ ∞ 8 ∞
Least values is 8(vertex 7 is selected)
7 12 ∞ ∞ ∞ ∞ 8 ∞
From the table the vertex 2 and 7, vertex 7 has least cost so we can select vertex 7.Mark vertex
7 as visited.
Adjacency vertex for 7 is 0,1,6 and 8. 0 and 1 is already visited, so find distance between
(7,6)and (7,8)
Distance (7,8)
d(x, y) = d(x) + c(x, y) < d(y)
d(7,8)=d(7)+c(7,8)<d(8)
= (8 + 7) < ∞
= 15 < ∞ update the table V(7,8)=15
Distance (7,6)
d(x, y) = d(x) + c(x, y) < d(y)
d(7,6)=d(7)+c(7,6)<d(6)
= (8 + 1) < ∞
= 9 < ∞ update the table V(7,6)=9
Now the altered table:
0 1 2 3 4 5 6 7 8
0 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞
1 4 ∞ ∞ ∞ ∞ ∞ 8 ∞
7 12 ∞ ∞ ∞ ∞ 8 ∞
6 12 ∞ ∞ ∞ 9 15 Least value is 9(vertex 6 is selected)

From the table the vertex 2 , 6 and 8, vertex 6 has least cost so we can select vertex 6.Mark
vertex 6 as visited.
Adjacency vertex for 6 is 7,8 and 5. 7 is already visited, so find distance between (6,8)and (6,5)
Distance (6,8)
d(x, y) = d(x) + c(x, y) < d(y)
d(6,8)=d(6)+c(6,8)<d(8)
= (9 + 15) < 15
= 24 < 15 table is not updated V(6,8)=15
Distance (6,5)
d(x, y) = d(x) + c(x, y) < d(y)
d(6,5)=d(6)+c(6,5)<d(5)
= (9 + 2) < ∞
= 11 < ∞ Update the table V(6,5)=11
Now the altered table:
0 1 2 3 4 5 6 7 8
0 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞
1 4 ∞ ∞ ∞ ∞ ∞ 8 ∞
7 12 ∞ ∞ ∞ ∞ ∞
8
6 12 ∞ ∞ ∞ 9 15

5 12 ∞ ∞ 11 15 Least value is 11(vertex 5 is selected)

From the table the vertex 2 , 5 and 8, vertex 5 has least cost so we can select vertex 5.Mark
vertex 5 as visited.
Adjacency vertex for 5 is 2,3,4 and 6. 6 is already visited, so find distance between (5,2), (5,3)
and(5,4)
Distance (5,2)
d(x, y) = d(x) + c(x, y) < d(y)
d(5,2) = d(5)+c(5,2) < d(2)
= (11 + 4) < 12
= 15 < 12 table is not updated V(5,2)=12
Distance (5,3)
d(x, y) = d(x) + c(x, y) < d(y)
d(5,3) = d(5)+c(5,3) < d(3)
= (11 + 14) < ∞
= 25 < ∞ update the table V(5,3) = 25
Distance (5,4)
d(x, y) = d(x) + c(x, y) < d(y)
d(5,4) = d(5) + c(5,4) < d(4)
= (11 + 10) < ∞
= 22 < ∞ update the table V(5,4)=22
Now the altered table
0 1 2 3 4 5 6 7 8
0 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞
1 4 ∞ ∞ ∞ ∞ ∞ 8 ∞
7 12 ∞ ∞ ∞ ∞ 8 ∞
6 12 ∞ ∞ ∞ 9 15
5 12 ∞ ∞ 11 15
12 25 22 Least value is 12(vertex 2 is
2 15 selected)

From the table the vertex 2,3,4 and 8, vertex 2 has least cost so we can select vertex 2.Mark
vertex 2 as visited.
Adjacency vertex for 2 is 1,3,5 and 8. 1 and 5 are already visited, so find distance between (2,3)
and(2,8)
Distance (2,3)
d(x, y) = d(x) + c(x, y) < d(y)
d(2,3) = d(2) + c(2,3) < d(3)
= (12 + 7) < 25
= 19 < 25 update the table V(2,3)
Distance (2,8)
d(x, y) = d(x) + c(x, y) < d(y)
d(2,8) = d(2) + c(2,8) < d(8)
= (12 + 2) < 15
= 14 < 15 update the table V(2,8) =14
Now the altered table
0 1 2 3 4 5 6 7 8
0 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞
1 4 ∞ ∞ ∞ ∞ ∞ 8 ∞
12 ∞ ∞ ∞ ∞
7 8 ∞
∞ ∞ ∞
6 12 9 15
∞ ∞
5 12 11 15
25 22
2 12 15
19 22 Least value is 14(vertex 8 is
8 14
selected)
19 22
3
22
4

From the table the vertex 3,4 and 8, vertex 8 has least cost so we can select vertex 8.Mark
vertex 8 as visited.
Adjacency vertex for 8 is 2,6 and 7. 2,6 and 7 are already visited, so we can take next least cost
vertex from the table.
From above table the next unvisited vertex are 3 and 4. The least value is 19 so we can select
vertex 3.Mark vertex 3 as visited.
From vertex 3 there is no adjacent unvisited vertex, so we can take next minimum cost vertex.
Next minimum vertex is 4 .
Shortest path between the vertex 0 to other vertex:
Minimum
Source Destination Shortest Path
Cost
0 1 4 0-1
0 2 8 0-1-2
0 3 19 0-1-2-3
0 4 22 0-7-6-5-4
0 5 11 0-7-6-5
0 6 9 0-7-6
0 7 8 0-7
0 8 14 0-1-2-8

Minimum Cost Spanning Trees:

The cost of the spanning tree is the sum of the weights of all the edges in the tree. There
can be many spanning trees. Minimum spanning tree is the spanning tree where the cost is
minimum among all the spanning trees. There also can be many minimum spanning trees.
What is Spanning tree?
A Spanning tree is a subset of Graph G, which has all the vertices covered with
minimum possible number of edges. Spanning tree does not have cycles and it cannot be
disconnected.
Example:
 Graph G
Spanning Trees:

Minimum Spanning-Tree Algorithm:

• Kruskal’s Algorithm
• Prim’s Algorithm
Prim’s Algorithm:
Prim's Algorithm is a greedy algorithm that is used to find the minimum spanning tree
from a graph. Prim's algorithm finds the subset of edges that includes every vertex of the graph
such that the sum of the weights of the edges can be minimized.

Prim's algorithm starts with the single node and explores all the adjacent nodes with all the
connecting edges at every step. The edges with the minimal weights causing no cycles in the
graph got selected.

Algorithm:
Step 1: Select a starting vertex
Step 2: Repeat Steps 3 and 4 until there are fringe vertices
Step 3: Select an edge 'e' connecting the tree vertex and fringe vertex that has minimum weight
Step 4: Add the selected edge and the vertex to the minimum spanning tree T
[END OF LOOP]
Step 5: EXIT

Discuss prim’s algorithm to find minimum spanning tree and analyze its complexity.
Apply the algorithm to find the minimum spanning tree for the following graph.

Step 1: Choose any arbitrary node as root node.

we choose S node as the root node of Prim's spanning tree. This node is arbitrarily
chosen, so any node can be the root node.
Step 2: Check outgoing edges and select the one with less cost
After choosing the root node S, we see that S,A and S,C are two edges with weight 7
and 8, respectively. We choose the edge S,A as it is lesser than the other.

Now, the tree S-A is treated as one node and we check for all edges going out from it. We
select the one which has the lowest cost and include it in the tree.

After this step, S-A-C tree is formed. Now we'll again treat it as a node and will check all the
edges again. However, we will choose only the least cost edge. In this case, C-D is the new
edge, which is less than other edges' cost 8,4, etc.

After adding node D to the spanning tree, we now have two edges going out of it having the
same cost 2, i.e. D-T and D-B. Thus, we can add either one. But the next step will again yield
edge 2 as the least cost. Hence, we are showing a spanning tree with both edges included.

Kruskal’s Algorithm:
Kruskal's Algorithm is used to find the minimum spanning tree for a
connected weighted graph. The main target of the algorithm is to find the subset of edges by
using which we can traverse every vertex of the graph. It follows the greedy approach that finds
an optimum solution at every stage instead of focusing on a global optimum.
Algorithm steps:

Step 1: Sort all edges in increasing order of their edge weights.

Step 2: Pick the smallest edge.

Step 3: Check if the new edge creates a cycle or loop in a spanning tree.

Step 4: If it doesn’t form the cycle, then include that edge in MST. Otherwise, discard it.

Step 5: Repeat from step 2 until it includes |V| - 1 edges in MST.

Discuss Kruskal’s algorithm to find minimum spanning tree and analyze its time
complexity. Apply the algorithm to find the minimum spanning tree for the following
graph.
Step 1:Arrange all edges in their increasing order of weight.

Step2: Add the edge which has the least weightage.

Now we start adding edges to the graph beginning from the one which has the least weight
without violating the spanning tree properties(ie) no edge should form a cycle.

The least cost is 2 and edges involved are B,D and D,T. We add them. Adding them does not
violate spanning tree properties, so we continue to our next edge selection.
Next cost is 3, and associated edges are A,C and C,D. We add them again

Next cost in the table is 4, and we observe that adding it will create a circuit in the graph. −

We ignore it. In the process we shall ignore/avoid all edges that create a circuit.

Edges with cost 5 and 6 also create circuits. We ignore them and move on.
Now we are left with only one node to be added. Between the two least cost edges available 7
and 8, we shall add the edge with cost 7.

We have included all the nodes of the graph and we now have minimum cost spanning tree.
UNIT IV DYNAMIC PROGRAMMING AND BACKTRACKING
Dynamic Programming: Computing binomial coefficient - Warshall's and Floyd's algorithm . Backtracking:
General method – N Queens Problem – Hamiltonian Circuits .Exhaustive search: DFS, BFS.

Dynamic Programming:
Dynamic programming is a technique for solving a complex problem by first breaking
into a collection of simpler subproblems, solving each subproblem just once, and then storing
their solutions to avoid repetitive computation.
Dynamic programming is a technique that breaks the problems into sub-problems, and
saves the result for future purposes so that we do not need to compute the result again. The
subproblems are optimized to optimize the overall solution is known as optimal substruct ure
property. The main use of dynamic programming is to solve optimization problems.

Consider an example of the Fibonacci series.

The following series is the Fibonacci series:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ,…
The numbers in the above series are not randomly calculated.
Mathematically, we could write each of the terms using the below formula:
F(n) = F(n-1) + F(n-2),

With the base values F(0) = 0, and F(1) = 1. To calculate the other numbers, we follow the
above relationship. For example, F(2) is the sum f(0) and f(1), which is equal to 1.
How can we calculate F(20)?

The F(20) term will be calculated using the nth formula of the Fibonacci series. The below
figure shows that how F(20) is calculated.

The following are the steps that the dynamic programming follows:
o It breaks down the complex problem into simpler subproblems.
o It finds the optimal solution to these sub-problems.
o It stores the results of subproblems (memorization). The process of storing the results
of subproblems is known as memorization.
o It reuses them so that same sub-problem is calculated more than once.
o Finally, calculate the result of the complex problem.
There are two approaches to dynamic programming:
Top-down approach
The top-down approach follows the memorization technique, while bottom-up approach
follows the tabulation method. Here memorization is equal to the sum of recursion and
caching. Recursion means calling the function itself, while caching means storing the
intermediate results.

Bottom-Up approach:

The bottom-up approach is also one of the techniques which can be used to
implement the dynamic programming.
 It uses the tabulation technique to implement the dynamic programming
approach.
 It solves the same kind of problems but it removes the recursion. If we remove
the recursion, there is no stack overflow issue and no overhead of the recursive
functions. In this tabulation technique, we solve the problems and store the
results in a matrix.
Computing Binomial Coefficient:
Binomial coefficient is a coefficient of a term in the expansion of the binomial(x+y)n .
According to the binomial theorem,
(x+y)n = nC0 xn y0 +nC1 xn-1y1+nC2 xn-2 y2 +………+nCn x0yn
Where nC0+nC1 +nC2 +………+nCn are binomial coefficient.
Binomial Coefficient using Dynamic Programming:

 Many sub problems are called again and again, since they have an overlapping
sub problems property. Re-computations of the same sub problems is avoided by
storing their results in the temporary array C[i, j] in a bottom up manner.
 The optimal substructure for using dynamic programming is stated as,

In Table, index i indicates row and index j indicates column

Example:Illustrate how binomial coefficient is found using dynamic programming and apply
the same to find C(6,4).
Solution:
Formula:
 r→ 0 1 2 3 4
n↓
0 1
1 1 1
2 1 1
3 1 1
4 1 1
5 1
6 1

By the above formula: C[2,1] = C[1,1]+C[1,0]

=1+1 = 2
C[3,1] = C[2,1]+C[2,0]
= 2+1 = 3
C[3,2] = C[2,2]+C[2,1]
= 1+2 = 3
C[4,1] = C[3,0]+C[3,1]
= 1+3 = 4
C[4,2] = C[3,1]+C[3,2]
=3+3=6
C[4,3] = C[3,2] + C[ 3,3]
=3+1=4
C[5,1] = C[4,0] + C[4,1]
=1+4=5
C[5,2] = C[4,1] + C[4,2]
= 4 + 6 =10
C[5,3] = C[4,2] + C[4,3]
= 6+ 4 = 10
C[5,4] = C[4,3] + C[4,4]
= 4 + 1 =5
C[6,1] = C[5,0] + C[5,1]
=1+5=6
C[6,2] = C[5,1] + C[5,2]
= 5 + 10= 15
 C[6,3] = C[5,2] + C[5,3]
= 10 +10=20
C[6,4] = C[5,3] + C[5,4]
= 10 + 5 =15
Initial table : First column value and the diagonal is 1 based on firstcondition. Use the second
formula to find remaining values below diagonal.

r→ 0 1 2 3 4
n↓
0 1
1 1 1
2 1 2 1
3 1 3 3 1
4 1 4 6 4 1
5 1 5 10 10 5
6 1 6 15 20 15 C(6,4) =15

Knapsack Problem and Memory Function:

The knapsack problem is to find the set of items which maximizes the profit such that
collective weight of selected items does not cross the knapsack capacity.

 Problem : Given a set of items, each having different weight and value or profit
associated with it. Find the set of items such that the total weight is less than or equal
to a capacity of the knapsack and the total value earned is as large as possible.
 The knapsack problem is useful in solving resource allocation problem. Let X = < x 1,
x2, x3 , . . . . . , xn> be the set of n items. Sets W = <w1 , w2, w3, . . . , w n> and V = < v1 ,
v2, v3, . . . , vn> are weight and value associated with each item in X. Knapsack
capacity is M unit.
 The knapsack problem is to find the set of items which maximizes the profit such that
collective weight of selected items does not cross the knapsack capacity.
 Select items from X and fill the knapsack such that it would maximize the profit.
Knapsack problem has two variations. 0/1 knapsack, that does not allow breaking of
items. Either add an entire item or reject it. It is also known as a binary knapsack.
Fractional knapsack allows breaking of items. Profit will be earned proportionally

The mathematical notion of the knapsack problem is given as :

V [1 …. n, 0 … M] : Size of the table
V (n, M) = Solution
n = Number of items

Example: Find an optimal solution for following 0/1 Knapsack problem using dynamic
programming: Number of objects n = 4, Knapsack Capacity M = 5, Weights (W 1, W 2,
W3 , W 4) = (2, 3, 4, 5) and profits (P1 , P2, P3, P4 ) = (3, 4, 5, 6).
Solution:
Solution of the knapsack problem is defined as,

Boundary conditions would be V [0, i] = V[i, 0] = 0.

Item Weight Value
1 2 3
2 3 4
3 4 5
4 5 6

Initial table:
 Boundary conditions would be V [0, i] = V[i, 0] = 0. Initial configuration of table looks
like.

Item
Weight Value 0 1 2 3 4 5
values
- - 0 0 0 0 0 0 0
2 3 1 0
3 4 2 0
4 5 3 0
5 6 4 0
Filling first column, j = 1
V [1, 1] ⇒ i = 1, j = 1, wi = w1 = 2
As, j < wi , V [i, j] = V [i – 1, j]
V [1, 1] = V [0, 1] = 0
V [2, 1] ⇒ i = 2, j = 1, wi = w2 = 3
As, j < wi , V [i, j] = V [i – 1, j]
V [2, 1] = V [1, 1] = 0

V [3, 1] ⇒ i = 3, j = 1, wi = w3 = 4
As, j < wi, V [i, j] = V [i – 1, j]
V [3, 1] = V [2, 1] = 0

V [4, 1] ⇒ i = 4, j = 1, wi = w4 = 5
As, j < wi, V[i, j] = V[i – 1, j]
V [4, 1] = V [3, 1] = 0
Filling first column, j = 2

V[1, 2] ⇒ i = 1, j = 2, wi = w1 = 2, vi = 3
As, j ≥ w i, V [i, j]=max {V [i – 1, j], vi + V[i – 1, j – wi] }
= max {V [0, 2], 3 + V [0, 0]}
V[1, 2] = max (0, 3) = 3

V[2, 2] ⇒ i = 2, j = 2, wi = w2 = 3, vi = 4
As, j < wi, V [i, j] = V[i – 1, j]
V[2, 2] = V[1, 2] = 3

V[3, 2] ⇒ i = 3, j = 2, wi = w3 = 4, vi = 5
As, j < wi, V[i, j] = V[i – 1, j]
V[3, 2] = V [2, 2] = 3

V[4, 2] ⇒ i = 4, j = 2, wi = w4 = 5, vi = 6
As, j < wi, V[i, j] = V[i – 1, j]
V[4, 2] = V[3, 2] = 3

Filling first column, j = 3

V[1, 3] ⇒ i = 1, j = 3, wi = w1 = 2, vi = 3
As, j ≥ w i, V [i, j]=max {V [i – 1, j], vi + V [i – 1, j – wi] }
= max {V [0, 3], 3 + V [0, 1]}
V[1, 3] = max (0, 3) = 3

V[2, 3] ⇒ i = 2, j = 3, wi = w2 = 3, vi = 4
As, j ≥ wi, V [i, j] = max {V [i – 1, j], vi + V [i – 1, j – wi] }
= max {V [1, 3], 4 + V [1, 0]}
V[2, 3] = max (3, 4) = 4

V[3, 3] ⇒ i = 3, j = 3, wi = w3 = 4, vi = 5
As, j < wi , V [i, j] = V [i – 1, j]
V[3, 3] = V [2, 3] = 4
V[4, 3] ⇒ i = 4, j = 3, wi = w4 = 5, vi = 6
As, j < wi, V[i, j] = V[i – 1, j]
V[4, 3] = V [3, 3] = 4

Filling first column, j = 4

V[1, 4] ⇒ i = 1, j = 4, w i = w1 = 2, vi = 3
As, j ≥ w i, V [i, j]=max {V [i – 1, j], vi + V [i – 1, j – wi] }
= max {V [0, 4], 3 + V [0, 2]}
V[1, 4] = max (0, 3) = 3

V[2, 4] ⇒ i = 2, j = 4, wi = w2 = 3 , vi = 4
As, j ≥ wi , V [i, j] =max {V [i – 1, j], vi + V [i – 1, j – wi] }
= max {V [1, 4], 4 + V [1, 1]}
V[2, 4] = max (3, 4 + 0) = 4

V[3, 4] ⇒ i = 3, j = 4, wi = w3 = 4, vi = 5
As, j ≥ w i, V [i, j]=max {V [i – 1, j], vi + V [i – 1, j – wi] }
= max {V [2, 4], 5 + V [2, 0]}
V[3, 4] = max (4, 5 + 0) = 5

V[4, 4] ⇒ i = 4, j = 4, wi = w4 = 5, vi = 6
As, j < wi , V [i, j] = V [i – 1, j]
V[4, 4] = V [3, 4] = 5
Filling first column, j = 5

V [1, 5] ⇒ i = 1, j = 5, wi = w1 = 2, vi = 3
As, j ≥ wi , V [i, j] = max {V [i – 1, j], vi + V [i – 1, j – wi] }
= max {V [0, 5], 3 + V [0, 3]}
V[1, 5] = max (0, 3) = 3

V[2, 5] ⇒ i = 2, j = 5, wi = w2 = 3, vi = 4
As, j ≥ wi , V [i, j] =max {V [i – 1, j], vi + V [i – 1, j – wi] }
= max {V [1, 5], 4 + V [1, 2]}
V[2, 5] = max (3, 4 + 3) = 7

V[3, 5] ⇒ i = 3, j = 5, w i = w3 = 4, vi = 5
As, j ≥ wi, V [i, j] = max {V [i – 1, j], vi + V [i – 1, j – wi] }
= max {V [2, 5], 5 + V [2, 1]}
V[3, 5] = max (7, 5 + 0) = 7

V [4, 5] ⇒ i = 4, j = 5, wi = w4 =5, vi = 6
As, j ≥ w i, V [i, j] = max {V [i – 1, j], vi + V [i – 1, j – wi] }
= max {V [3, 5], 6 + V [3, 0]}
V[4, 5] = max (7, 6 + 0) = 7
Final table would be,
Item
Weight Value 0 1 2 3 4 5
values
- - 0 0 0 0 0 0 0
2 3 1 0 0 3 3 3 3
3 4 2 0 0 3 4 4 7
4 5 3 0 0 3 4 5 7
5 6 4 0 0 3 4 5 7

Find selected items for M = 5

Step 1 : Initially, i = n = 4, j = M = 5

V[i, j] = V[4, 5] = 7
V[i – 1, j] = V[3, 5] = 7
V[i, j] = V[i – 1, j], so don’t select ith item and check for the previous item.
so i = i – 1 = 4 – 1 = 3
Solution Set S = { }

Step 2 : i = 3, j = 5
V[i, j] = V[3, 5] = 7
V[i – 1, j] = V[2, 5] = 7
V[i, j] = V[i – 1, j], so don’t select ith item and check for the previous item.
so i = i – 1 = 3 – 1 = 2
Solution Set S = { }
Step 3 : i = 2, j = 5
V[i, j] = V[2, 5] = 7
V[i – 1, j] = V[1, 5] = 3
V[i, j] ≠ V[i – 1, j], so add item Ii = I2 in solution set.
Reduce problem size j by wi
j = j – wi = j – w2 = 5 – 3 = 2
i=i–1=2–1=1
Solution Set S = {I2}
Step 4 : i = 1, j = 2
V[1, j] = V[1, 2] = 3
V[i – 1, j] = V[0, 2] = 0
V[i, j] ≠ V[i – 1, j], so add item Ii = I1 in solution set.
Reduce problem size j by wi
j = j – wi = j – w1 = 2 – 2 = 0
Solution Set S = {I1 , I2}
Problem size has reached to 0, so final solution is
S = {I1, I2 } X = (1,1,0,0) Earned profit = P1 + P2 = 7

Floyd Warshall Algorithm:

The Floyd Warshall Algorithm is for solving all pairs of shortest-path problems. The
problem is to find the shortest distances between every pair of vertices in a given edge-
weighted directed Graph.
 Floyd–Warshall’s Algorithm is used to find the shortest paths between all pairs of vertices
in a graph, where each edge in the graph has a weight which is positive or negative.
 The biggest advantage of using this algorithm is that all the shortest distances between any
2 vertices could be calculated in O(V3), where V is the number of vertices in a graph.
 Floyd-Warshall algorithm is also called as Floyd’s algorithm, Roy-Floyd algorithm, Roy-
Warshall algorithm, or WFI algorithm.
 This algorithm follows the dynamic programming approach to find the shortest paths.

Algorithm:
For a graph with N vertices:
Step 1: Initialize the shortest paths between any 2 vertices with Infinity.
Step 2: Find all pair shortest paths that use 0 intermediate vertices, then find the shortest paths
that use 1 intermediate vertex and so on.. until using all N vertices as intermediate nodes.
Step 3: Minimize the shortest paths between any 2 pairs in the previous operation.
Step 4: For any 2 vertices (i,j) , one should actually minimize the distances between this pair
using the first K nodes, so the shortest path will be: min(dist[i][k]+dist[k][j],dist[i][j]).
dist[i][k] represents the shortest path that only uses the first K vertices, dist[k][j] represents the
shortest path between the pair k,j. As the shortest path will be a concatenation of the shortest
path from i to k, then from k to j.
for k in range(1,n):
for i in range(1,n):
for j in range(1,n):
dist[i][j] = min( dist[i][j], dist[i][k] + dist[k][j] )

In the above given algorithm the basic operation is :

Example:
Warshall Algorithm:

Warshall's algorithm is used to determine the transitive closure of a directed graph or

all paths in a directed graph by using the adjacency matrix. For this, it generates a sequence
of n matrices. Where, n is used to describe the number of vertices.
R(0), ..., R(k-1) , R(k), ... , R(n)
Generalformula can written as:

rij(k) = rij(k-1)or (rik(k-1)and rkj(k-1))

Warshall's Algorithm for computing transitive closure
Warshall(A[1...n, 1...n]) // A is the adjacency matrix
R(0) ← A
for k ← 1 to n do
for i ← 1 to n do
for j ← to n do
R(k)[i, j] ← R(k-1)[i, j] or (R(k-1)[i, k] and R(k-1)[k, j])
return R(n)
Example:
Exhaustive Search Algorithm:
Exhaustive search Exhaustive search is a brute force approach to solving a problem
that involves searching for an element with a special property; usually among combinatorial
objects such permutations, combinations, or subsets of a set.
Method:
1. Systematically construct all potential solutions to the problem
 2. Evaluate solutions one by one, disqualifying infeasible ones and, for optimization
problems, keeping track of the best solution found so far
3. When search ends, return the (best) solution found
Example 1: Traveling salesman problem
Given n cities with known distances between each pair, find the shortest tour that passes
through all the cities exactly once before returning to the starting city.
Alternatively: Find shortest Hamiltonian circuit in a weighted connected graph.
Example: a b c d 8 2 7 5 3 4 TSP by exhaustive search
Tour Cost
a→b→c→d→a 2+3+7+5 = 17
a→b→d→c→a 2+4+7+8 = 21
a→c→b→d→a 8+3+4+5 = 20
a→c→d→b→a 8+7+4+2 = 21
a→d→b→c→a 5+4+3+8 = 20
a→d→c→b→a 5+7+3+2 = 17
Example 2: Knapsack Problem
Given n items with
weights: w1 w2 … wn
values: v1 v2 … vn
and a knapsack of capacity W,
find most valuable subset of the items that fit into the knapsack
Example: Knapsack capacity W=16
Item Weight Value

1 2 $20
2 5 $30
3 10 $50
4 5 $10

Knapsack by exhaustive search:

Subset Total weight Total value

{1} 2 $20
{2} 5 $30
{3} 10 $50
{4} 5 $10
{4} 5 $10
{1,2} 7 $50
{1,3} 12 $70
{1,4} 7 $30
{2,3} 15 $80
 {2,4} 10 $40
{3,4} 15 $60
{1,2,3} 17 not feasible
{1,2,4} 12 $60
{1,3,4} 17 not feasible
{2,3,4} 20 not feasible
{1,2,3,4} 22 not feasible

Comments on Exhaustive Search:

1. Typically, exhaustive search algorithms run in a realistic amount of time only on very small
instances
2. For some problems, there are much better alternatives – shortest paths – minimum spanning
tree – assignment problem
3. In many cases, exhaustive search (or variation) is the only known way to solve problem
exactly for all its possible instances
TSP
knapsack problem

Iterative Deepening Search(IDS) or Iterative Deepening Depth First Search(IDDFS):

There are two common ways to traverse a graph, BFS and DFS. Considering a Tree
(or Graph) of huge height and width, both BFS and DFS are not very efficient due to some
reasons.
Breadth-first Search:
o Breadth-first search is the most common search strategy for traversing a tree or graph.
This algorithm searches breadthwise in a tree or graph, so it is called breadth-first
search.
o BFS algorithm starts searching from the root node of the tree and expands all
successor node at the current level before moving to nodes of next level.
o The breadth-first search algorithm is an example of a general-graph search algorithm.
o Breadth-first search implemented using FIFO queue data structure.
Advantages:
o BFS will provide a solution if any solution exists.
o If there are more than one solutions for a given problem, then BFS will provide the
minimal solution which requires the least number of steps.

Disadvantages:
o It requires lots of memory since each level of the tree must be saved into memory to
expand the next level.
o BFS needs lots of time if the solution is far away from the root node.

Example:
 In the below tree structure, we have shown the traversing of the tree using BFS algorithm
from the root node S to goal node K. BFS search algorithm traverse in layers, so it will follow
the path which is shown by the dotted arrow, and the traversed path will be:
1. S---> A--->B---->C--->D---->G--->H--->E---->F---->I >K

Time Complexity: Time Complexity of BFS algorithm can be obtained by the number of
nodes traversed in BFS until the shallowest Node. Where the d= depth of shallowest solution
and b is a node at every state.

T (b) = 1+b2 +b3 + ....... + b d= O (b d)

Space Complexity: Space complexity of BFS algorithm is given by the Memory size of
frontier which is O(b d).

Algorithm for BFS:

from collections import defaultdict, deque

class Graph:
def __init__(self):
self.graph = defaultdict(list)

def add_edge(self, u, v):

self.graph[u].append(v)

def bfs(self, start):

visited = set()
queue = deque([start])
visited.add(start)
while queue:
node = queue.popleft()
print(node, end=" ")
 for neighbor in self.graph[node]:
if neighbor not in visited:
queue.append(neighbor)
visited.add(neighbor)

# Example usage:
# Create a graph
g = Graph()
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 2)
g.add_edge(2, 0)
g.add_edge(2, 3)
g.add_edge(3, 3)

print("Breadth First Traversal starting from vertex 2:")

g.bfs(2)

2. Depth-first Search
o Depth-first search isa recursive algorithm for traversing a tree or graph data structure.
o It is called the depth-first search because it starts from the root node and follows each
path to its greatest depth node before moving to the next path.
o DFS uses a stack data structure for its implementation.
o The process of the DFS algorithm is similar to the BFS algorithm.
Advantage:
o DFS requires very less memory as it only needs to store a stack of the nodes on the
path from root node to the current node.
o It takes less time to reach to the goal node than BFS algorithm (if it traverses in the
right path).
Disadvantage:
o There is the possibility that many states keep re-occurring, and there is no guarantee
of finding the solution.
 o DFS algorithm goes for deep down searching and sometime it may go to the infinite
loop.
Example:

Algorithm for Depth-first Search

from collections import defaultdict

class Graph:
def __init__(self):
self.graph = defaultdict(list)

def add_edge(self, u, v):

self.graph[u].append(v)

def dfs_util(self, v, visited):

visited.add(v)
print(v, end=" ")

for neighbor in self.graph[v]:

if neighbor not in visited:
self.dfs_util(neighbor, visited)

def dfs(self, start):

visited = set()
self.dfs_util(start, visited)

# Example usage:
# Create a graph
g = Graph()
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 2)
g.add_edge(2, 0)
g.add_edge(2, 3)
g.add_edge(3, 3)

print("Depth First Traversal starting from vertex 2:")

g.dfs(2)

In the below search tree, we have shown the flow of depth-first search, and it will follow the
order as:
Root node--->Left node----- > right node.
It will start searching from root node S, and traverse A, then B, then D and E, after traversing
E, it will backtrack the tree as E has no other successor and still goal node is not found. After
backtracking it will traverse node C and then G, and here it will terminate as it found goal
node.

Completeness: DFS search algorithm is complete within finite state space as it will expand
every node within a limited search tree.
Time Complexity: Time complexity of DFS will be equivalent to the node traversed by the
algorithm. It is given by:
T(n)= 1+ n2 + n3 + ......... + nm=O(nm)
Where, m= maximum depth of any node and this can be much larger than d (Shallowest
solution depth)
Space Complexity: DFS algorithm needs to store only single path from the root node, hence
space complexity of DFS is equivalent to the size of the fringe set, which is O(bm).

Iterative deepening depth-first Search:

The iterative deepening algorithm is a combination of DFS and BFS algorithms. This search
algorithm finds out the best depth limit and does it by gradually increasing the limit until a
goal is found.

This algorithm performs depth-first search up to a certain "depth limit", and it keeps
increasing the depth limit after each iteration until the goal node is found.

This Search algorithm combines the benefits of Breadth-first search's fast search and depth-
first search's memory efficiency.
The iterative search algorithm is useful uninformed search when search space is large, and
depth of goal node is unknown.
Advantages:
o It combines the benefits of BFS and DFS search algorithm in terms of fast search and
memory efficiency.

Disadvantages:
o The main drawback of IDDFS is that it repeats all the work of the previous phase.

Algorithm for Iterative deepening depth-first Search:

class Graph:
def __init__(self):
self.graph = {}
def add_edge(self, u, v):
if u in self.graph:
self.graph[u].append(v)
else:
self.graph[u] = [v]
def iddfs(self, start, goal):
depth = 0
while True:
found = self.dfs(start, goal, depth, set())
if found:
print("Goal found at depth:", depth)
return True
depth += 1
def dfs(self, node, goal, depth, visited):
if depth == 0 and node == goal:
print(node, end=" ")
return True
if depth > 0:
print(node, end=" ")
visited.add(node)
if node == goal:
return True
if node in self.graph:
for neighbor in self.graph[node]:
if neighbor not in visited:
 if self.dfs(neighbor, goal, depth - 1, visited):
return True

# Example usage:
# Create a graph
g = Graph()
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 3)
g.add_edge(1, 4)
g.add_edge(2, 5)
g.add_edge(2, 6)

start_node = 0
goal_node = 6

print("Iterative Deepening Depth-First Search:")

g.iddfs(start_node, goal_node)

Example:

Following tree structure is showing the iterative deepening depth-first search. IDDFS
algorithm performs various iterations until it does not find the goal node. The iteration
performed by the algorithm is given as:
 1'st Iteration --------> A
2'nd Iteration -------> A, B, C
3'rd Iteration -------- >A, B, D, E, C, F, G
4'th Iteration --------- >A, B, D, H, I, E, C, F, K, G
In the fourth iteration, the algorithm will find the goal node.

Completeness:
This algorithm is complete is if the branching factor is finite.

Time Complexity:
Let's suppose b is the branching factor and depth is d then the worst-case timecomplexity is
O(b d).
Optimal:
IDDFS algorithm is optimal if path cost is a non- decreasing function of the depth ofthe node.

1.BACKTRACKING
General Method:
Backtracking is used to solve problem in which a sequence of objects is chosen from a specified set so that the
sequence satisfies some criterion. The desired solution is expressed as an n-tuple (x1, , xn) where each xi Є S, S
being a finiteset.

The solution is based on finding one or more vectors that maximize, minimize, or satisfy a criterion function P
(x1, , xn). Form a solution and check at every step if this has any chance of success. If the solution at any point
seems not promising, ignore it. All solutions requires a set of constraints divided into two categories: explicit and
implicit constraints.

Definition 1: Explicit constraints are rules that restrict each xi to take on values only from a given set. Explicit
constraints depend on the particular instance I of problem being solved. All tuples that satisfy the explicit
constraints define a possible solution space for I.

Definition 2: Implicit constraints are rules that determine which of the tuples in the solution space of I satisfy the
criterion function.
For 8-queensproblem:

Explicit constraints using 8-tuple formation, for this problem are S= {1, 2, 3, 4, 5, 6, 7,8}.
The implicit constraints for this problem are that no two queens can be the same (i.e., all queens must be on
different columns) and no two queens can be on the same diagonal.

Backtracking is a modified depth first search of a tree. Backtracking algorithms determine problem solutions by
systematically searching the solution space for the given problem instance. This search is facilitated by using a
tree organization for the solution space.

Backtracking is the procedure whereby, after determining that a node can lead to nothing but dead end, we go
back (backtrack) to the nodes parent and proceed with the search on the next child.
A backtracking algorithm need not actually create a tree.
Rather, it only needs to keep track of the values in the current branch being investigated. This is the way we
implement backtracking algorithm. We say that the state space tree exists implicitly in the algorithm because it is
not actually constructed.

State space: is the set of paths from root node to other nodes. State space tree is the tree organization of the
solution space. The state space trees are called static trees.
Terminology:
Problem state is each node in the depth first search tree.
Solution states are the problem states „S‟ for which the path from the root node to „S‟ defines a tuple in the
solution space.
Answer states are those solution states for which the path from root node to s defines a tuple that is a member of
the set of solutions.
Live node is a node that has been generated but whose children have not yet been generated.
E-node is a live node whose children are currently being explored. In other words, an E-node is a node currently
being expanded.
Dead node is a generated node that is not to be expanded or explored any further. All children of a dead node
have already beenexpanded.
Branch and Bound refers to all state space search methods in which all children of an E-node are generated
before any other live node can become theE-node.
Depth first node generation with bounding functions is called backtracking. State generation methods in which
the E-node remains the E-node until it is dead, lead to branch and bound methods.
N-Queens Problem:
Let us consider, N = 8. Then 8-Queens Problem is to place eight queens on an 8 x 8 chessboard so that no two
“attack”, that is, no two of them are on the same row, column, or diagonal.
All solutions to the 8-queens problem can be represented as 8-tuples (x1,......... , x8), where xi is the column of the
ith row where the ith queen is placed.
The explicit constraints using this formulation are Si = {1, 2, 3, 4, 5, 6, 7, 8}, 1 <i < 8.
Therefore the solution space consists of 888-tuples.

The implicit constraints for this problem are that no two xi‟s can be the same (i.e., all queens must be on
different columns) and no two queens can be on the same diagonal.
This realization reduces the size of the solution space from 88 tuples to 8! Tuples.
The promising function must check whether two queens are in the same column or diagonal:
Suppose two queens are placed at positions (i, j) and (k, l) Then:

Column Conflicts: Two queens conflict if their xi values areidentical.

Algorithm for 8 Queens Problem:
def is_safe(board, row, col):
# Check if there is a queen in the same column
for i in range(row):
if board[i] == col:
return False
# Check upper diagonal on left side
for i, j in zip(range(row, -1, -1), range(col, -1, -1)):
if board[i] == j:
return False
# Check upper diagonal on right side
for i, j in zip(range(row, -1, -1), range(col, 8)):
if board[i] == j:
return False
return True
def solve_queens(board, row):
if row >= 8:
return True
for col in range(8):
if is_safe(board, row, col):
board[row] = col
if solve_queens(board, row + 1):
return True
# Backtrack if placing a queen at (row, col) doesn't lead to a solution
board[row] = -1
return False
def print_board(board):
for i in range(8):
for j in range(8):
if board[i] == j:
print("Q", end=" ")
else:
print(".", end=" ")
print()
def solve_8_queens():
board = [-1] * 8
if solve_queens(board, 0):
print("Solution Found:")
print_board(board)
else:
print("No solution exists")
# Example usage
solve_8_queens()
Algorithm for 4 Queen’s Problems:
def is_safe(board, row, col):
# Check if there is a queen in the same column
for i in range(row):
if board[i] == col:
return False
# Check upper diagonal on left side
for i, j in zip(range(row, -1, -1), range(col, -1, -1)):
if board[i] == j:
return False
# Check upper diagonal on right side
for i, j in zip(range(row, -1, -1), range(col, 4)):
if board[i] == j:
return False
return True
def solve_queens(board, row):
if row >= 4:
return True

for col in range(4):

if is_safe(board, row, col):
board[row] = col
if solve_queens(board, row + 1):
return True
# Backtrack if placing a queen at (row, col) doesn't lead to a solution
board[row] = -1
return False
def print_board(board):
for i in range(4):
for j in range(4):
if board[i] == j:
print("Q", end=" ")
else:
print(".", end=" ")
print()
def solve_4_queens():
board = [-1] * 4
if solve_queens(board, 0):
print("Solution Found:")
print_board(board)
else:
print("No solution exists")
# Example usage
solve_4_queens()
Hamiltonian Circuits:
Let G = (V, E) be a connected graph with n vertices. A Hamiltonian cycle (suggested by William Hamilton) is a round-trip
path along n edges of G that visits every vertex once and returns to its starting position. In other vertices of G are visited in
the order v1, v2, ............, vn+1, then the edges (vi, vi+1) are in E, 1 <i <n, and the vi are distinct expect for v1 and vn+1,
which are equal. The graph G1 contains the Hamiltonian cycle 1, 2, 8, 7,6,
5, 4, 3, 1. The graph G2 contains no Hamiltoniancycle
The backtracking solution vector (x1, xn) is defined so that xi represents the ith visited vertex of the proposed cycle. If
k = 1, then x1 can be any of the n vertices. To avoid printing the same cycle n times, we require that x1 = 1. If 1 < k < n,
then xk can be any vertex v that is distinctfromx1,x2,. ,xk–1and is connected by an edge to kx-1.The vertex xn can only be
one remaining vertex and it must be connected to both xn-1 and x1.
Using NextValue algorithm we can particularize the recursive backtracking schema to find all Hamiltonian cycles. This
algorithm is started by first initializing the adjacency matrix G[1: n, 1: n], then setting x[2: n] to zero and x[1] to 1, and then
executing Hamiltonian(2).
The traveling salesperson problem using dynamic programming asked for a tour that has minimum cost. This tour is a
Hamiltonian cycles. For the simple case of a graph all of whose edge costs are identical, Hamiltonian will find a minimum-
cost tour if a tour exists.
Algorithms for Hamiltonian Circuits:
class Graph:
def __init (self, vertices):
self.graph = [[0 for column in range(vertices)]
for row in range(vertices)]
self.V = vertices
# Check if this vertex can be added to the current path
def isSafe(self, v, pos, path):
# Check if this vertex is an adjacent vertex of the previously added vertex
if self.graph[path[pos - 1]][v] == 0:
return False
# Check if the vertex has already been included
for vertex in path:
if vertex == v:
return False
return True
# A recursive utility function to solve Hamiltonian cycle problem
def hamCycleUtil(self, path, pos):
if pos == self.V:
# Last vertex must be adjacent to the first vertex in path to make a cycle
if self.graph[path[pos - 1]][path[0]] == 1:
return True
else:
return False
# Remove current vertex if it doesn't lead to a solution
path[pos] = -1
return False
def hamCycle(self):
path = [-1] * self.V
 # Start from vertex 0 as the first vertex in the path
path[0] = 0
if self.hamCycleUtil(path, 1) == False:
print("No Hamiltonian Cycle exists")
return False
self.printSolution(path)
return True
def printSolution(self, path):
print("Hamiltonian Cycle exists:")
for vertex in path:
print(vertex, end=" ")
# Complete the cycle
print(path[0], "\n")
# Example usage
g1 = Graph(5)
g1.graph = [[0, 1, 0, 1, 0],
[1, 0, 1, 1, 1],
[0, 1, 0, 0, 1],
[1, 1, 0, 0, 1],
[0, 1, 1, 1, 0]]
g1.hamCycle()
g2 = Graph(5)
g2.graph = [[0, 1, 0, 1, 0],
[1, 0, 1, 1, 1],
[0, 1, 0, 0, 1],
[1, 1, 0, 0, 0],
[0, 1, 1, 0, 0]]
g2.hamCycle()

Floyd's algorithm, also known as Floyd-Warshall algorithm:

Floyd's algorithm, also known as Floyd-Warshall algorithm, is a dynamic programming-based

algorithm used for finding shortest paths in a weighted graph with positive or negative edge
weights (but with no negative cycles). It's particularly useful for finding the shortest paths
between all pairs of vertices in a graph.

Here's how Floyd's algorithm works:

Initialization: The algorithm initializes a 2D array called the "distance matrix". This matrix
stores the shortest distances between all pairs of vertices in the graph. Initially, it's filled with the
direct edge weights if there's an edge between two vertices, otherwise, it's set to infinity. Also,
the distance from a vertex to itself is set to 0.

Iterative Update: The algorithm iterates through all vertices and considers each vertex as an
intermediate vertex in the shortest path. For each pair of vertices (i, j), it checks if the shortest
path from vertex i to vertex j can be improved by including vertex k as an intermediate vertex. If
it can, the distance matrix is updated to reflect the new shortest path.

Termination: After all iterations, the distance matrix will contain the shortest distances between
all pairs of vertices in the graph.

Floyd's algorithm has a time complexity of O(V^3), where V is the number of vertices in the
graph.

Here's a Python implementation of Floyd's algorithm:

INF = float('inf')
def floyd(graph):
V = len(graph)
dist = [[0]*V for _ in range(V)]

for i in range(V):
for j in range(V):
dist[i][j] = graph[i][j]

for k in range(V):
for i in range(V):
for j in range(V):
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
return dist
# Example graph represented as an adjacency matrix
graph = [
[0, 5, INF, 10],
[INF, 0, 3, INF],
[INF, INF, 0, 1],
[INF, INF, INF, 0]
]

shortest_distances = floyd(graph)
for row in shortest_distances:
print(row)

Let's walk through this example:

Consider a graph with 4 vertices and the following adjacency matrix:
0 5 ∞ 10
∞ 0 3 ∞
∞ ∞ 0 1
∞ ∞ ∞ 0
The matrix represents the following edges:

Vertex 0 is connected to vertex 1 with weight 5 and to vertex 3 with weight 10.
Vertex 1 is connected to vertex 2 with weight 3.
Vertex 2 is connected to vertex 3 with weight 1.
Applying Floyd's algorithm on this graph will yield the shortest distances between all pairs of
vertices:

[0, 5, 8, 9]
[inf, 0, 3, 4]
[inf, inf, 0, 1]
[inf, inf, inf, 0]

This output shows that the shortest distance from vertex i to vertex j is stored at index [i][j] in
the resulting distance matrix.
UNIT V BRANCH-AND-BOUND,NP PROBLEMS AND APPROXIMATION
ALGORITHMS
Branch and Bound-Assignment -Knapsack problem – Traveling salesman problem -
NPComplete and NP-Hard problems. Approximation Algorithms - NP Hard
ProblemsKnapsack and Travelling Sales Man Problem..
Branch-And-Bound:

Branch and Bound is another method to systematically search a solution space. Just
like backtracking, we will use bounding functions to avoid generating subtrees that do not
contain an answer node.

Branch and Bound differs from backtracking in two important points:

 It has a branching function, it uses breadth first search

 It has a bounding function, which goes far beyond the feasibility test as a mean
to prune efficiently the search tree.
Branch and Bound refers to all state space search methods in which all children of the E-node
are generated before any other live node becomes the E-node.

 Live node is a node that has been generated but whose children have not yet
been generated.
 E-node is a live node whose children are currently being explored. In other words,
an E-node is a node currently being expanded.
 Dead node is a generated node that is not to be expanded or explored any further.
All children of a dead node have already been expanded.
 Branch-an-bound refers to all state space search methods in which all children of
an E-node are generated before any other live node can become the E-node.
Assignment Problem:
 Given n tasks and n agents.
 Each agent has a cost to complete each task.
 Assign each agent a task to minimize cost.

Example:
There are two approaches to calculate the cost function:
1. For each worker, we choose job with minimum cost from list of unassigned jobs (take minimum
entry from each row).
2. For each job, we choose a worker with lowest cost for that job from list of unassigned workers
(take minimum entry from each column).
In this article, the first approach is followed.
Let’s take below example and try to calculate promising cost when Job 2 is assigned to worker A.

Since Job 2 is assigned to worker A (marked in green), cost becomes 2 and Job 2 and worker A
becomes unavailable (marked in red).

Now we assign job 3 to worker B as it has minimum cost from list of unassigned jobs. Cost becomes 2
+ 3 = 5 and Job 3 and worker B also becomes unavailable.

Finally, job 1 gets assigned to worker C as it has minimum cost among unassigned jobs and job 4 gets
assigned to worker C as it is only Job left. Total cost becomes 2 + 3 + 5 + 4 = 14.
Below diagram shows complete search space diagram showing optimal solution path in green.

Knapsack Problem:

Example:

Solve the following instance of the knapsack problem using branch andbound.
Traveling salesman problem:
Travelling Salesman Problem (TSP) Problem is defined as “given n cities and distance
between each pair of cities, find out the path which visits each city exactly once and come
back to starting city, with the constraint of minimizing thetravelling distance.”

Algorithm :
1. Initially, graph is represented by cost matrix C, where
 Cij = cost of edge, if there is a direct path from city i to city j
 Cij = ∞, if there is no direct path from city i to city j.
2. Convert cost matrix to reduced matrix by subtracting minimum values from appropriate
rows and columns, such that each row and column contains at least one zero entry.

3. Find cost of reduced matrix. Cost is given by summation of subtracted amount from the
cost matrix to convert it in to reduce matrix.

4. Prepare state space tree for the reduce matrix

5. Find least cost valued node A (i.e. E-node), by computing reduced cost node matrix with
every remaining node.

6. If <i, j> edge is to be included, then do following :

(a) Set all values in row i and all values in column j of A to ∞

(b) Set A[j, 1] = ∞

(c) Reduce A again, except rows and columns having all ∞ entries.
 7. Compute the cost of newly created reduced matrix as,Cost =
L + Cost(i, j) + r

Where, L is cost of original reduced cost matrix and r is A[i, j].

8. If all nodes are not visited then go to step 4.

Example:

Find the solution of following travelling salesman problem using branch and bound
method.

Solution:
Reduce above cost matrix by subtracting minimum value from each row andcolumn.
Reduce it subtracting minimum value from corresponding column. Doing this weget,
Cost of M1 = C(1)
= Row reduction cost + Column reduction cost

= (10 + 2 + 2 + 3 + 4) + (1 + 3) = 25

This means all tours in graph has length at least 25. This is the optimal cost of thepath.

State space tree

Select edge 1-2:

Set M1 [1] [ ] = M1 [ ] [2] = ∞ Set
M1 [2] [1] = ∞
Reduce the resultant matrix if required.

M2 is already reduced.
Cost of node 2 :

C(2) = C(1) + Reduction cost + M1 [1] [2]

= 25 + 0 + 10 = 35

Select edge 1-3

Set M1 [1][ ] = M1 [ ] [3] = ∞ Set
M1 [3][1] = ∞
Reduce the resultant matrix:

Cost of node 3:

C(3) = C(1) + Reduction cost + M1[1] [3]

= 25 + 11 + 17 = 53

Select edge 1-4:

Set M1 [1][ ] = M1[ ][4] = ∞ Set
M1 [4][1] = ∞
Reduce resultant matrix :

Matrix M4 is already reduced.

Cost of node 4:

C(4) = C(1) + Reduction cost + M1 [1] [4]

= 25 + 0 + 0 = 25

Select edge 1-5:

Set M1 [1] [ ] = M1 [ ] [5] = ∞ Set
M1 [5] [1] = ∞
Reduce the resultant matrix:

Cost of node 5:

C(5) = C(1) + reduction cost + M1 [1] [5]

= 25 + 5 + 1 = 31

State space diagram:

Node 4 has minimum cost for path 1-4. We can go to vertex 2, 3 or 5. Let’s explore all
three nodes.

Select path 1-4-2 : (Add edge 4-2)

Set M4 [1] [] = M4 [4] [] = M4 [] [2] = ∞ Set
M4 [2] [1] = ∞
Reduce resultant matrix :

Matrix M6 is already reduced.

Cost of node 6:

C(6) = C(4) + Reduction cost + M4 [4] [2]

= 25 + 0 + 3 = 28

Select edge 4-3 (Path 1-4-3):

Set M4 [1] [ ] = M4 [4] [ ] = M4 [ ] [3] = ∞ Set
M [3][1] = ∞

Reduce the resultant matrix:

Reduce it by subtracting 11 from column 1.

Cost of node 7:

C(7) = C(4) + Reduction cost + M4 [4] [3]

= 25 + 2 + 11 + 12 = 50

Select edge 4-5 (Path 1-4-5):

Matrix M8 is reduced.
Cost of node 8:

C(8) = C(4) + Reduction cost + M4 [4][5]

= 25 + 11 + 0 = 36

State space tree

Path 1-4-2 leads to minimum cost. Let’s find the cost for two possible paths.
Add edge 2-3 (Path 1-4-2-3):
Set M6 [1][ ] = M6 [4][ ] = M6 [2][ ]
= M6 [][3] = ∞
Set M6 [3][1] = ∞
Reduce resultant matrix:
Cost of node 9:

C(9) = C(6) + Reduction cost + M6 [2][3]

= 28 + 11 + 2 + 11 = 52

Add edge 2-5 (Path 1-4-2-5):

Set M6 [1][ ] = M6 [4][ ] = M6 [2][ ] = M6 [ ][5] = ∞ Set M6
[5][1] = ∞
Reduce resultant matrix

Cost of node 10:

C(10) = C(6) + Reduction cost + M6 [2][5]

= 28 + 0 + 0 = 28

State space tree

Add edge 5-3 (Path 1-4-2-5-3):

Cost of node 11:

C(11) = C(10) + Reduction cost + M10 [5][3]

= 28 + 0 + 0 = 28

State space tree:

NP PROBLEMS:
P – POLYNOMIAL TIME

NP – NON-DETERMINISTIC POLYNOMIAL TIME

P – POLYNOMIAL TIME

• P – the set of all problems solvable in polynomial time by a deterministic Turing

machine (DTM)
  Polynomial on the length of the input string
 Solved in time O(nk )
 This is the class we are most familiar with Includes
sorting, searching, etc.
 Easiest method to prove a problem in P – provide a polynomial
algorithm

NP - NON-DETERMINISTIC POLYNOMIAL TIME:

• NP – the set of all problems solvable in polynomial time by a non- deterministic

Turing machine (NDTM)
– Polynomial on the length of the input string
• Alternatively, the set of all problems for which a solution can be verified
in polynomial time
– Example: Partition

EXAMPLE :
NP VS P:

Tractable Problem: a problem - polynomial-time algorithm. The upper boundis polynomial.

Intractable Problem: a problem - Non- polynomial-time algorithm. The lower bound is

exponential.

Polynomial Reduction:

Reduction : Reduction is a method for solving one problem using another.

NP - HARD

• Every problem in NP is reducible to polynomial time

• A problem in NP-hard if every NP problem can be polynomial reducible

NP Complete

• NP complete problems are problems that live in both NP and NP-Hardclasses

• A problem that is NP-complete can be solved in polynomial time if all other NP-
complete problems can also be solved in polynomial time
Approximation Algorithm for Knapsack problem:

1.Greedy Algorithm for Knapsack problem:

Example: Solve the knapsack problem for the following instance using greedy approach. The item
can be completely selected or skipped completely.