DS Notes

IT-T33 DATA STRUCTURES
Subject Code Subject Name Lectures (Periods) Tutorials (Periods) Practical (Periods)
IT-T33 Data Structures 3 1 0
Course Objectives:
 To introduce the primary data structures and the associated operations
 To understand the applications of data structures with case studies
 To learn the implementation issues of the data structures introduced
Course Outcomes:
On successful completion of this course students will be able to:
 Use appropriate data structures in programming
 Learn various ways of implementing the data structures
Unit-I (10 Periods)
Basics : Abstract Data Type(ADT) – introduction to data structures – representation -
implementation
Stack and list: representing stack – implementation – application – balancing symbols – conversion
of infix to postfix expression – evaluating a postfix expression – recursive function call – Linked list
ADT – implementation using arrays – limitations - linked list using dynamic variables- linked
implementation of stacks – circular list – doubly linked lists
Unit-II (10 Periods)

Queues: Queue abstract data type - Array implementation – circular queue - linked list
implementation of queues – priority queues – double ended queues – multiple stacks and queues -
application.
Unit-III (12 Periods)

Trees : General trees – binary tree – traversal methods – expression trees – game trees. Binary
+
search trees – AVL trees – Splay trees – B Trees – B Trees – Tries – application.
Unit-IV (10 Periods)

Sorting: O notation – efficiency of sorting – bubble sort – quick sort – selection sort – heap sort –
insertion sort – shell sort – merge sort – radix sort.
Unit-V (12 Periods)

Hashing: Introduction – Hash function – methods - Hash table implementation - rehashing.
Graph: Directed and un directed graph – representation of graphs – graph traversals: Depth first
search – Breadth first search – transitive closure – spanning trees – application - topological sorting.
(Total: 54 Periods)
Content beyond Syllabus:
1. Advanced data structures and their implementation.
2. Implementation of the data structures in different language platforms.
Text Books:
th
1. Mark Allen Weiss, Data structures and algorithm analysis in C++, Pearson Education, 6
edition, 2011
2. YedidyahLangsam, Moshe J Augenstein and Aaron M Tanenbaum, Data Structures using C
nd
and C++, 2 edition, Prentice Hall of India, 2009.
Reference Books:
1. G.A.V.Pai, Data Structures and Algorithms – Concepts, Techniques and Applications, Tata
McGraw Hill Publishing Company Limited, New Delhi, 2008.
nd
2. Ellis Horowitz and SartajSahni, Fundamentals of Data structures, Galgotia Publications, 2
Edition, New Delhi, 2001.
3. Alfred V. Aho, Jeffrey D. Ullman, John E. Hopcroft. Data Structures and Algorithms. Addison
Wesley, 1983
Websites:
 http://www.cs.sunysb.edu/~skiena/214/lectures/
 http://opendatastructures.org/
 http://www.cplusplus.com/doc/tutorial/structures/
IT T33- Data Structures
UNIT I
Basics: Abstract Data Type (ADT) - Introduction to Data Structures – Representation –
Implementation
Stack and List: Representation of Stack – Implementation – Application – Balancing Symbols –
Conversion of infix to postfix expression – Evaluating a postfix expression - Recursive function call
– Linked list ADT – Implementation using arrays – Limitations – Linked list using dynamic
Variables – Linked implementation of stacks – Circular list – Doubly Linked List
Objective
 To introduce the primary data structures and their associated operations
 Understand The concepts of linear data structure stack and its applications
 To introduce the concept of different types of linked lists
Outcome:
 Able to use the different types of data structures , stack and linked list
concepts
1.1 Introduction to Data Structures
Data - A collection of facts, concepts, figures, observations, occurrences in a formalized

manner. Example: light, 10, 11.5.
1.1.1 Data Type

A data type is a term which refers to the kind of data that variables may hold in
the programming language. Example:int, float, char,
Types of data types

 Built-in data types
 User defined data types
Built-in data type-The data type which is defined by the programming language itself
is called built-in data type.
Example: int, float, char, etc.
User defined data type-User defined data type can be defined using built in data
types. In other words, using the set of built-in data type user can define their own data
type.
Example:
Array Structure
int regno[10]; typedef struct Stud
float marks[10]; {
char result[20]; int a;
-----
-----;
}s;
SMVEC- Department of Information Technology 1

1.1.2 Data Structures:

Definition 1: A data structure is logical way of storing and organizing data either in
computer's memory or on the disk storage so that it can be used efficiently.
Definition 2 : A data structure is defined as collection of elements and all possible
operations which are required for those set of elements.
1.1.3 Classification of data structure
Fig 1.1 Types of Data Structures
Primary data structure
Primary data structure is the basic data structure that directly operates upon the
machine instruction. They have different representation on different computers.
Example:
8085 8086 Motorola Dual Core
int 2 byte 3 byte 1 byte 4 byte
float 3 byte 4 byte 5 byte 6 byte
Secondary data structure
Secondary data structure are more complicated data structures derived from
primary data structures.
Example: array, structure
Secondary data structure can be classified as:

1. Static Data Structure
2. Dynamic Data Structure
Static data structure (Finite Size Data Structure)

 Static data structure is created using static memory allocation (data structure
form when the number of data items are known in advance).
 The size will be known during the compilation time itself.
Example: array and structure
Dynamic data structure (Variable size Data Structure)

Dynamic data structure is created using dynamic memory allocation (data
structure form when the number of data elements are not known in advance).
Dynamic data structure can be classified as:

1. Linear Data Structure: Have a linear relationship between its adjacent elements.
Example: List
2. Non-Linear Data Structure: Do not have a linear relationship between its adjacent
elements,but have the hierarchical relationship.
Example: Tree
Tree Graph
A tree is a non-linear dynamic data A graph is similar to the tree except that
structure that may point to one or more it has no hierarchical relationship
nodes at a time. between its adjacent elements.
1.1.4 Difference between static and dynamic implementation of data structures
Static implementation of list Dynamic implementation of list

Memory must be allocated continuously. Memory can be allocated anywhere and
are linked together using linked list.
Memory will be wasted. Utilization of Utilization of memory is effective.
memory is poor.
Insertion and deletion operations are time Insertion and deletion operations are not
consuming due to „SHIFT‟ operations. time consuming.
Any element in the list can be accessed Elements can be accessed randomly.
sequentially.
There is a limitation on number of values There is no limitation on number of values
in a list because of fixed size of array. in a list.
Memory is allocated and reallocated for Since the size of the list is known only at
the list at compile time because the size the run time memory allocation and
of the list will be known in compile time reallocation are done at run time only.
only.

1.1.5 Applications of data structure :

 Operating systems.
 Data Base Management System (DBMS).
 Compiler Design.
 Network Analysis
1.2 Abstract Data Type (ADT)

 The Abstract Data Type (ADT) is a set of operations .They are the mathematical
abstractions and define how the set of operations are implemented.
 In Abstract Data Type all the implementation details are hidden.
ADT = Type + Function + Behavior of each function

The ADT is a combination of
„D‟ - Set of domains

„F‟ - Set of functions
„A‟ – Set of axioms in which only what to be done is mentioned but how it
has to be doneis not mentioned
Instances-Instances represent the element on which various operations can be

performed.
Operations- Operations represent basic operation that can be performed on those

elements.
1.2.1 Array ADT
Array is collection of similar data elements in contiguous memory location.

Instance: An array of some size, index i and total number of elements in the array is n.
Operations:
Store() This operation stores the desired element at each successive

location.
Search() This operation searches the specific element from the list of
elements in the array.
Display() This operation displays all the elements in the array.
Sort() This operation arranges the elements in ascending or

descending order of an array.

1.2.2 LISTADT
In a linked list, each element is called a node. Every node in the list points to the
next node inthe list.
Instance: List is an ordered set of elements.

The general form of the list is A1 A2, A3 . . . . . An
A1, - First element of the list

An,- Last element of the list
N - Size of the list If the element at position i is A. then its successor (next) is A i+1 and its
predecessor(previous) is Ai-1.
Operations:
Operations Axioms
createlist() Create an initialized list object.
destroylist() Free the memory allocated for the list.
getdata() Returns the data stored in the current node or index.
getcount() Returns the number of elements in the list.
inserrtfirst() Insert a new element in the first position of the list.
insertintermediate() Insert a new element in any intermediate position of the
list.
insertlast() Insert a new element in the last position of the list.
Note:The list ADT can be used as the building block for many other types of abstract
data type such as STACK ADT and QUEUE ADT.
1.3 Stack ADT

 Stack is a linear data structure in which data is added and removed at only one
end.
 The end from which the elements are added and deleted is referred as the „top’ of
the stack.
 Thus, the last element that is pushed into the stack, is the first element to be
popped out of
the stack, so it is called as Last In First Out (LIFO).
 Stack is also referred as PILES or PUSH down list.
The primary operations that can be carried out on the stack are:
1. PUSH (Insertion)
2. POP (Deletion)
3. PEEK(Display the top of the stack)
4. DISPLAY
Two ways of implementation of Stack:
 Static implementation of stack using array

 Dynamic implementation of stack using linked list
1.3.1 Static Implementation of Stack Using ARRAY
 The simplest way of representing a stack isby single dimensional array.

 In array, the number of elements in the array is fixed, not possible to change the
number of elements through the operation insertion and deletion.
 In stack, the size of the stack varies continuously when elements are pushed and
popped.
 One end of the array (bottom of the stack) is fixed and the other end of the array
(top of the stack) is continuously changed depending upon the elements pushed
or popped in the stack.
1.3.2 Basic Operations
PUSH
 The procedure of inserting a new element to the top of the stack is known as Push
Operation.
 While implementing push the overflow condition is checked to prevent pushing an
element ,when the stack is full
Algorithm push(stack, top, stacksize)

{
if top==stacksize-1
{
write "Stack overflow. Push operation not possible.";
return;
}
read rollno;
top=top+1;
stack[top]=rollno;
}
POP
 The procedure of removing element from the top of the stack is called Pop
Operation
 While implementing the pop operation, the underflow condition is checked to
prevent pop out an element ,when the stack is empty.
Algorithm pop(stack, top, stacksize)
{
if top==-1
{
write "Stack underflow. Pop operation not possible.";
return;
}
write "The element to be deleted.",stack[top];
rollno=stack[top];
top=top-1;
write rollno;
return;
}
PEEK
 Peek operation is used to display the element from the stack pointed by the
point by top.
 While implementing the peek operation, the underflow condition is checked to
prevent peek, when the stack is empty.
Algorithm peek(stack,top)
{
if top==-1
{
write "Stack underflow. Peek operation not possible.";
return;
}
write stack[top];
return;
}
DISPLAY:To read or display the element from the stack, traverse in the stack from top to
0th position.The underflow condition of the stack is to be checked to avoid retrieving an
element from empty stack.
Algorithm display(stack,top)
{
if top=-1
{
write "Stack is in underflow condition. No element to display”
return;
}
for i=top to step-1
{
write stack[top];
}
return;
}

Fig 1.2 Example for Stack Operations
1.4 Dynamic Implementation of Stack Using Linked List
1.4.1 Problems with Array Implementation of Stack:

 The size of the stack must be determined when a stack is declared i.e during
compile time
 Space is wasted if we use less elements
 We cannot "push" more elements than the array can hold
1.4.2 Creating Linked Stack Data Structure:
 Allocate memory for each new element dynamically at run time, the stack can grow
and shrink in size without wasting the memory space.
 Each node in the stack should contain two parts:
o data: the user's data
o next(or) link: the address of the next element in the stack
Structure for Linked Stack Basic operation

struct node 1. PUSH
{ 2. POP
int data; 3. PEEK
struct node *link; 4. DISPLAY
}
Push Operation
Algorithm Push(struct node *top)
{ struct node *newnode;
newnode=new node;
read rollno;
newnode->data=rollno;
newnode->link=NULL;
if top==NULL
{
top=newnode;
}
else
{ newnode->link=top;
top=newnode;
}
return *top;
}

Pop Operation
Algorithm pop(struct node *top)
{
struct node *temp;
if top==NULL
{
write "Stack is in underflow condition. Pop operation is not possible.";
return;
}
temp=top;
top=top->link;
write "Delete rollno.";
delete temp;
}
Peek Operation
Algorithm peek(struct node *top)
{
struct node *temp;
if top==NULL
{
return;
}
write top->data;
return;
}
Display Operation
Algorithm display(struct node *top)
{
struct node *temp;
if top==NULL
{
return;
}
temp=top;
while temp!=NULL
{ write temp->data;
temp=temp->link;
}
return;
}

1.5 Applications of Stack
 Balanced Parenthesis
 Conversion from infix to postfix
 Evaluation of arithmetic expression
 Recursion
1.5.1 Balanced Parenthesis

The balanced parenthesis problem is to determine the set of parenthesis in the
expression or not.
Algorithm for balanced Parenthesis

1. Consider the expression with character and parenthesis (),{},[] to determine if an
expression is balanced or not.
2. For each character that is used to read from the expression, follow the next steps.
3. If the character is an opening parenthesis (,{,[ then push it into the stack.
4. If the character is closing symbol or parenthesis ),},] then check the last entry in the
stack using pop operation and compare the symbol in opening brace list in
corresponding position.
5. If it is matched, repeat the step from 2 until you reach the end of statement.
6. If it is not matched, or if the stack is empty which not reaching the end of
expression, the given expression is unbalanced.
7. If the stack is empty while the end of the expression the given expression is
balanced.
Example Expression: { b [c (d + e)/2 –f ] + 1}
Fig 1.3 Balanced Parenthesis

Example Expression: { 5+ ( 4 [ 3 + 2 ) * 1 ] }, { ( [ ) ] }
Fig 1.4 Unbalanced Parenthesis
1.5.2 Conversion from infix to postfix expression
An expression is string of operators and operands.Operands- Numeric values

Operators- Unary & binary operator
 Unary operator- It includes only single operand (+,-) Eg: +a, -b, b--,++a
 Binary Operator: It includes two or more operands(+,-,*,/) Eg: a+b, a-b*c;
Types of Expression
1. Infix expression: operand1 operator operand2 : a+b
2. Postfix expression: opeand1 operand2 operator: ab+
3. Prefix expression: operator operand1 operand2+ab
Rules which has to be followed while converting infix expression to postfixform :

 The expression is to be read from left to right.
 Read one character at a time from infix expression.
 Make use of stack to store the operators.
 There should not be any parenthesis in the postfix form
1.5.2.1 Algorithmfor Infix to postfix conversion:
Algorithm infix_to_Postfix(instring,poststring)
{
Initially stack is empty;
Initialize the stack;
while(instring!=NULL)
{
ch=get the character from instring;
if(ch==operand)
{
append ch into poststring;
}

else if(ch=='(')
{
pop the data from the stack and append the data into post string
until we get '(' from the stack;
}
else if(ch==operator)
{
while(precedence(top of stack)>=precedence of ch)
{
pop the data from the stack and append into poststring;
}
push ch into stack;
}
}
pop all data from the stack and append into poststring until stack is empty;
}
1.5.2.2Postfix Expression (or) Reverse Polish notation (RPN):

A way of writing mathematical expressions in a format where the operators are
written after the operands; puts expressions in a format that can be used by the interpreter
or compiler.
The advantage of postfix (or) reverse polish notation is that the order of operation
evaluation is unique without the need for precedence rules or parenthesis.The notation is
used because the format that the equation is easier for machines to interpret rather than
the infix notation.
Advantages
 No need for parentheses - avoid ambiguity
 Calculations occur as soon as an operator is specified
 RPN uses a stack. Intermediate results are available for later use
 RPN calculators have no limit on the complexity of the expressions that can be evaluated
 No equals key required for it to be evaluated

Fig 1.5 Infix to Postfix expression
1.5.3 Evaluation of postfix expression

 Scan each term of the expression from left to right
 Use a single stack to hold the operands
 If a term is an operand, push it onto the stack
 If a term is a binary operator, evaluate its result because its two operands are
already on stack on the top positions
 Pop the stack to retrieve the operands
 Evaluate the expression
 Push the result back onto the stack
When it comes to the evaluation of the expression, following rules are used.
 Brackets should be evaluated first.

 The * and / have equal priority, which is higher than + and -.
 All operators are left associative, or when it comes to equal operators, the
evaluation is from left to right.
Example :The total evaluation is as follows.

2 + 3 * (4 – 6 / 2 + 7) / (2 + 3)-(( 4 – 1) * (2 – 10 /2 ))
=2 + 3 * 8 / (2 + 3) - ((4 - 1) * (2 – 10 / 2))
=2 + 3 * 8 / 5 -((4 - 1) * (2 – 10 / 2))
=2 + 3 * 8 /5 -(3 * (2 – 10 / 2))
=2 + 3 * 8 /5 -(3 * (2 - 5))
=2 + 3 * 8 / 5 - (3 * (-3))
=2 + 3 * 8 / 5 + 9
=2 + 24 / 5 + 9
=2 + 4.8 + 9
=6.8 + 9
=15.8
Algorithm for postfix evaluation
Algorithm Evaluate_postfix(poststring)
{ initialize stack;
while(poststring!=NULL)
{
ch=get the character from the poststring;
if ch=operand
{
Read value for ch and push the value into stack;
}
else if(ch=operator)
{
pop the two operands from the stack
perform the arithmetic operation with the operator and
push the result into the stack;
}
}
pop the data from the stack and return popped data;
}
Fig 1.6 Solving Post fix Evaluation : Example :5 3 2 + 8 * +

1.6 Recursive function call

Recursion:Recursion is a technique that breaks a problem into one or more sub-problems
that are similar the original problem.
Recursive function: A recursive function is defined as a function that calls itself to solve a
smaller version of its task until a final call is made which doesn‟t require a call to itself.
Application using Recursion:Tower of Hanoi is one of the main applications of a

recursion. It says that, "if you can solven-1 cases, then you can easily solve the nth case.
 From Fig 1.6 Every program to be executed the main is loaded into a program stack at
the beginning of execution. It remains there until it completes, at which time it is
popped off of the stack.
 If main calls a function, that function is loaded onto the top of the stack and remains
there until it is complete at which point it is popped off of the stack.
 A recursive function calls itself. That means another instance of the function will be
placed on the stack and will remain there until the function completes.
Fig 1.6 Recursion Function Call

1.6.1Example for Recursion function:
int Fact(n) int Fact1(int n, int res)
{ {
if (n==1)
return Fact1(n, 1); return res;
} return Fact1(n-1, n*res);
}
Fig 1.7 Stack representation of recursion: (Calculating the factorial of 4)
1.7 Linked list ADT
1.7.1 Implementation (representation) of LIST ADT
The list can be implemented using two methods:

 Static implementation using array (Array Implementation of List)
 Dynamic implementation using linked list (Linked list representation of List)
Array representation of list (static)

One of the simple ways of representing the list is by means of array. Both lists and
array are ordered collection of elements, but array and list are two different things.
Array
The number of elements in the array is fixed and it is not possible to change the
number of elements in the array because insertion and deletion are not allowed in array.
1.7.2 List using array
 The size of the list varies continuously when the elements are deleted or inserted.
 The list is stored in a part of array. So, an array can be declared large enough to
hold maximum number of elements of a list.
 During the execution of the program, the size of the list can be varied within the
space reserved for it.
 One end of the array is fixed and other end of the array is constantly changed
depending upon the element inserted and deleted in the list.
1.7.3 Basic operations in a LIST using array
1. Creation of the list

2. Insertion
 Insertion of an element in the first position of the list
 Insertion of an element in the intermediate position of the list
 Insertion of an element in the last position of the list
3. Deletion
 Deletion of an element from any position of the list
 Deletion of an element from the last position of the list
4. Searching an element from the list
5. Traversal of a list (Display the elements from the list)
1.7.4 Creation of the List

Algorithm createlist()
{
do
{
top=top+1;
read rollno;
roll[top]=rollno;
read ch;
} while ch=='y';
return;
}
1.7.5 Insertion of an element at last position
Algorithm insertlast()
{
if top==listsize-1 then
{
write "List is full. Insertion is not possible";
return;
}
read rollno;
top=top+1;
roll[top]=rollno;
return;
}

1.7.6 Insertion of an element in the intermediate position
Algorithm intermediate()
{
if top==listsize-1 then
{
write "List is full. Insertion is not possible.";
return;
}
read key;
for i=0 to top
{
if roll[i]==key
{ for j=top to i
{
roll[j+1]=roll[j];
}
}
read rollno;
roll[i]=rollno;
}
top=top+1;
return;
}
1.7.7 Deletion of first element from the list
Algorithm deletefirst(roll,top)
{
if top==-1 then
{
write "List is empty. Deletion is not possible.";
return;
}
del data=roll[0];
for j=1 to top
{
roll[j-1]=roll[j];
}
top=top-1;
write "The data",deldata, "was deleted";
}

1.7.8 Deletion of an intermediate element from the list
Algorithm deleteintermediate(roll,top)
{
if top==-1 then
{
return;
}
read key;
for i=0 to top
{
if roll[i]==key then
{
deldata=roll[i];
for j=i+1 to top
{
roll[j-1]=roll[j];
}
}
}
top=top-1;
write deldata;
}
1.7.9Traversal of the list
Algorithm search(roll,top)
{
if top==-1 then
{
return;
}
read key;
for i=0 to top
{
write roll[i];
}
return;
}
1.7.10 Searching of an element from the given list

Algorithm search(roll,top)
{
if top=-1 then
{
return;
}
read key;

for i=0 to top
{
if roll[i]=key then
{
write "Key exits";
return;
}
}
write "Key does not exists";
return;
}
1.7.11 Modification of an element in the list

Algorithm modify (roll,top)
{
if top=-1 then
{
return;
}
read key;
for i=0 to top
{
if roll[i]=key then
{
read rollno;
roll[i]=rollno;
return;
}
}
write "Key does not exists";
return;
}
Limitations of static or array implementation of list:

 There is a limitation on number of elements in a list because of fixed size of array.
 Insertion and deletion of elements in the list (array) is complicated because it
requires shifting of elements.
 Shifting is a time logic consuming process.
1.8 Linked list representation of List
 A linked list is a linear collection of data elements. These data elements are called
nodes.
 Every node in the list points to the next node in the list.
 Therefore, in a linked list every node contains two types of information:
o Data field - Data field contains actual data of an element to be stored in a
list.
o Link/Address field-It is also referred to as next address field which contains
the address of next node in the list.It is a pointer or link to the next node in
the list.
1.8.1 Three types of Linked List address

 External Address
 Internal Address
 NULL Address
External Address- The address of the first node in the list is the external address. This
address is stored in the header pointer which points to the first node in the list. The
entire link can be accessed only with the help of the header pointer.
Internal Address- Internal address is the address stored in each and every node of the
linked list except the last node.
NULL Address- NULL address is the address stored by the NULL pointer from the last
node of the list which indicates the end point of the list.
1.8.2 Types of linked list

1. Singly Linked List
2. Doubly Linked List
3. Circular Linked List
Singly Linked List(SLL)

 In singly linked list, each node has a single link to its next node. This node is
also referred as a linear linked list.
 In singly linked list, we can traverse the list to only one direction (from head to
NULL pointer in the list). It cannot traverse through the list in the reverse
direction from NULL pointer to the head pointer of the list.
Basic operations in singly linked list
 Creation of a list
 Insertion of a node in a list
o Inserting a first node in the list
o Inserting a last node in the list
o Inserting an intermediate node in the list
 Deletion of a node in a list
 Modification of a node in a list
 Searching a node in a list
 Traverse of a list

1.8.3 Node Representation of Linked List

In the linear linked list the node is divided into two parts, first part contains information field
and the second part holds the address of the next node.
struct node
{ int data;
struct node *next;
} *start =NULL;
Start node
Data Next Data Next Data Next Data NULL
Address of the next node
Fig 1.8 Example of Singly Linked List
1.8.4 Inserting an item:Inserting a new node has three situations:
This operation is used to insert a new node in the linked list at the specified position
1. Insertion at beginning of the list
2. Insertion at middle of the list
3. Insertion at end of the list
1.8.4.1 Insertion at beginning:
- From Fig 1.9 Obtain space for new node
- Assign data to the data field of the new node
- Set the next field of the new node to the beginning of the linked list
- Change the reference pointer of the linked list to point to the new node
Start
Data Next Data Next Data NULL
X Next
p
Fig 1.9 Insert at Beginnning

Algorithm:
Node insertbeg(node *start, int x)
{ p=new node;
p->data=x;
p->next=start;
start=p;
}
1.8.4.2 Insertion at middle:

- From Fig 1.10 Obtain space for new node
- Assign data to the data field of the new node
- Set the next field of the new node to q->next
- Change the reference pointer of the linked list to point to the new node q->next=p.
q
X Next
P
Fig 1.10 Insert at Middle
Algorithm:
Node insertmiddle(node *start, int x)
{
p=new node;
q = start;
while(key != q->data && q != null)
q=q->next;
p->next = q->next;
q->next=p
}
1.8.4.3Insertion at end:
Start q
X NULL
Fig 1.11 Insertion at End P

Algorithm:
Node insertend(node *start, int x)
{
P=new node;
p->data=X;
p->next=NULL;
if(start == NULL)
start=p;
q=start;
while(q->next!=NULL)
q=q->next;
q->next=p
}
1.8.5 Deletion:
This operation is used to delete an item from the linked list. Here we have three situations.
1. Deleting the first item

2. Deleting the last item
3. Deleting the meddle of the list
1.8.5.1 Algorithm for deleting the first item:
1. From Fig 1.11 Store the address of the first node in a pointer variable, say P
p=start
2. Move the head to the next node.
head = head -> next
3. Free the node whose address is stored in the pointer variable P,
free(P).
Start
5 Next 4 Next 7 NULL
P Before Deletion
Start
4 Next 7 NULL
After Deletion
Fig 1.11 Deletion at First
1.8.5.2 Algorithm for Deleting the middle item:
1. From Fig 1.12 Store the address of the preceding node in a pointer variable q. Node
to be deleted is marked as key node.

2. Store the address of the key node in a pointer variable p, so that it can be freed
subsequently.
3. Make the successor of the key node as the successor of the node pointed by q.
q->next = p->next
4. Free the node whose address is stored in the pointer variable p.
free(p)
Start node
Data Next Data Next Data Next Data NULL
q p
Fig 1.12 Deletion at middle
1.8.5.3 Algorithm for Deleting the last item:
If(start->next == NULL)
free(start)
else
q=start;
while(q-> next != NULL)
q=q->next
p=q->next
free(p)
Start node
Data Next Data Next Data Next
q
Data NULL
p
Fig 1.13 Deletion at last
1.8.6 Algorithm to display (or) traverse the elements in a linked list:
q=start;
while(q!=NULL)
write q->data
q=q->next

1.9 Circular Linked List(CLL)

Circular linked list is another form of linked list in which the last node of the list is
connected to the first node in the list. There are 2 types:
 Circular singly linked list

 Circular doubly linked list
Circular linked list looks like a cyclic linked list where there is no null pointer to indicate
the end of the list.
Basic Operations:
1. Insertion
2. Deletion
3. Traversal / Display
A queue data structure can be implemented using a circular linked list with a single pointer
“rear” as the front node can be accessed through the rear node
struct node
{
int data;
struct node *next;
} *start=NULL;
1.9.1 Insertion at end:
Insertion of a node at the start or end of a circular linked list identified by a pointer to the
last node of the linked list takes a constant amount of time.
Start node
Data Next Data Next Data Next Data Next
Address of the
first node
rear P
Fig 1.14 Insertion at end

Algorithm:
If(rear==NULL)
rear=p;
p->next =p;
return p;
else
rear->next = p;
p->next= rear->next;
rear=p;
1.9.2 Insertion at middle:

q start
Data Next
p
Fig 1.15 Insertion at middle
Algorithm:
Node *insert(int *start, int x, intloc)

{
P=new node;
If(start==NULL)
p->next=p
return(p)
q=head->next;
for(i=0; i <loc; i++) //loc is position of qth element
q=q->next;
p->next=q->next;
q->next=p
return(p);
}

1.9.3 Deletion:
q start
p
Fig 1.16 Deletion based on position
Algorithm:
Node *delete (int *head, int x, intloc)

{
If(head==NULL)
write “Underflow”
else If(start->next==start)
free(p);
else
q=head->next;
for(i=0; i <loc; i++) //loc is position of qth element
q=q->next;
p=q->next;
q->next=p->next;
free(p);
}
1.9.4 Display: Algorithm:
display( node *rear)

{
node *p;
if(rear!=NULL)
{
P=rear->next;
do
{
write p->next;
P=p->next;
}while(p!=rear->next);
}
}

1.10 Doubly Linked List(DLL)
For some applications, especially for those where it is necessary to traverse the list in
both direction, doubly linked list works much better than singly linked list. Doubly linked list
is an advanced form of singly linked list in which each node contains three fields:
 Previous Address Field
 Data Field
 Next Address Field
The previous link field contains the address of its previous node. This field is also
referred as backward link field. The data field stores the information part of the node.
The next field contains address of its next node in the list. This field is also referred to
as forward link field.
Basic operations
1. Insert
2. Delete
3. Traverse
One of the most striking disadvantages of these lists is that the inability to traverse the list
in the backward.
In most of the real world applications it is necessary to reverse the list both in
forward direction and backward direction. The most appropriate data structure for such an
application is a doubly linked list.
A double linked list is one in which all nodes are linked together by multiple number
of links which help in accessing both the successor node and predecessor node form the
given node position. It provides bi-directional traversing.
Each node in a double linked list has two linked fields. These are used to point to
the successor node and predecessor nodes. Prev field holds the address of the previous
node and next field holds the address of the nest node.
prev data next
struct node
{
int data;
struct node *prev, *next;
} *start=NULL;

Start node
NULL data next Prev data next Prev data NULL
Fig 1.17 Doubly linked list
1.10.1 Creating a node:

Step 1:From Fig 1.18 Create memory space for the new data
q=new node;
step 2: store x in the newly acquired node
q->data=x;
step 3: make previous and next field as NULL ;
q->prev=NULL; q->next=NULL
Initially start is NULL

P
Start NULL 5 NULL After insertion of 5

Start
P
NULL 5 next Prev 2 NULL After insertion of 2
Fig 1.18 Creation of a node for DLL
1.10.2 Insertion at middle: From Fig 1.19 Insertion and deletion are two basic operations
on such lists. Consider that a new node pointed to by p is to be inserted after the node
pointed to by q in a doubly linked list. Links of two nodes are altered during insertion.
Fig 1.19 Insertion at middle

Start q
NULL 5 next Prev 11 next Prev 6 NULL
Prev 3 next
Start q
NULL 5 next Prev 11 next Prev 3 next Prev 6 NULL
P
Previous link

1.10.3 Algorithm for Insertion at beginning:
insertbeg()
{
p=(node*)malloc(sizeof(node));
p->data=x
p->prev=NULL
p->next=start;
if( start!=NULL)
start ->prev=p;
}
1.10.4 Algorithm for Insertion at end:
insertend()
{
p=(node*)malloc(sizeof(node));
p->data=x
p->next=NULL;
q=start;
while(q->next!=NULL)
q=q->next;
p->prev=q;
q->next=p
}
1.10.5 Deletion of node:
When a node, pointed to by P is to be deleted then its predecessor node x and its
successor node y will be affected.
- Right link at x should be set to y.

- Left link at y should be set to x.
- Release the memory allocated to the node pointed to by p.
Start X Y

Start X Y
P
Fig 1.20 Deletion based on position
p->prev->next=p->next;
p->next->prev=p->prev;
free(p);
1.10.6 Algorithm for display the elements in a linked list:

display()
{ q=start;
while(q!=NULL)
printf(“%d”,q->data)
q=q->next
}
1.11 Polynomial expression representation using linked list:
Polynomials:
One classic example of an ordered list is a polynomial.
Definition:
A polynomial is the sum of terms where each term consists of variable, coefficient and
exponent.
Various operations which can be performed on the polynomial are,
 Addition of two polynomials
 Multiplication of two polynomials
 Evaluation of polynomials
The Polynomial Expression can be represented using Linked list by the following
illustration,
Fig 1.21 Polynomial representation using Linked List

1.11.1 Structure of the polynomial expression linked list
struct list
{
int coef;
int pow;
struct list *next;
};
struct list *p1=NULL,*p2=NULL,*p=NULL;
1.11.2 Creating node for polynomial expression
generate(struct list *node)

{
read node->coef
read node->pow
node->next=(struct list*)malloc(sizeof(struct list));
node=node->next;
node->next=NULL;
}
1.11.3 Addition of two polynomials
add(struct list *p1,struct list *p2,struct list *p)

{
while(p1->next && p2->next)
{
if(p1->pow> p2->pow)
{
p->pow = p1->pow;
p->coef= p1->coef;
p1= p1->next;
}
else if(p1->pow< p2->pow)

{
p->pow=p2->pow;
p->coef=p2->coef;
p2=p2->next;
}

else
{
p->pow=p1->pow;
p->coef=p1->coef+p2->coef;
p1=p1->next;
p2=p2->next;
}
p->next=(struct list *)malloc(sizeof(struct list));
p=p->next;
p->next=NULL;
}
while(p1->next || p2->next)
{
if(p1->next)
{
p->pow=p1->pow;
p->coef=p1->coef;
p1=p1->next;
}
if(p2->next)
{
p->pow=p2->pow;
p->coef=p2->coef;
p2=p2->next;
}
p->next=(struct list *)malloc(sizeof(struct list));
p=p->next;
p->next=NULL;
}
}

Two Marks
1. Define Data Structures (December 2014)(November 2013)
Definition 1:A data structure is logical way of storing and organizing data either in
computer's memory or on the disk storage so that it can be used efficiently.
Definition 2:A data structure is defined as collection of elements and all possible
operations which are required for those set of elements.
2.Define Linear data structure?

Linear data structures are data structures having a linear relationship between its
adjacent elements. Eg.Linked List.
3. Define Non Linear data structure?(December 2014)

Non Linear data structures are data structures don‟t have a linear relationship
between its adjacent elements, but had the hierarchical relationship. Ex. Graph, Tree.
4. Define Linked Lists
Linked list consists of a series of structures, which are not necessarily adjacent
inmemory. Each structure contains the element and a pointer to a structure containing
itssuccessor. We call this theNext Pointer. The last cell‟sNext pointer points to NULL.
5. What are different types of Linked List?

Single linked list
Double linked list
Circular linked list
6 What are different types of Circular Linked List?(April 2015)

Circular Single linked list
Circular double linked list
7. List the basic operations carried out in a linked list
The basic operations carried out in a linked list include:

• Creation of a list
• Insertion of a node
• Deletion of a node
• Modification of a node
• Traversal of the list
8. List out the advantages of using a linked list
 It is not necessary to specify the number of elements in a linked list during its
declaration
 Linked list can grow and shrink in size depending upon the insertion and deletion
that occurs in the list
 Insertions and deletions at any place in a list can be handled easily and efficiently
 A linked list does not waste any memory space
9. List out the disadvantages of using a linked list
 Searching a particular element in a list is difficult and time consuming

 A linked list will use more storage space than an array to store the same number of
elements
10. List out the applications of a linked list (December 2014)
Some of the important applications of linked lists are manipulation of polynomials,

sparse matrices, stacks and queues.
11. State the difference between arrays and linked lists (November 2013)
Arrays Linked Lists
Size of an array is fixed Size of a list is variable
It is necessary to specify the number of It is not necessary to specify thenumber

elements duringdeclaration. of elements duringdeclaration
Insertions and deletions are Insertions and deletions are carried
somewhat difficult out easily
It occupies less memory than alinked list It occupies more memory
for the same number ofelements
12. Define a stack
Stack is an ordered collection of elements in which insertions and deletions are

restricted to one end. The end from which elements are added and/or removed is referred
to as top of the stack. Stacks are also referred as piles, push-down lists and last-in-first-
out (LIFO) lists.
13. List out the basic operations that can be performed on a stack (December 2014)
The basic operations that can be performed on a stack are
• Push operation
• Pop operation
• Peek operation
• Empty check
• Fully occupied check

14. State the different ways of representing expressions
The different ways of representing expressions are
• Infix Notation
• Prefix Notation
• Postfix Notation
16. State the rules to be followed during infix to postfix conversions (December
2014)
Rules which has to be followed while converting infix expression to postfix form :
• The expression is to be read from left to right.
• Read one character at a time from infix expression.
• Make use of stack to store the operators.
• There should not be any parenthesis in the postfix form
17. State the difference between stacks and linked lists
The difference between stacks and linked lists is that insertions and deletions may
occur anywhere in a linked list, but only at the top of the stack
18. Mention the advantages of representing stacks using linked lists than arrays
• It is not necessary to specify the number of elements to be stored in a stackduring

its declaration, since memory is allocated dynamically at run timewhen an element
is added to the stack
• Insertions and deletions can be handled easily and efficiently
• Linked list representation of stacks can grow and shrink in size withoutwasting
memory space, depending upon the insertion and deletion that occursin the list
• Multiple stacks can be represented efficiently using a chain for each stack
19. What is the data structures used to perform recursion?
Stack. Because of its LIFO (Last In First Out) property it remembers its „caller‟ so
knows whom to return when the function has to return. Recursion makes use of system
stack for storing the return addresses of the function calls. Every recursive function has its
equivalent iterative (non-recursive) function. Even when such equivalent iterative
procedures are written, explicit stack is to be used.
20. Define an Abstract Data Type (ADT) (Apr 2015)(Nov 2015)(May 2014)(December
2014)
An abstract data type is a set of operations. ADTs are mathematical abstractions;In

ADT‟s definition ,implementation of operations is not mentioned. Objects such as lists,
sets and graphs, along with their operations can beviewed as abstract data types.
21. What are the advantages of modularity?
• It is much easier to debug small routines than large routines

• It is easier for several people to work on a modular program simultaneously
• A well-written modular program places certain dependencies in only one
 routine, making changes easier
22. What are the objectives of studying data structures?
 To identify and create useful mathematical entities and operations todetermine what
classes of problems can be solved using these entities andoperations
 To determine the representation of these abstract entities and to implement the
abstract operations on these concrete representation
23. List the applications of stacks (November 2015)
• Towers of Hanoi
• Reversing a string
• Balanced parenthesis
• Recursion using stack
• Evaluation of arithmetic expressions
24. Why we need cursor implementation of linked lists?
Many languages such as BASIC and FORTRAN do not support pointers. If linkedlists
are required and pointers are not available, then an alternative implementation mustbe
used known as cursor implementation.
25. List the applications of set ADT.
• Maintaining a set of connected components of a graph

• Maintain list of duplicate copies of web pages
• Constructing a minimum spanning tree for a graph

Assignment Questions
1. Write a program to convert an infix expression that includes (, ), +, -, *, and / to

postfix.
2. Write a routine to solve the towers of Hanoi problem. The conditions are
 You can move only one disk at a time.
 For temporary storage, a third pole may be used.
 You cannot place a disk of larger diameter on a disk of smaller diameter.
3. Write an array implementation of self-adjusting lists. In a self-adjusting list, all

insertions are performed at the front. A self-adjusting list adds a find operation, and
when an element is accessed by a find, it is moved to the front of the list without
changing the relative order of the other items.
4. Write a routine to perform polynomial addition using singly linked list.
5. Write a routine to maintain the singly linked list in sorted order.

UNIT II
Queues: Queue abstract data type - Array implementation – circular queue - linked list
implementation of queues – priority queues – double ended queues – multiple stacks and
queues - application
Objective:
 To introduce and understand the concept of queue and its operations
 To understand the application of queues
Outcome:
 Able to apply the queue data structures in programming
2.1 Queue- Abstract Data type

A Queue is an ordered collection of items from which items may be deleted at one
end called the front of the queue and into which items may be inserted at the other end
called rear of the queue. Queue is called as First –in-First-Out (FIFO).The primary
operation that can be done on a queue are(Fig 2.1):
 Enqueue (Insert)-adds a new element in the queue, this process is carried out
by incrementing the rear end and adding the new element in the rear position.
 Dequeue(Delete)-delete an element from the queue, this process is carried out
by incrementing the front end and deleting the element a front end position.
Fig 2.1 Queue

Types of queue
1. Linear Queue
2. Circular Queue
3. Double ended queue
4. Priority Queue
2.1.1 Linear queue

Linear queue is an ordered collection of items from which items may be deleted at
one end called the front of the queue and into which items may be inserted at the other
end called rear of the queue. Queue is called as First –in-First-Out (FIFO).
2.1.2 Circular Queue
Circular Queue is the another form of linear queue in which last position is connected
to the first position of the queue. Circular queue also has two ends:-
 Front
 Rear
The front end is where we delete element and the rear end is where we insert element.
The next position of the rear is front, then the queue is said to be fully occupied.
2.1.3 Double Ended Queue

In double ended queue, insertion and deletion are made at both rear and front end of the
queue. They are two variations of deque.
 Input restricted Dequeue -Insertion can be done only at one of the dequeue,while
deletion can be done on both ends
 Output restricted dequeue - deletion can be done only at one of the
dequeue,while insertion can be done on both ends
Types of dequeue
1. Linear dequeue
2. Circular dequeue
Linear Dequeue
It is similar to the linear queue except the following conditions:
 If the front pointer is in the first position (zeroth position), we can’t insert data at
front end.
 If the rear is in the last position (queuesize-1) we can’t insert data at rear end.
Circular Dequeue
Circular dequeue is similar to circular queue except the following conditions:
 Insertion and deletion are made at front and rear end of the queue.Irrespective of
the position of the front and rear we can insert and delete
2.2 Static implementation (Representation) of linear queue using Array
Representation of linear queue

1. Array representation of queue [Static implementation of queue]
2. Linked list representation of queue [Dynamic implementation of queue]
Array representation of queue

One of the simplest ways of representing a queue is by means of single
dimensional array.
Basic operations
1. Enqueue
2. Dequeue
3. Display

 Initially the front end and the rear end are at the same position (-1).
 The rear pointer is in the last position (size-1) then queue is said to be full, if front
pointer is (-1) then the queue is empty.
 When you insert elements, rear pointer moves one by one until the last position
is reached.
 When we delete elements, the front pointer moves one by one until the rear
pointer is reached.
2.2.1 Enqueue
Algorithm Enqueue(queue,rear,front,queuesize)
{
if rear==queuesize-1
{
write "queue is in overflow condition. Thus enqueue operation is not possible.";
return;
}
if rear==-1 and front==-1
{
rear=front=0;
}
else
{
rear=rear+1;
}
read rollno;
queue[rear]=rollno;
}
2.2.3 Dequeue
Algorithm Dequeue(queue,rear,front,queuesize)
{
if front==-1 || front>rear
{
write "queue is in underflow condition. Thus dequeue operation is not
possble.";
return;
}
if rear==front
{
rear=front=-1;
}
else
{
front=front+1;
}
}

2.2.4 Display
Algorithm display(queue,front,rear)
{
if front==-1 || front>rear
{ write "Queue is in underflow condition. Display operation is not possible.";
return;
}
for i=front to rear
{
write queue[i];
}
return;
}
2.3 Dynamic implementation(Representation) of Linear queue using Linked List

Each element is represented as node. The node is represented in two fields.
 Data
 Link Field
Since, the node contains collection of two different data, it is defined as structure.
struct node
{
int data;
struct node *link;
}*front=NULL,* rear=NULL;
2.3.1 Enqueue
Algorithm enqueue(struct node *front, struct node *rear)
{
struct node *newnode;
newnode=new node;
read rollno;
newnode->data=rollno;
newnode->link=NULL;
if front==NULL and rear==NULL

{
front=newnode;
rear=newnode;
}
else
{
rear->link=newnode;
rear=newnode;
}
return;
}

2.3.2 Dequeue
Algorithm dequeue(struct node *front, struct node *rear)
{
struct node *temp;
{
write "Queue is in underflow condition. Dequeueoperaation is not possible.";
return;
}
if front==rear
{
front=rear=NULL;
}
else
{
front=front->link;
}
delete temp;
return;
}
2.3.3 Display
Algorithm display(struct node *front, struct node *rear)
{
struct node *temp;
{
write "Queue is in underflow condition. Dequeueoperaation is not possible.";
return;
}
temp=front;
while(temp!=front)
{
write temp->data;
temp=temp->link;
}
return;
}
Applications of Queue:
o When a resource is shared among multiple consumers. Examples include CPU scheduling,
Disk Scheduling.
o When data is transferred asynchronously (data not necessarily received at same rate as sent)
between two processes. Examples include IO Buffers, pipes, file IO, etc.

2.4 Circular Queue
Circular queue also has two ends:-
 Front
 Rear
Fig 2.2 Circular Queue

Circular Queue
 From Fig 2.2 When a new item is inserted at the rear, the pointer to rear moves
upwards.
 When an item is deleted from the queue the front arrow moves downwards.
 After a few insert and delete operations the rear might reach the end of the queue and
no
 More items can be inserted although the items from the front of the queue have been
deletedand there is space in the queue.
Concept of Circular Queue:

There is a formula which has to be applied for setting the front and rear pointers, for a
circular queue.
Circular Queue Empty: Front=Rear=0.

Basic operations
 Enqueue
 Dequeue
 Display
2.4.1 Enqueue
Algorithm enqueue(queue,front,rear,queuesize)
{
if (rear+1)%queuesize==front
{
write "Queue is in overflow condition. Enqueue operation is not possible.";
return;
}
read rollno;
if front=-1 and rear=-1
{
front=rear=0;
}
else
{
rear=(rear+1)%queuesize;
}
queue[rear]=rollno;
return;
}
2.4.2 Dequeue
Algorithm dequeue(queue, front, rear, queuesize)
{
if front==-1 and rear==-1
{
write "Queue is in underflow condition. Dequeue operation is not possible.";
return;
}
write "The element to be deleted",queue[front];
if front==rear
{
front=rear=-1;
}
else
{
front=(front+1)%queuesize;
}
return;
}
2.4.3 Display
Algorithm display(queue, front, rear, queuesize)
{
{
write "Queue is in underflow condition. Dequeue operation is not possible."
return;
}
i=front;
while(i!=rear)
{
write queue[i];
i=(i+1)%queuesize;
}
write queue[rear];
return;
}

2.5 Priority Queue (or) Application of Queue

Application of queue
 Direct applications
o Access to shared resources (e.g., printer)
o Multiprogramming
 Indirect applications
o Priority queue
o Auxiliary data structure for algorithms
o Component of other data structures
Priority queue
Priority queue is a data structure having collection of elements which are associated
with specific order. They are of two types:
 Ascending Priority Queue- It is a collection of elements in which the insertion
of element can be any order, but only the smallest element can be
removed.
 Descending Priority Queue- It is a collection of elements in which the
insertion of element can be any order, but only the largest element can be
removed.
 The priority queue elements are arranged in any order and out of which only the
smallest or largest element allowed to be deleted each time.
 The implementation of priority can be done by using array and linked list. The data
structure heap is used to implement priority queue efficiently.
Fig 2.3 Priority Queue
Basic Operations
 Enqueue
 Dequeue
2.5.1 Enqueue
Algorithm enqueue(pqueue,front,rear,queuesize,num,prno)
{
if rear==queuesize-1;
{
write "Queue is in overflow condition. Enqueue is not possible.";
return;
}

read num;
read pno;
I if rear==-1
{
rear=rear+1;
front=front+1;
}
else
{
rear=rear+1;
}
pqueue[rear].data=num;
pqueue[rear].pno=prno;
}
2.5.2 Dequeue
Algorithm dequeue(pqueue,front,rear,max=0,pos=0)
{
if front=-=1
{
write "Queue is in underflow condition. Dequeue operation is not possible.";
return;
}
if front==rear
{
front=rear=-1;
}
else
{
for(i=front to i<=rear)
{
if pqueue[i].pno>max
{
max=pqueue[i].pno;
pos=i;
}
}
for (i=pos to i<=rear)
{
pqueue[i].data=pqueue[i+1].data;
pqueue[i].pno=pqueue[i+1].pno;
}
}
}

2.6 Double Ended Queue (DEQUE)
In double ended queue, insertion and deletion are made at both rear and front end
of the queue.
Fig 2.4 Double Ended Queue
They are two variations of dequeue.

 Input restricted Dequeue -Insertion can be done only at one of the dequeue,while
deletion can be done on both ends
Fig 2.4 Input Restricted Dequeue

 Output restricted Dequeue - deletion can be done only at one of the
dequeue,while insertion can be done on both ends
Fig 2.5 Output Restricted Dequeue

Types of deque
 Linear dequeue
 Circular dequeue
Linear Deque
It is similar to the linear queue except the following conditions:
 If the front pointer is in the first position (zeroth position), we can’t insert data at
front end.
 If the rear is in the last position (queuesize-1) we can’t insert data at rear end.
Circular Deque
Circular deque is similar to circular queue except the following conditions:
 Insertion and deletion are made at front and rear end of the queue.
 Irrespective of the position of the front and rear we can insert and delete he data.

2.6.1 Enqueue– Front

Algorithm enqueue (queue, front,rear,queuesize)
{
if front=0
{
write "Queue is in overflow condition. Enqueue is not possible.";
return;
}
{
front=rear=queuesize-1;
}
else
{
front=front-1;
}
read rollno;
queue[front]=rollno;
return;
}
2.6.2 Enqueue – rear
Algorithm enqueue (queue, front,rear,queuesize)
{
if front=0
{ write "Queue is in overflow condition. Enqueue is not possible.";
return;
}
{
front=rear=0;
}
else
{
rear=rear+1;
}
read rollno;
queue[rear]=rollno;
return;
}
2.6.3 Dequeue – front
Algorithm dequeue(queue,front,rear)
{
if rear=-1 and front=-1
{ write "Queue is in underflow condition. Dequeue is not possible.";
return;
}
write "Element to be deleted",queue[front];

if front=rear
{
front=rear=-1;
}
else
{ front=front+1;
}
return;}
2.6.4 Dequeue – rear
Algorithm dequeue(queue,front,rear)
{
if rear=-1 and front=-1
{
write "Queue is in underflow condition. Dequeue is not possible.";
return;
}
write "Element to be deleted",queue[front];
if front=rear
{
front=rear=-1;
}
else
{
rear=rear-1;
}
return;
}
2.7 Multiple Stacks and Queues in detail
2.7.1 Multiple Stacks:
When a stack is created using single array, we cannot able to store large amount of
data, thus this problem is rectified using more than one stack in the same array of
sufficient array. This technique is called as Multiple Stack.
When an array of STACK[n] is used to represent two stacks, say Stack A and Stack
B. Then the value of n is such that the combined size of both the Stack[A] and Stack[B] will
never exceed n. Stack[A] will grow from left to right, whereas Stack[B] will grow in opposite
direction ie) right to left.
 Here only one single one-dimensional array (Q) is used to store multiple stacks.
 B (i) denotes one position less than the position in Q for bottommost element of
stacks i.
 T (i) denotes the top most element of stack i.
 m denotes the maximum size of the array being used.
 n denotes the number of stacks.
We also assume that equal segments of array will be used for each stack.
Initially let B (i) = T (i) = [m/n]*(i-1) where 1<= i <= n.
Again we can have push or pop operations, which can be performed on each of these
stacks .
Algorithm for Push operation

Push (i, x)
{
If (((i<n) && (T(i)==B(i+1)) || ((i>=n) && (T(i) ==m)));
{
Then call STACK_FULL ;
}
Else
{
T(i) = T(i) + 1;
Q[T(i)] = x ;
}
}
Algorithm for Pop Operation

Pop (i,x)
{
if ( T(i) = = B(i) )
{
Then print that the stack is empty.

}
Else
{
x = Q[T(i)];
T[i] = T[i] – 1;
}
}

2.7.2 Multiple Queues:

 Problems with the queues represented with arrays are:
 We have to allocate large space to avoid the overflow.
 Large space will be wasted due to less size of queue.
 There exists a trade-off between the number of overflows and the space.
 One possibility to reduce this tradeoff is to represent more than one queue in the
same array of sufficient size
 Free elements could be anywhere in the Queue such as before the front, after the rear,
and between front and rear in the Queue
 Queue 1’s and Queue 2 ‘s size could be change if it is necessary. When the Queue 1
is full and the Queue 2 has free space; the Queue 1 can increase the size to use that
free space from the Queue 2. Same way for the Queue 2
Insertion and deletion of Multiple Queue
 Inserts data to the Queue 1,

Q1Rear = (Q1Front + Q1count) % Q1Size
 Inserts data to the Queue 2,

Q2Rear = (Q2Front + Q2count) % Q2Size + Q1Size
 Deletes data from the Queue 1,

Q1Front = (Q1Front + 1) % Q1Size
 Deletes data from the Queue 2,

Q2Front = (Q2Front + 1) % Q2Size + Q1Size

Two Marks
1. Define a queue
Queue is an ordered collection of elements in which insertions are restricted toone
end called the rear end and deletions are restricted to other end called the front
end.Queues are also referred as First-In-First-Out (FIFO) Lists.
2. Define a priority queue (April 2015)(November 2015)(November 2013)
Priority queue is a collection of elements, each containing a key referred as
thepriority for that element. Elements can be inserted in any order (i.e., of
alternatingpriority), but are arranged in order of their priority value in the queue. The
elements aredeleted from the queue in the order of their priority (i.e., the elements with the
highestpriority is deleted first). The elements with the same priority are given equal
importanceand processed accordingly.
3. State the difference between queues and linked lists

The difference between queues and linked lists is that insertions and deletionsmay
occur anywhere in the linked list, but in queues insertions can be made only in therear end
and deletions can be made only in the front end.
4. Define a Deque or Double ended queue (April 2015)(May 2014)(November 2013)

Deque (Double-Ended Queue) is another form of a queue in which insertions
anddeletions are made at both the front and rear ends of the queue.
There are two variationsof a deque, namely, input restricted deque and output
restricted deque. The inputrestricted deque allows insertion at one end (it can be either
front or rear) only. The output restricted deque allows deletion at one end (it can be either
front or rear) only.
5. What are the types of queues?

• Linear Queues
• Circular Queues
• Double-Ended-Queue
6. What is linear queue?

The queue has two ends, the front end and the rear end. Therear end is where we
insert elements and front end is where we deleteelements. We can traverse in a
linear queue in only one direction ie) fromfront to rear.
7. What is Circular queue?(November 2015)

Another form of linear queue in which the last position isconnected to the first
position of the list. The circular queue is similar to linearqueue has two ends, the front end
and the rear end. The rear end is where weinsert elements and front end is where we
delete elements. We can traverse ina circular queue in only one direction ie) from front to
rear.
9. List the applications of queues

 Serving requests of a single shared resource like (printer, disk, CPU), between two
processes
 Job Scheduling
 Used in multitasking operating System
 Categorizing of data
 Simulation and Modeling
10. What are the applications of priority queues?
• The selection problem

• Event simulation
11. List out the difference between Linked stack and Linked Queue.
Stack Queue
Stack is a collection of items Queue is an ordered collection of items

Items are inserted & deleted at one end Items are deleted at one end called ‘front’
called end of the queue.
‘Top of the stack’. Items are inserted at other end called
‘rear’ of the queue.
It allows access to only one data item: the The first item inserted is the first to be
last item inserted. removed (FIFO).
This structure of accessing is known as This structure of accessing is known as
Last in First in First out structure (FIFO)
First out structure (LIFO)

Assignment questions
1. Efficiently implement a queue class using a circular array. You may use a vector
(rather than a primitive array) as the underlying array structure.
2. Design a data representation sequentially mapping n queues into an array M
[m]. Represent each queue as a circular queue within M. Write functions Add,
Delete, and QueueFull for this representation.
3. Write routines to implement two stacks using only one array. Your stack routines
should not declare an overflow unless every slot in the array is used.
4. Obtain a data representation mapping a stack s and a queue q into a single array M
[n]. Write algorithms to add and delete elements from these two data objects. What
can you say about the suitability of your data representation?
5. Write a routine for implementing the priority queue?

UNIT III
Trees : General trees – binary tree – traversal methods – expression trees – game trees.
Binary search trees – AVL trees – Splay trees – B Trees – B+ Trees – Tries – application.
Objective:
 To learn the concept and application of different varieties of tree data structure
Outcome:
 Able to implement the tree data structure in programming
3.1 General Trees

3.1.1. Definition of Tree
A tree is a collection of nodes. The collection can be empty .Otherwise a tree
consists of distinguished node r called the root and zero or more non empty sub-trees
T1,T2,T3…………….Tk each of whose roots are connected by a directed edge from r.
Fig 3.1 General Tree
 There is one specially designated node called ROOT.

 The remaining nodes are partitioned into a collection of sub-trees of the root each of
which is also a tree.
3.1.2 Basic Terminology of tree:

Node (Vertex, Edge)
 Main component of a tree structure
 Stores data and links to other nodes
Edge - connection between one node to another.
Root - the top most node in a tree.
Parent - node that has a child.
Siblings - nodes with the same parent.

Leaves - nodes with no children.
Internal nodes - nodes with at least one child.
Degree - number of sub trees of a node.
Level - The level of a node is defined by 1 + the number of connections between the
node and the root
Height - The height of a node is the length of the longest downward path between the
node and a leaf
Forest- A set of disjoint trees
External nodes -A node that has no children is called as a terminal node
Fig 3.2 Tree Terminologies
Properties of a Tree
 Any node can be the root of the tree and each node in a tree has the property that
there is exactly one path connecting that node with every other node in the tree.
 The tree in which the root is identified is called a rooted tree; a tree in which the
root is not identified is called a free tree.
 Each node, except the root, has a unique parent.
3.2 Binary Tree:
 From Fig 3.3 Finite collection of elements / nodes that is either empty or partitioned
into three disjoint subsets.
 The first subset is termed as the root element.
 The remaining elements (if any) are partitioned into two binary trees.
 These are called the left and right sub-trees of the binary tree.

Fig 3.3 Binary Tree

Properties of Binary Trees:
Property 1: Each node can have up to two successor nodes.
Property 2:A unique path exists from the root to every other node.
Full binary tree: A full binary tree (2-tree or strictly binary tree) is a tree in which every
node other than the leaves has two children.
Fig 3.4 Full Binary Tree
Complete binary tree: The binary tree in which every level, except possibly the last, is
completely filled, and all nodes are as far left as possible
Fig 3.5 Complete Binary Tree

Strictly binary tree: If every non-leaf node in a binary tree has non-empty left and right
sub-trees,
Height-balanced Binary Tree:
 A height-balanced binary tree is a binary tree such that, the left & right sub trees
for any given node differ in height by no more than one
 Note: Each complete binary tree is a height-balanced binary tree
Fig 3.6 Height Balanced and Not Height Balanced Binary tree
Extended Binary tree:
 From Fig 3.7 ,A binary tree T is said to be an extended binary tree if each node in
the tree has either no child or exactly two children.
 In extended binary tree, node having two children are called internal node, and node
without children are called as external node.
Fig 3.7 Binary Tree and Extended Binary Tree
In-degree and Out-degree In binary tree:
Degree: The degree of node is equal to number of children that a node has.
In-degree: The number of edges arriving at that node .The root node is the only node
that has in-degree as zero
Out-degree: The number of edges leaving that node
Balancing factor in binary tree:The balance factor of a binary tree is the difference in
height between its left and right sub trees:
B  HL  HR

Searching in a binary tree:
 Start at the root
 Search the tree level by level, until you find the element you are searching for or
you reach a leaf.
 Time Taken for searching binary tree is O(N),which is not efficient
3.2.1 Representation of Binary Trees.

 Linear representation or Array representation
 Linked list representation
Linear representation or Array representation:

 The linear representation method of implementing a binary tree uses a one
dimensional array of size (2h+1)-1.
 Once the size of the array has been determined the following method is used to
represent the tree.
1. Store the root in 1st location of the array.
2. The left child of the nth node is stored at location 2n, and the right child of
the nth node is stored at location 2n+1.
3. If there is no left or right child , the array location is left empty.
Location 0 of the array can be used to store the size of the tree in terms of total number of
nodes.
Example
Fig 3.8 Linear representation of Tree
 All non-existing children are show by \0.

 Index of the left child of a node n= 2*n
 Index of the right of a node n=2*n+1
 Index of the parent of a node i=i/2.

Advantages
 Given a child node, its parent node can be determined immediately. If a child node is at
location N in the array, then its parent is at location N/2.
 It can be implemented easily in languages in which only static memory allocation is
directly available.
Disadvantages
 Insertion or deletion of a node causes considerable data movement up and down the
array, using an excessive amount of processing time.
 Wastage of memory due to partially filled trees.
Linked list representation:
The advantage of using linked representation of binary tree is that insertion and deletions
involve no data movement of nodes except the rearrangement of pointers.
Disadvantage of linked representation of binary trees.
 Given a node structure, it is difficult to determine its parent node.

 Memory spaces are wasted for storing NULL pointers for the nodes, which have one or
no sub-tree.
 This implementation requires dynamic memory allocation which is not possible in some
programming language.
A node of a binary tree consists of the three fields as shown below.

 Data Typedef struct node
 Address of Left Data Right {
the left child int data;
 Address of struct node *left;
the right child struct node *right;
}node;
Left Data Right
Left Data Right Left Data Right
Left Data Right
Fig 3.9 Linked List representation of binary tree

3.3 Traversals in binary tree:
In a traversal of a binary tree, each element of the binary tree is visited exactly
once. During the visit of an element, all action(searching for particulars nodes, compilers
commonly build binary trees in the process of scanning, parsing, generating code and
evaluation of arithmetic expression)with respect to this element is taken. The various
traversals in binary tree are:
 In-order Traversal (Left, Parent, Right)

 Preorder Traversal (Parent, Left, Right)
 Post-order Traversal (Left, Right, Parent)
 Level Order Traversal (Top to Bottom, Left to Right)
Fig 3.10 Tree Traversal Methods

Structure of the Node :
struct node
{
int info;
struct node *lchild;
struct node *rchild;
} struct node NODE;
3.3.1 Inorder Traversal (Left-Root-Right)

In this traversal, if T is not empty, the following steps followed;
Steps : void inorder_traversal ( NODE * T)
1. Traverse left subtree in inorder {
2. Process root node if( T ! = NULL)
3. Traverse right subtree in { inorder_traversal(T->lchild);
inorder Write T->info;
inorder_traversal(T->rchild);
}
}

Consider the binary tree given in the following figure.

-
+ *
A * D E
B C
Fig 3.11 Expression Tree- (A+B*C)-(D*E)

A binary tree can be used to represent arithmetic expressions if the node value can be
either operators or operand values and are such that
 Each operator node has exactly two branches.
 Each operand node has no branches; such trees are called expression trees.
Form the Fig 3.11 ,Tree T at the start is rooted at ‗-‗;

 Since left(T) is not empty; current T becomes rooted at ‗+‘;
 Since left(T) is not empty; current T becomes rooted at ‗A‘;
 Since left (T) is empty; we visit root i.e. A.
 We access T root i.e. ‗+‘.
 We now perform in-order traversal of right (T) current T becomes rooted at ‗*‘.
 Since left(T) is not empty; current T becomes rooted at ‗B‘ since left(T) is empty; we
visit it to root i.e. B; cluck for right (T) which is empty, therefore we move back to parent
tree. We visit its root i.e. ‗*‘.
 Now Inorder traversal of right (T) is performed; which would give us‗C‘. We visit T‘s root
i.e., ‗D‘ and perform in-order traversal of right (T); which would give us ‗* and E‘.
The final listing is A+B*C-D*E. We may note that expression is in infix notation.

Fig 3.12 Inorder Traversal Example
3.3.2 Preorder traversal(root-left-right)

Steps : void preorder_traversal ( NODE * T)
1. Process root node {
2. Traverse left subtree in preorder if( T ! = NULL)
3. Traverse right subtree in preorder {
write T->info;
preorder_traversal(T->lchild);
preorder_traversal(T->rchild);
}
}
From the Fig 3.11

 Since it visits the root first , it is displayed i.e. ‗-‗ is displayed
 Next left traversal is done. Here the current T becomes rooted at ‗+‘
 Since left(T) is not empty; current T becomes rooted at A
 Since left (T) is empty we visit right (T) i.e. ‗*‘ and T is rooted here.
 Since left (T) is not empty , current T gets rooted at B
 Since left (T) is empty, we visit right (T) i.e. ‗C‘ and T is at present rooted here
 Since left (T) is empty and no right (T) we move to the root ‗*‘
 Visit root ‗+‘
 Now the left sub tree is complete so we move to right sub tree i.e. T is rooted at ‗*‘
 Since left (T) is not empty , current T becomes rooted at D
 Since left (T) is empty, T gets rooted at right (T) i.e. E.
Thus the complete listing is -+A*BC*DE.We may note that expression is in prefix
notation.

Fig 3.13 Preorder Traversal Example
3.3.3 Postorder Traversal( Left-Right-Root):

Steps : void postorder_traversal ( NODE * T)
1. Traverse left subtree in postorder {
2. Traverse right subtree in postorder if( T ! = NULL)
3. process root node {
postorder_traversal(T->lchild);
postorder_traversal(T->rchild);
write T->info;
}
}
From Fig 3.11
 Tree, T, at the start is rooted at ‗-‗ ;
 Since left (T) is not empty ; current T becomes rooted at ‗+‘;
 Since left (T) is not empty ; current T becomes rooted at ‗A‘;
 Since left (T) is empty ; we visit right (T) ‗*‘
 Since Right (T) is empty ; we visit root i.e. A
 We access right T‘s root it *
 Since left (T) is not empty ; we visit right (T)
 Since right (T) is empty we visit root i.e., B
 Since right (T) is not empty ; current T becomes rooted at ‗C‘
 Since left (T) & right (T) is empty , we visit root i.e. ‗C‘
 Visit root i.e. ‗*‘
 Visit root i.e., ‗+‘
 Since right (T) is not empty ; current T becomes rooted at ‗*‘
 Since left (T) is not empty ; current T becomes rooted at ‗D‘
 Since left (T) and right (T) are empty we visit root i.e., ‗D‘
 Since right (T) is not empty ; current T becomes rooted at ‗E‘.
 Since left (T) & right (T) are empty ; we visit root i.e., ‗E‘
 Visit root is ‗*‘
 Visit root is ‗-‗
Therefore, the complete listing is ABC*+DE*- . We may note that expression is in
postfix notation.
Fig 3.14 Post order Traversal Example
3.4 Expression Tree

A binary tree can be used to represent arithmetic expressions if the node value can
be either operators or operand values and are such that
 Each operator node has exactly two branches.
 Each operand node has no branches; such trees are called expression trees.
Construction of expression tree

For constructing expression tree we use a stack. We loop through input expression and do
following for every character.
 If character is operand push that into stack.
 If character is operator pop two values from stack make them its child and push
current node again.
 At the end only element of stack will be root of expression tree.
Example: The input is: a b + c d e + * *

1. Since the first two symbols are operands, 2.The next symbol is a '+'. It pops the two
one-node trees are created and pointers are pointers to the trees, a new tree is formed,
pushed to them onto a stack. For and a pointer to it is pushed onto the
convenience the stack will grow from left to
right.

stack.
3.Next, c, d, and e are read. A one-node 4.Continuing, a '+' is read, and it merges the
tree is created for each and a pointer to the last two
corresponding tree is pushed onto the
trees.
stack
5. Now, a '*' is read. The last two tree 6.Finally, the last symbol is read. The two
pointers are popped and a new tree is trees are merged and a pointer to the final
formed with a '*' as the root tree remain on the stack
3.5 Game Trees

 General trees prove to be a useful strategy for planning moves in a game.

 Eliminating a potential move eliminates the entire subtree as a set of possible
scenarios
 In game theory, a game tree is a directed graph whose nodes are positions in a
game and whose edges are moves. The complete game tree for a game is the
game tree starting at the initial position and containing all possible moves from each
position.
The diagram shows the first two levels, or ply, in the game tree for tic-tac-toe.
Fig 3.15 Game Tree
 We consider all the rotations and reflections of positions as being equivalent, so the
first player has three choices of move: in the centre, at the edge, or in the corner. The
second player has two choices for the reply if the first player played in the centre,
otherwise five choices and so on.
 The number of leaf nodes in the complete game tree is called the game tree
complexity. It is the number of possible different ways the game can be played. The
game tree complexity for tic-tac-toe is 26,830.
 Game trees are important in artificial intelligence because one way to pick the best
move in a game is to search the game tree using the min-max algorithm or its
variants.
3.6 Binary Search Tree (BST)

A binary search tree is a binary tree which is either empty or satisfies the following
properties(Fig 3.16):
 Every node has a value and no two nodes have the same value.
 If there exists a left child or left subtree then its value is less than the value of
the root.
 The values in the right child or right subtree is larger than the value of the root.
Operations of binary search tree(BST)

 Insertion
 Deletion
 Searching
 Find min, find max

Fig 3.16 Binary Search Tree
Structure of node in binary search tree:
Struct BSTnode
{
int data;
struct BSTnode *left, *right;
}BSTnode;
3.6.1 Insertion:
 Check whether the root node of the binary search tree is NULL.
 If the condition is true, it mean, that the binary search tree is empty hence
consider the new node as the root node.
 Compare the new node data with root node data, for the following three condition
 If the content of the new node is equal to the root node insertion operation
is terminated.
 If the content of the new node is lesser than the root node data. Check
whether the left child of the root node is null. If it is true insert the new
node.
 If the content of the newnode data is greater than the root node data, check
whether the right child of the root node is NULL. If the condition is true,
insert the new data.
Advantages of binary search tree
 Since the elements in the tree are ordered ,searching is faster and easier
 Insertion and deletion are also fast.
Example for Insertion in Binary search Tree:

Insert 10 , Since the tree is 12>10 , insert to the right 5<10,insert to the left since
empty make it as root node since the right is empty the left is empty
Compare 4<10, already left is Compare 20>10,already right Compare 8<10,

full compare 4<5 , insert to is full,compare 20>12,insert Compare 8>5, So insert to
the left of 4 to the right of 12 the right of 5
BSTnode *insert(BST *T, int x)

{
If(T==NULL)
{
T=new BSTnode;
T->data=x;
T->left=NULL;
T->right=NULL;
}
if(x > T -> data)
{
T -> right = insert (T -> right, x);
return(T);
}
Else
{
T -> left = insert(T -> left, x);
return (T);
}
}
3.6.2 Deletion:
Memory is to be released for the node to be deleted. A node can be deleted from the tree
from three different places namely,
 Deleting the leaf node

 Deleting the node with only one child
 Deleting the node with two children.
Deleting the Leaf node:
 Search the parent of the leaf node, and make the link to the leaf node or NULL.
 Release the memory for the deleted node(Fig 3.17)
Deleting the node with only one child:
 Search the parent of the node to be deleted(with only one child)

 Assign the link of the parent node to the child of the node to be deleted.
 Release the memory for the deleted node.(Fig 3.18)
Deleting the node with the two children:
 Search the parent of the node to be deleted (with two children)

 Copy the content of the inorder successor to the node to be deleted.
 Delete the inorder successor node – if the inorder successor node has no child.
 Release the memory for the inorder successor node.(Fig 3.19)
Fig 3.17 Deletion of Leaf Node

Fig 3.18 Deleting the node with only one child
Fig 3.19 Deleting the node with two children

3.6.3Searching:
 Check whether the root node of the binary search tree is NULL. If yes, binary search
tree is empty.
 If the binary search tree is not empty, compare the new node data with root node data
for the following three condition.
o If the content of the new node data is equal to the root node data,
search element is found.
o If the content of the new node data is lesser than the root node
data, check the left child.
o If the content of the new node data is greater than the root node
data, check the right child.
find(BSTnod *rroot, int x)

{
if ((root == NULL))
return(NULL);
if (root -> data == x)
return(root);
if (x > root -> data)
return (find (root -> right), x));
else
return(find(root->left), x));
}
3.6.4 Find Min:
This function returns to address of the node with smallest value in the tree.
BSTnode *find min (BSTnode *T)

{
while (T -> left! = NULL)
T = T -> left;
return(T);
}
3.6.5 Find Max:

This function returns the address of the node with largest value in the tree.
BSTnode find max(BSTnode *T)

{
while (T -> right! = NULL)
T = T -> right;
return(T);
}
3.7 AVL tree
AVL tree: G.M. Adelson-Velskii and E.M. Landis, who discovered them in 1962.
 A binary search tree, in which the heights of the left and right sub-trees of the
root differ by at most 1.The left and right sub-trees of the root are again AVL trees
 An AVL tree may or (in certain cases) may not be balanced.
Calculating balance factor for AVL tree:

 AVL trees are height-balanced binary search trees. A height-balanced binary tree
is a binary tree such that, the left & right sub trees for any given node differ in
height by no more than one.
 The height of a node in a tree is the length of a longest path from the node to a leaf.
The height of a tree is the height of its root.
 An AVL tree has balance factor calculated at every node:
Balance factor= Height(left sub-tree)-Height(right sub-tree)
 In binary search tree every node has a balancing factor of -1 ,0,1 is said to be
height balanced.
 A node with any other balance factor is said to be unbalanced tree and thus
required to be rebalancing
Structure of AVL Node:
struct avlnode
{
int data;
struct avl_node *left;
struct avl_node *right;
}*root;
3.7.1 Inserting into an AVL Tree :
 The basic insertion algorithm is similar to that of a binary search tree; during
insertion, the new node is inserted as the leaf node, as nodes are randomly
added or removed the balance factor can get disturbed.
 Balance factor will get disturbed when, the new node is added to a sub-tree of the
root, that is higher than the other sub-tree and the new node increases the height of
the sub-tree.
Critical Node: Initially the node was heavy (either left or right) and the new node has been
inserted in the heavy sub-tree thereby creating an unbalanced sub-tree. Such a node is
said to be a critical node.
3.7.2 Imbalanced Conditions:

 Addition of a node affects the AVL property, that is the height value is greater than -1
 These imbalance conditions can be reduced to one of four reference cases,
Case1: Addition in left sub-tree of left child (Left-Left Imbalance).
Case2: Addition in right sub-tree of left child (Left-Right Imbalance).
Case3: Addition in right sub-tree of right child (Right-Right Imbalance).
Case 4: Addition in left sub-tree of right child (Right-Left Imbalance).
Case – I: Left-Left Imbalance Case – II: Left-Right Imbalance
Case – III: Right-Right Imbalance Case – IV: Right-Left Imbalance
3.7.3 Restoring Balance:

Balance, in either of the cases can be restored by means of a process termed rotation
 In cases I & III balance is restored by means of single rotation(LL,RR)
 In cases II & IV balance is restored by means of double rotation (LR,RL)
LL rotations: Inserted node is in the left sub-tree of the left sub-tree of root node A.

RR rotations: Inserted node is in the right sub-tree of the right sub-tree of root node A.
LR rotations: Inserted node is in the right sub-tree of the left sub-tree of root node A.
RL rotations: Inserted node is in the left sub-tree of the right sub-tree of root node A.
3.7.4 RR Rotation:
An LL imbalance occurs at a node A such that A has a balance factor -2 and a left child
B with a balance factor -1 or 0,this type of imbalance can be fixed by performing a
single right rotation at A.
avlnode*avlTree::RR_rotation(avlnode*parent)
{
avl_node *temp;
temp = parent->right;
parent->right = temp->left;
temp->left = parent;
return temp;
}
3.7.5 LL Rotation:
An RR imbalance occurs at a node A such that A has a balance factor +2 and a right
child B with a balance factor +1 or 0, this type of imbalance can be fixed by performing
a single left rotation at A.

avl_node*avlTree::LLrotation(avlnode*parent)
{
avl_node *temp;
temp = parent->left;
parent->left = temp->right;
temp->right = parent;
return temp;
}
3.7.6 LR Rotation:
 An LR imbalance occurs at a node A such that A has a balance factor -2 and a left
child B with a balance factor +1,
Assume B‘s right child is C. This type of imbalance can be fixed by performing a
double rotation at A (first a single left rotation at B and then a single right rotation
at A)
avlnode*avlTree::LR_rotation(avlnode
*parent)
{
avl_node *temp;
temp = parent->left;
parent->left = rr_rotation (temp);
return ll_rotation (parent);
}
3.7.7 RL Rotation:
 An RL imbalance occurs at a node A such that A has a balance factor +2 and a

right child B with a balance factor -1,
 Assume B‘s left child is C. This type of imbalance can be fixed by performing a double
rotation at A (first a single right rotation at B and then a single left rotation at A)

avlnode*avlTree::RL_rotation(avlnode*parent)
{
avl_node *temp;
temp = parent->right;
parent->right = ll_rotation (temp);
return rr_rotation (parent);
}
3.7.8 Deletion in AVL Tree:
 Search for the key to be deleted.

 If the key is not contained, we are done.
Otherwise we distinguish three cases:
(a) The node to be deleted has no internal nodes as its children.
(b) The node to be deleted has exactly one internal child node.
(c) The node to be deleted has two internal children.
 After deleting a node the AVL property may be violated (similar to insertion).This
must be fixed appropriately.
3.8 Splay Trees
Splay Tree is a self - adjusted Binary Search Tree in which every operation on an
element re-arrange the tree so that the element is placed at the root position of the tree.
 In a splay tree, every operation is performed at root of the tree. All the operations
on a splay tree are involved with a common operation called "Splaying".
 Splaying an element is the process of bringing it to the root position by
performing suitable rotation operations.
In a splay tree, splaying an element rearrange all the elements in the tree so that splayed
element is placed at root of the tree. With the help of splaying an element we can bring
most frequently used element closer to the root of the tree so that any operation on
those element performed quickly. That means the splaying operation automatically brings
more frequently used elements closer to the root of the tree.
Advantages
 A splay tree gives good performance for search, insert and delete operations

 Splay trees are considerably simpler to implement than other self-balancing binary
search trees,
 Splay tree minimizes memory requirements
 Splay trees gives good performance (amortized O(log n))
Disadvantages
 While sequentially accessing all the nodes of the tree tree becomes completely
unbalanced
 For uniform access, the performance of a splay tree will be considerably worse.
Rotations in Splay Tree
 Zig Rotation
 Zag Rotation
 Zig - Zig Rotation
 Zag - Zag Rotation
 Zig - Zag Rotation
 Zag - Zig Rotation
3.8.1 Zig Rotation
The Zig Rotation in a splay tree is similar to thesingle right rotation in AVL Tree
rotations. In zig rotation every node moves one position to the right from its current
position.
3.8.2 Zag Rotation
The Zag Rotation in a splay tree is similar to the single left rotation in AVL Tree
rotations. In zag rotation every node moves one position to the left from its current
position. Consider the following example...

3.8.3 Zig-Zig Rotation
The Zig-Zig Rotation in a splay tree is a double zig rotation. In zig-zig rotation every node
moves two position to the right from its current position.
3.8.4 Zag-Zag Rotation

The Zag-Zag Rotation in a splay tree is a double zag rotation. In zag-zag rotation every
node moves two position to the left from its current position.
3.8.5 Zig-Zag Rotation

The Zig-Zag Rotation in a splay tree is a sequence of zig rotation followed by zag rotation.
In zig-zag rotation every node moves one position to the right followed by one position to
the left from its current position.
3.8.6 Zag-Zig Rotation

The Zag-Zig Rotation in a splay tree is a sequence of zag rotation followed by zig rotation.
In zag-zig rotation every node moves one position to the left followed by one position to
the right from its current position.

Note:Every Splay tree must be a binary search tree but it is need not to be balanced tree.
3.8.7 Insertion Operation in Splay Tree
The insertion operation in Splay tree is performed using following steps.

Step 1: Check whether tree is Empty.
Step 2: If tree is Empty then insert the newNode as Root node and exit from the operation.
Step 3: If tree is not Empty then insert the newNode as a leaf node using Binary Search
tree insertion logic.
Step 4: After insertion, Splay the newNode
3.8.8 Deletion Operation in Splay Tree
In a Splay Tree, the deletion operation is similar to deletion operation in Binary

Search Tree. But before deleting the element first we need to splay that node then delete it
from the root position then join the remaining tree.
3.9 B-Trees
B-Tree:
 A B-tree is a specialized m- way tree that is widely used for disk access.
 A B tree of order m can have maximum m-1 keys and m pointers to its sub-trees.
 A B-tree may contain a large number of key values and pointers to sub-trees.
 A B-tree is designed to store sorted data and allows search, insert, and delete
operations.
3.9.1 Properties of B-Tree

 Every node has at most m children.
 Every node (except root and leaves) has at least ceil(m⁄2) children.
 The root has at least two children if it is not a leaf node.
 All leaves appear in the same level, and carry information.
 A non-leaf node with k children contains k–1 key
 Each leaf node (other than the root node if it is a leaf) must contain
at least ceil(m / 2) - 1 keys
 Keys and sub-trees are arranged in the fashion of search tree
3.9.2 Search in a B-Tree:
 Searching is similar to searching a binary search tree.

 Starting at the root, the tree is recursively traversed from top to bottom. At each
level, the search chooses the child pointer (sub-tree) whose separation values are
on either side of the search value.
 Binary search is typically (but not necessarily) used within nodes to find the
separation values and child tree of interest.
3.9.3 Insertion in B-Tree:
All insertions start at a leaf node. To insert a new element, search the tree to find the
leaf node where the new element should be added. Insert the new element into that node
with the following steps:
1. Insert the new element in the node, keeping the node's elements ordered.
2. Otherwise the node is full, evenly split it into two nodes so:
o A single median is chosen from among the leaf's elements and the new
element.
o Values less than the median are put in the new left node and values greater
than the median are put in the new right node, with the median acting as a
separation value.
o The separation value is inserted in the node's parent, which may cause it to be
split, and so on. If the node has no parent (i.e., the node was the root), create a
new root above this node (increasing the height of the tree).
3.9.4 Deletion in B-Tree:
 Like insertion, deletion must be on a leaf node. If the key to be deleted is not in a
leaf, swap it with either its successor or predecessor (each will be in a leaf).
 The successor of a key k is the smallest key greater than k.
 The predecessor of a key k is the largest key smaller than k.
 In a B-tree the successor and predecessor, if any, of any key is in a leaf node
Deletion Algorithm:
1. If the key k is in node x and x is a leaf, delete the key k from x.
2. If the key k is in node x and x is an internal node, do the following:

a. If the child y that precedes k in node x has at least t keys, then find the
predecessor k' of k in the subtree rooted at y. Recursively delete k', and replace k
by k' in x. (Finding k' and deleting it can be performed in a single downward pass.)
b. Symmetrically, if the child z that follows k in node x has at least t keys, then find
the successor k' of k in the subtree rooted at z. Recursively delete k', and replace k
by k' in x. (Finding le and deleting it can be performed in a single downward pass.)
c. Otherwise, if both y and z have only t - 1 keys, merge k and all of z into y, so that
x loses both k and the pointer to z, and y now contains 2t - 1 keys. Then, free z and
recursively delete k from y.
Example : Construct a B-Tree with order m=3
Since M=3
Key = (M-1) = 3-1 = 2
Pointers = M = 3
Fig 3.20 Insertion in B Tree
Case 1: Delete a key at a leaf – no underflow. Within this first case, no properties are
violated if we just remove the key:

Fig 3.21 Deletion of Leaf Node
Case 2: Delete non-leaf key – no underflow. Within this second case, we face the
problem of re-assigning empty key "slots" because there are pointers to leaves that need
to be kept (this is different than in case 1 where we just deleted the key "slot").
Fig 3.22 Deletion of non-leaf
When filling the empty key, we have two different options for choosing which key we want
to use as a replacement:
1. The largest key from the left subtree

2. The smallest key from the right subtree
Note: If the node from which we took a key now also has an empty "slot" that needs to be
filled (i.e., it wasn't a leaf), just repeat the same steps above recursively until we hit a leaf
node!
Case 3: Delete leaf-key — underflow, and "rich sibling"

Fig 3.23 Delete leaf-key — underflow
Note that, in the case above, the sibling was "rich" enough to provide a key to the parent in
order for the parent to be able to give a key to the empty node.
Case 4: Delete leaf-key — underflow, and "poor sibling"
3.10 B+Trees
A B+ tree is a balanced tree in which every path from the root of the tree to a leaf is
of the same length, and each non-leaf node of the tree has between [n/2] and [n] children,
where n is fixed for a particular tree. It contains index pages and data pages. The capacity
of a leaf has to be 50% or more.
For example: if n = 4, then the key for each node is between 2 to 4.

Index page will be 4 + 1 = 5.
Example of a B+ tree
3.10.1 Properties of B+trees

• Balanced
• Every node except root must be at least ½ full.
• Order: the minimum number of keys/pointers in a non-leaf node
• Fan-out of a node: the number of pointers out of the node
Operations in B+ Tree
• Search:
o logd(n) – Where d is the order, and n is the number of entries
• Insertion:
o Find the leaf to insert into
o If full, split the node, and adjust index accordingly
o Similar cost as searching
• Deletion
o Find the leaf node
o Delete
o May not remain half-full; must adjust the index accordingly
Search:Since no structure change in a B+ tree during a searching process, so just

compare the key value with the data in the tree, then give the result back.
For example: find the value 45, and 15 in below tree.

Result:
1. For the value of 45, not found.
2. For the value of 15, return the
position where the pointer located.
3.10.2 Insertion
 Since insert a value into a B+ tree may cause the tree unbalance, so rearrange the
tree if needed.

3.10.3 Deletion algorithm
• Descend to the leaf where the key exists.

• Remove the required key and associated reference from the node.
• If the node still has enough keys and references to satisfy the invariants, stop.
• If the node has too few keys to satisfy the invariants, but its next oldest or next
youngest sibling at the same level has more than necessary, distribute the keys
between this node and the neighbor. Repair the keys in the level above to represent

that these nodes now have a different ―split point‖ between them; this involves simply
changing a key in the levels above, without deletion or insertion.
• If the node has too few keys to satisfy the invariant, and the next oldest or next
youngest sibling is at the minimum for the invariant, then merge the node with its
sibling; if the node is a non-leaf, we will need to incorporate the ―split key‖ from the
parent into our merging. In either case, we will need to repeat the removal algorithm
on the parent node to remove the ―split key‖ that previously separated these merged
nodes — unless the parent is the root and we are removing the final key from the root,
in which case the merged node becomes the new root (and the tree has become one
level shorter than before).
3.11 Tries: Tries are an extremely special and useful data-structure that are based on
the prefix of a string. They are used to represent the ―Retrieval” of data and thus the
name Trie.
Prefix : The prefix of a string is nothing but any n letters n≤|S| that can be considered
beginning strictly from the starting of a string. For example , the word ―abacaba‖ has the
following prefixes:
a
ab
aba
abac

abaca
abacab
A Trie is a special data structure used to store strings that can be visualized like a
graph. It consists of nodes and edges. Each node consists of at max 26 children and
edges connect each parent node to its children. These 26 pointers are nothing but pointers
for each of the 26 letters of the English alphabet A separate edge is maintained for every
edge.
Strings are stored in a top to bottom manner on the basis of their prefix in a trie. All
prefixes of length 1 are stored at until level 1, all prefixes of length 2 are sorted at until
level 2 and so on.
Two Marks
1. Define a tree
A tree is a collection of nodes. The collection can be empty; otherwise, a treeconsists
of a distinguished node r, called the root, and zero or more nonempty (sub) treesT1,
T2,…,Tk, each of whose roots are connected by a directed edge from r.
2. Define root
This is the unique node in the tree to which further sub-trees are attached.
Here, A is the root.

3. Define degree of the node
The total number of sub-trees attached to that node is called the degree of the node.
For node A, the degree is 2 and for B and C, the degree is 0.

4. Define leaves
These are the terminal nodes of the tree. The nodes with degree 0 are always the leaves.
Here, B and C are leaf nodes.
5. Define internal nodes

The nodes other than the root and the leaves are called internal nodes.
Here, C is the internal node.
6. Define parent node

The node which is having further sub-branches is called the parent node of those
sub-branches.
Here, node C is the parent node of D and E
7. Define depth and height of a node

For any node ni, the depth of ni is the length of the unique path from the root to ni.
The height of ni is the length of the longest path from n i to a leaf.
8. Define depth and height of a tree

The depth of the tree is the depth of the deepest leaf. The height of the tree is equal
to the height of the root. Always depth of the tree is equal to height of the tree.
9. What do you mean by level of the tree?

The root node is always considered at level zero, then its adjacent children are
supposed to be at level 1 and so on.
Here, node A is at level 0, nodes B and C are at level 1 and nodes D and E are at level 2.
10. Define forest

A tree may be defined as a forest in which only a single node (root) has no
predecessors. Any forest consists of a collection of trees.
11. Define a binary tree (May 2014)

A binary tree is a finite set of nodes which is either empty or consists of a root and
two disjoint binary trees called the left sub-tree and right sub-tree.
12. Define a path in a tree

A path in a tree is a sequence of distinct nodes in which successive nodes are
connected by edges in the tree.
13. Define a full binary tree

A full binary tree is a tree in which all the leaves are on the same level and every
non-leaf node has exactly two children.
14. Define a complete binary tree

A complete binary tree is a tree in which every non-leaf node has exactly two
children not necessarily to be on the same level.
15. State the properties of a binary tree

• The maximum number of nodes on level n of a binary tree is 2n-1, where n≥1.
• The maximum number of nodes in a binary tree of height n is 2n-1, where n≥1.
• For any non-empty tree, nl=nd+1 where nl is the number of leaf nodes and nd is
the number of nodes of degree 2.
16. What is meant by binary tree traversal?

Traversing a binary tree means moving through all the nodes in the binary tree,
visiting each node in the tree only once.
17. What are the different binary tree traversal techniques?

• Preorder traversal
• Inorder traversal
• Postorder traversal

• Levelorder traversal
18. What are the tasks performed during inorder traversal? (November 2013)
• Traverse the left sub-tree
• Process the root node
• Traverse the right sub-tree
19. What are the tasks performed during postorder traversal? (November 2013)
• Traverse the left sub-tree
• Traverse the right sub-tree
• Process the root node
20. State the merits of linear representation of binary trees.

• Storage method is easy and can be easily implemented in arrays
• When the location of a parent/child node is known, other one can be determined
easily
• It requires static memory allocation so it is easily implemented in all Programming
language
21. State the demerit of linear representation of binary trees.

Insertions and deletions in a node take an excessive amount of processing time
due to data movement up and down the array.
22. State the merit of linked representation of binary trees.

Insertions and deletions in a node involve no data movement except the
rearrangement of pointers, hence less processing time.
23. State the demerits of linked representation of binary trees.

• Given a node structure, it is difficult to determine its parent node
• Memory spaces are wasted for storing null pointers for the nodes, which have one
or no sub-trees
• It requires dynamic memory allocation, which is not possible in some
programming language
24. Define a binary search tree (December 2014)(November 2015)

A binary search tree is a special binary tree, which is either empty or it should
satisfy the following characteristics:
Every node has a value and no two nodes should have the same value i.e) the
values in the binary search tree are distinct
• The values in any left sub-tree is less than the value of its parent node
• The values in any right sub-tree is greater than the value of its parent node
• The left and right sub-trees of each node are again binary search trees

25. What is the use of threaded binary tree?
In threaded binary tree, the NULL pointers are replaced by some addresses. Theleft
pointer of the node points to its predecessor and the right pointer of the node points toits
successor.
26.Traverse the given tree using Inorder, Preorder and Postorder traversals.
Inorder : D H B E A F C I G J
Preorder: A B D H E C F G I J
Postorder: H D E B F I J G C A
27. In the given binary tree, using array you can store the node 4 at which
location?(May 2014)
At location 6
1 2 3 - - 4 - - 5
where LCn means Left Child of node n and RCn means Right Child of node n
28.Define AVL Tree. (November 2013)

An empty tree is height balanced. If T is a non-empty binary tree with TL and
TR as its left and right subtrees, then T is height balanced if
i) TL and TR are height balanced and
ii) │hL - hR│≤ 1
Where hL and hR are the heights of TL and TR respectively.
29.What do you mean by balanced trees? (November 2015)

Balanced trees have the structure of binary trees and obey binary searchtree
properties. Apart from these properties, they have some special constraints,which differ
from one data structure to another. However, these constraints areaimed only at reducing
the height of the tree, because this factor determines thetime complexity.
Eg: AVL trees, Splay trees.
30.What are the categories of AVL rotations? (April 2015)

Left-Left: The newly inserted node is in the left subtree of the left child of A.
Right-Right: The newly inserted node is in the right subtree of the right child of
Left-Right: The newly inserted node is in the right subtree of the left child of A.
Right-Left: The newly inserted node is in the left subtree of the right child of A.
31.What do you mean by balance factor of a node in AVL tree?

The height of left subtree minus height of right subtree is called balancefactor of a
node in AVL tree.The balance factor may be either 0 or +1 or -1.Theheight of an empty
tree is -1.
32. Define splay tree.

A splay tree is a binary search tree in which restructuring is done using ascheme
called splay. The splay is a heuristic method which moves a given vertexv to the root of
the splay tree using a sequence of rotations.
33.What is the idea behind splaying?

Splaying reduces the total accessing time if the most frequently accessednode is
moved towards the root. It does not require to maintain any informationregarding the
height or balance factor and hence saves space and simplifies thecode to some extent.
34.List the types of rotations available in Splay tree.

Let us assume that the splay is performed at vertex v, whose parent and
grandparent are p and g respectively. Then, the three rotations are named as:
Zig: If p is the root and v is the left child of p, then left-left rotation at p would suffice. This
case always terminates the splay as v reaches the root after this rotation.
Zig-Zig: If p is not the root, p is the left child and v is also a left child, then a left- left
rotation at g followed by a left-left rotation at p, brings v as an ancestor of g as well as p.
Zig-Zag: If p is not the root, p is the left child and v is a right child, perform a left-right
rotation at g and bring v as an ancestor of p as well as g.
35. Define Heap.

A heap is defined to be a complete binary tree with the property that thevalue of each
node is atleast as small as the value of its child nodes, if they exist.The root node of the
heap has the smallest value in the tree.
36.What is the minimum number of nodes in an AVL tree of height h?

The minimum number of nodes S(h), in an AVL tree of height h is given
by S(h)=S(h-1)+S(h-2)+1. For h=0, S(h)=1.
37. Define B-tree of order M.

A B-tree of order M is a tree that is not binary with the following structural
properties:
• The root is either a leaf or has between 2 and M children.
• All non-leaf nodes (except the root) have between ┌M/2┐ and M children.
• All leaves are at the same depth.
38. What do you mean by 2-3 tree?

A B-tree of order 3 is called 2-3 tree. A B-tree of order 3 is a tree that is not binary
with the following structural properties: The root is either a leaf or has between 2 and 3
children.
• All non-leaf nodes (except the root) have between 2 and 3 children.
39. What do you mean by 2-3-4 tree?

A B-tree of order 4 is called 2-3-4 tree. A B-tree of order 4 is a tree that is not binary
with the following structural properties:
• The root is either a leaf or has between 2 and 4 children.
• All non-leaf nodes (except the root) have between 2 and 4 children.
40. What are the applications of B-tree? (April 2015)

• Database implementation
• Indexing on non primary key fields
41. Define expression trees?

The leaves of an expression tree are operands such as constants or variable names
and the other nodes contain operators.
1. Perform all the tree traversal on the following tree
2. Show the result of inserting 2, 1, 4, 5, 9, 3, 6, 7 into an initially empty AVL tree.

Prove that the resulting tree is perfectly balanced.
3. Write a routine to perform insertion into a B-tree. b. Write a routine to perform
deletion from a B-tree. Construct a B-Tree with order m = 3.for the key values 2, 3,
7, 9, 5, 6, 4, 8, 1 and delete the values 4 and 6. Show the tree in performing all
operations.

4. Construct a binary search tree by inserting 30, 10, 4, 19, 62, 35, 28, 73 into an
initially empty tree.Show the results of splaying the nodes 4 and 62 one after the
other of the constructed tree.
5. Give the prefix, infix, and postfix expressions corresponding to the tree in the Figure

Unit IV
Sorting: O notation – efficiency of sorting – bubble sort – quick sort – selection sort –
heap sort – insertion sort – shell sort – merge sort – radix sort.
Objective:
 To study and analyze time complexity of various sorting algorithms

 To design, implement, and analyze the various sorting algorithms
Outcome:
 Able to differentiate the different sorting algorithms
 Know the suitable sorting method for specific application
4.1 Efficiency of an algorithm or performance analysis of an algorithm
Algorithm : It is a step by step process to accomplish a particular task.
Efficiency of an algorithm
Efficiency of an algorithm is one of the properties of an algorithm based on the

resources used by the algorithm. The most commonly used resources are time and
space.
Space Complexity- It is the amount of memory space (main memory) required to
complete the execution of the algorithm.
Time Complexity - It is the amount of CPU time required to complete the execution of the
algorithm.
Computing Space Complexity: The space required for an algorithm is calculated based
on fixed and variable part of the program.
Fixed part:
 Space required for code

 Simple variable
 Static compound variable
 Constants
Variable part:
 Dynamic compound variable

 Recursive procedure
The space required to execute any algorithm P is denoted by,

S[P] = C + Sp(instance characteristics)
Where C – is constant i.e. fixed part, can be ignored.
Sp – Variable part.
Eg 1:
Algorithm ComputeABC(a,b,c)
{
Sum = a+b+c;
}
S(ComputeABC) = C + Sp(instance characteristics)
= C + Sp(0)
=0
Eg 2:
Algorithm Sum(a,n)
{
Sum = 0;
for i=0 to n
{
Sum = Sum + a[i];
}
return Sum;
}
Instance Code a n Sum i Total
1(n=5) C 10 2 2 2 10+6
2(n=10) C 20 2 2 2 20+6
3(n=100) C 200 2 2 2 200+6
4(n=1000) C 2000 2 2 2 2000+6
5(n=10000) C 20000 2 2 2 20000+6
S(Sum) = C + Sp(n)
=C+n+3
=n+3
= O (n)
Computing Time Complexity: Time complexity of any program is the sum of compile
time and run time.
The compile time remains constant for all instance of an algorithm (assume that a
compiled program can be run many times without recompilation).So compile time can be
ignored.
T(p) = tp(instance characteristics)
There are 2 methods to calculate time complexity
 Count method
 Step table method

Program Step
It is defined as syntactically and semantically meaningful segment of a program that
has execution time which is independent of the instance characteristics of the problem.
Number of program steps assigned for any program statement depends on kind of
statement.
 Comment line has zero program step.

 Assignment statement which does not involve any function call is assigned one
program step.
 Control part of a program such as while, for, do has one program step.
Count method
Count is a global variable with initial value „0‟. Whenever the statement in the
algorithm is executed, the count is incremented by the program step assigned for that
statement.
Eg:
Algorithm Sum(a,n)
{
Sum = 0; -1
for i=0 to n - n+1
{
Sum = Sum + a[i]; -n
}
return Sum; -1
}
t(Sum) = 1+ n + 1 + n + 1
= 2n + 3
= O (n)
Step table method

The Step table list out the following fields
(i) Statement in algorithm to be analysed.
(ii) No. of program steps per execution of statement
(iii) Total no. of times (frequency) each statement is executed.
(iv) Total no. of program steps contributed for each statement.

Statement No. of program Frequency Total no. of

steps per execution program steps
Algorithm Sum(a,n) - - -
{ - - -
Sum = 0; 1 1 1
for(i=0 to n) 1 n+1 n+1
{ - - -
Sum = 1 n n
Sum+a[i];
} - - -
return Sum 1 1 1
} - - -
2n+3
Asymptotic notation: (o, Ω, ө)
Asymptotic Notation is used to represent the efficiency of an algorithm.
O – Big ‘oh’ Notation
f(n) = O(g(n)), iff there exist a positive constant c,n 0 such the f(n) <= c*g(n) for all
n>= n0.
Eg: f(n) = 2n + 3
f(n) = O(n).
Eg: f(n) = 10n3+n2+9n+10

f(n) = O(n3).
Ω - Omega Notation
f(n) = Ω(g(n)), iff there exist a positive constant c,n0 such the f(n) >= c*g(n) for all
n>= n0.
Ө - Omega Notation
f(n) = Ө(g(n)), iff there exist a positive constant c 1,c2,n0 such the
c1*g(n)<= f(n) <= c2*g(n).
Relation between time complexity in Big „oh‟ notation :
O(1) < O(log n) < O(n) < O(n log n) < O(n2) < O(n3) < O(2n).

4.2 Sorting
Sorting a sequence of elements means rearranging them in either ascending or
descending order depending upon the relationship among the data items present in the
group.
Factors to be considered while choosing the sorting techniques

 Programming time of a sorting technique.
 Execution time of a sorting technique.
 No. of comparison required for sorting the list.
 Main memory or auxiliary memory space, needed for the sorting techniques.
Sorting algorithm
A sorting algorithm is defined as an algorithm that puts elements of a list in a certain order
that can either be numerical order, lexicographical order or any user-defined order.
Types of Sorting:
 Internal sorting - which deals with sorting the data stored in computer‟s memory
 External sorting - This deals with sorting the data stored in files.
Application of Sorting
Speeding up the search process is the most important application of sorting.
Various Sorting techniques

 Bubble Sort
 Selection Sort
 Insertion Sort
 Shell Sort
 Merge Sort
 Quick Sort
 Radix (Bucket) Sort
 Heap Sort
4.3 Bubble sort

It is the easiest and most widely used sorting technique. This technique is also
referred to as sinking sort. The idea in this technique is to repeatedly move the
smallest element into the lowest index position or repeatedly move the largest element
into highest index position in the list.

Algorithm BubbleSort(a,n)
{
for(i=1 to n)
{
for(j=1 to n-i)
{
if(a[j]>a[j+1])
{
temp = a[j];
a[j]=a[i];
a[i]=temp;
}
}
}
}
Analysis (Efficiency)
Best case: O (n2)
Average case: O (n2)
Worst case: O (n2)
Advantages of Bubble Sort

 Popular & easy to implement.
 No additional temporary storage is required.
 It requires only few lines of code.
Disadvantage of Bubble Sort

 Amount of time increases with the no. of elements get increased.
 Sorting becomes difficult when element size increases
Example : Sort the elements a[1:5] = { 56 , 91 , 35, 72, 43}
i j a[1] a[2] a[3] a[4] a[5] a[j]>a[j+1] operation

1 1 56 91 35 72 43 56>91 (f) No operation
2 56 91 35 72 43 91>35 (t) Swap 91 &
35
3 56 35 91 72 43 91>72 (t) Swap 91 &
72
4 56 35 72 91 43 91>43 (t) Swap 91 &
43
56 35 72 43 91
2 1 56 35 72 43 91 56>35 (t) Swap 56 &
35
2 35 56 72 43 91 56>72 (f) No operation
3 35 56 72 43 91 72>43 (t) Swap 72 &
43
35 56 43 72 91

3 1 35 56 43 72 91 35>56 (f) No operation
2 35 56 43 72 91 56>43 (t) Swap 56 &
43
35 43 56 72 91
4 1 35 43 56 72 91 35>43 (f) No operation
35 43 56 72 91
35 43 56 72 91 Sorted order
4.4 Quick sort algorithm
Quick sort is otherwise called as partition exchange sorting.

Basic Concept: divide and conquer-
Given an array of n elements (e.g., integers):
• If array only contains one element, return
• Else
– Pick one element to use as pivot.
– Partition elements into two sub-arrays:
• Elements less than or equal to pivot
• Elements greater than pivot
 Quick sort two sub-arrays, Recursively apply Quicksort to the subgroups
 Return results
Different ways to select a pivot element:
 First element
 Last element
 Use that median as the pivot.
 Random element
Algorithm QuickSort(low,high)
{
if(low<high)then
{
j=partition(a,low,high+1);
QuickSort(low,j-1);
QuickSort(j+1,high);
}
}
Algorithm partition(a,m,p)
{
v=a[m];
i=m;
j=p;
repeat

{
repeat
{
i=i+1
}until a[i]>=v;
repeat
{
j=j-1
}until a[j]<=v;
if(i<j)then
Interchange(a,i,j);
}until(i>=j);
a[m]=a[j];
a[j]=v;
return j;
}
Algorithm Interchange(a,i,j)
{ temp=a[i];
a[i]=a[j];
a[j]=temp;
}
a[1] a[2] a[3] a[4] a[5] i j i<j i>=j

50 20 60 10 ∞ 3 4 3<4 (t)
i)Swap a[i] &a[j]
ii)repeat
50 20 10 60 ∞ 4 3 4<3 (f) 4>=3 (t)
i)Swap a[j] & a[m]
ii) return 3
10 20 50 60 ∞ 2 1 2<1 (f) 2>=1 (t)
i)Swap a[j] & a[m]
ii) return 1
Best case: O (n log n)
Average case: O (n log n)
Worst case: O (n2)

Step 1, select a pivot(it is arbitrary)

We will select the first element
Step 2,
 Start process of dividing data into LEFTand
RIGHT groups:
 The LEFT group will have elements less than
the pivot.
 The RIGHT group will have elements greater
that the pivot.
 Use markers left and right
Step 3,
 If left element belongs to LEFT group, then
increment left index.
 If right index element belongs to RIGHT,
then decrement right.
 Exchange when you find elements that
belong to the other group. Step 4:
 Element 33 belongs to RIGHT group.
 Element 22 belongs to LEFT group.
 Exchange the two elements.
Step 5:
 After the exchange, increment left marker,
decrement right marker
Step 6:
 Element 35 belongs to RIGHT group.
 Element 12 belongs to LEFT group.
 Exchange, increment left, and decrement
right.

Step 7: Step 8:
 Element 29 belongs to RIGHT.  When the left and right markers pass each
 Element 19 belongs to LEFT. other, we are done with the partition task.
 Exchange ,increment left, decrement right.  Swap the right with pivot.
Step 9:
Apply Quick sort to the LEFT and RIGHT groups, recursively.
4.5 Selection Sort

 Keep finding the “next” smallest item
 Place the item found in the appropriate position
Algorithm SelectionSort(a,n)
{
for(i=1 to n)
{
min = i;
for j=i+1 to n
{
if(a[j]<a[min])
{
min = j;
}
}
if(i!=min)
{
temp=a[i];
a[i]=a[min];
a[min]=temp;
}
}
}

Best case: O (n2)

Worst case: O (n2)
Advantages of Selection Sort
 Easy of understand and implement

 Performs well for small data set
Disadvantage of Selection Sort

 Poor efficiency when dealing with higher no. of elements
 Needs n2 sequential no. of steps for sorting n elements.
Example: Sort the elements a[1:5] = { 56 , 91 , 35, 72, 48}
i J min a[1] a[2] a[3] a[4] a[5] a[j]<a[min] Operation

1 2 1 56 91 35 72 48 91<56 (f) No operation
3 1 56 91 35 72 48 35<56 (t) min = j (=3)
4 3 56 91 35 72 48 72<35 (f) No operation
5 3 56 91 35 72 48 48<35 (f) No operation
3 56 91 35 72 48 End of Swap min and
pass i
35 91 56 72 48
2 3 2 35 91 56 72 48 56<91 (t) min = j (=3)
4 3 35 91 56 72 48 72<56 (f) No operation
5 3 35 91 56 72 48 48<56 (t) min = j (=5)
pass i
35 48 56 72 91
3 4 3 35 48 56 72 91 72<56 (f) No operation
5 3 35 48 56 72 91 91<56 (f) No operation
pass i
35 48 56 72 91
4 5 4 35 48 56 72 91 91<72 (f) No operation
pass i
35 48 56 72 91
5 - - 35 48 56 72 91 Sorted
order

4.6 Heap sort
 Heap sort is an efficient sorting algorithm

 The (binary) heap data structure is an array object that can be viewed as a complete
binary tree
 Heap sort is an in-place algorithm i.e. does not use any extra space
 This method is based on a data structure called Heap.
 Heap data structure can also be used as a priority queue.
Complete Binary tree: A Binary tree with n nodes of depth k is complete if its nodes
correspond to the nodes which are numbered from 1 to n in a full binary tree of depth k
(nodes are numbered starting from nodes at level 1 then go to nodes at level 2 and so
on… from left to right).
Eg:
7
8 12
3 1 12
55
Heap:
There are two types of Heap
(i) Max-Heap
(ii) Min-Heap
Heap Property:
 Max-Heap
 A Max-heap is a complete binary tree with a property that each node is at least
as large as the values at its children (if they exist)
 Min-Heap
 A Min-heap is a complete binary tree with a property that each node is at least
as small as the values at its children (if they exist).
4.6.1 Heap Sort Algorithm
Algorithm HeapSort(a,n)
{
Heapify(a,n);
for i = n to 0,step-1 do
{
t=a[i];
a[i]=a[1];
a[1]=t;
adjust(a,1,i-1);
}
}
Algorithm Heapify(a,n)
{
for i =n/2 to 1,step-1 do
{
adjust(a,i,n);
}
}
Algorithm adjust(a,i,n)
{
j=2i;
item=a[i];
while(j<=n)do
{
if((j<n)and(a[j]<a[j+1]))
{
break;
}
a[j/2]=a[j];
j=2j;
}
a[j/2]=item;
}
Example: Sort the list a[1:6] = {5, 7, 6, 20, 10, 25} using heap sort.
Step 1: Construct a complete binary tree for the given set of elements
a[1:6] = {5, 7, 6, 20, 10, 25}
7 6
20 10 25
55
Step 2: Convert the complete binary tree into max-heap using adjust.

Adjust Adjust
Adjust
Adjust
Adjust
Adjust
 Since all the non-leaf node(root) in the complete binary tree satisfy the max-heap
property, it becomes max-heap and the first largest element in the list is moved into
the root.
 Interchange the element in the first root with the element in the n th position node
Interchange
Since, the nth element is in sorted order, it is not considered for the remaining
sorting process. Therefore the node is deleted from the tree.

Step 3: Construct a complete binary tree for the element 1 to n-1 and convert it to max-
heap
Adjust
Since all root in the complete binary tree satisfy the heap property, it becomes max-
heap and second largest element is moved into the first root.
Interchange the element in the first root with the element in the (n-1)th position node
Interchange
Since, the (n-1)th element is in sorted order, it is not considered for the remaining sorting
process. Therefore the node is deleted from the tree.

heap
Adjust
heap and third largest element is moved into the first root.
Interchange
heap
Adjust
heap and fourth largest element is moved into the first root.

Interchange
heap
Since all root in the complete binary tree satisfy the heap property, it becomes max-heap
and fourth largest element is moved into the first root.
Interchange
Finally the heap consists of single element i.e. the n th largest element which is placed in 1st
position i.e. the (n-5)th position of array
The sorted list a[1:6] = {5, 6, 7, 10, 20, 25}.

Best case: O(n log n)

Average case: O(n log n)
Worst case: O(n log n)
4.7 Insertion sort
The insertion sort algorithm is performed using following steps...
Step 1: Assume that first element in the list is in sorted portion of the list and remaining all
elements are in unsorted portion.
Step 2: Consider first element from the unsorted list and insert that element into the sorted
list in order specified.
Step 3: Repeat the above process until all the elements from the unsorted list are moved
into the sorted list.
Algorithm InsertionSort(a,n)
{
for i=2 to n
{
key = a[i];
j=i-1;
while (j>0) and (key < a[j])
{
a[j+1]=a[j];
j=j-1;
}
a[j+1]=key;
}
}
Example: Sort the elements a[1:5] = {56, 91, 35, 72, 48}
i j a[1] a[2] a[3] a[4] a[5] key< a[i] Operation
{a[j+1]=a[j]…(t)
a[j+1]=key…(f) &
(no more previous
element)
2 1 56 91 35 72 48 91<56 (f) a[2] = key (=91)
56 91 35 72 48 End of pass -
3 2 56 91 35 72 48 35<91 (t) a[3] = a[2] (=91)
1 56 91 91 72 48 35<56 (t) a[2] = a[1] (=56)
0 56 56 91 72 48 No more a[1] = key (=35)
previous
element
35 56 91 72 48 End of pass -
4 3 35 56 91 72 48 72<91 (t) a[4] = a[3] (=91)
2 35 56 91 91 48 72<56 (f) a[3] = key (=72)
35 56 72 91 48 End of pass -

5 4 35 56 72 91 48 48<91 (t) a[5] = a[4] (=91)
3 35 56 72 91 91 48<72 (t) a[4] = a[3] (=72)
2 35 56 72 72 91 48<56 (t) a[3] = a[2] (=56)
1 35 56 56 72 91 48<35 (f) a[2] = key (=48)
35 48 56 72 91 End of pass -
6 - 35 48 56 72 91 - Sorted order
Best case: O(n)

Average case: O(n)
Worst case: O(n2)
4.8Shell sort (or) Diminishing increment sort
 It is improvement of insertion sort.

 Shell sort works by comparing elements that are distant rather than adjacent elements
in an array or list where adjacent elements are compared.
 Shell sort is also known as diminishing increment sort.
 The distance between comparisons decreases as the sorting algorithm runs until the
last phase in which adjacent elements are compared.
 The shell sort compares elements that are a certain distance away (d positions away)
from each other and it compares these elements repeatedly.
 The comparison is made as by using the concept of dividing the array as n/2 , and
compare the elements, compare until 1.
 The comparison model makes the sorting process of the shell sort very efficient.
Algorithm ShellSort(a,n)
{
dist=n/2;
do
{
for(i=1 to n)
{
j = i;
key = a[i+dist];
while ((j>0)and(key<a[j]))
{
a[j+dist]=a[j];

j=j-dist;
}
a[j+dist]=key;
}
dist=dist/2;
}while(dist);
}
Best case: O (n log n)
Worst case: O (n2)
Example: Sort the list of elements a[1:6] = {70, 50, 40, 30, 35, 25}.
dist= n/2 = 6/2 = 3;
dist I j a[1] a[2] a[3] a[4] a[5] a[6] j>0 key< a[i] No operation
3 1 1 70 50 40 30 35 25 1>0(t) 30<70 a[j+dist]=a[j]
(t) a[4]=70
j=j-dist (j= -2)
- 70 50 40 70 35 25 -2>0(f) - a[j+dist]=key
2 a[1]=30
- 30 50 40 70 35 25 - - i=2;j=2;key=35;
2 2 30 50 40 70 35 25 2>0(t) 35<50 a[j+dist]=a[j]
(t) a[5]=50
j=j-dist (j= -1)
- 30 50 40 70 50 25 -1>0(f) - a[j+dist]=key
1 a[2]=35
- 30 35 40 70 50 25 - i=3;j=3;key=25;
3 3 30 35 40 70 50 25 3>0(t) 25<40 a[j+dist]=a[j]
(t) a[6]=40
j=j-dist (j= 0)
0 30 35 40 70 50 40 0>0 (f) - a[j+dist]=key
a[3]=25
- 30 35 25 70 50 40 - - i=4;
dist=dist/2 (=1)
1 1 1 30 35 25 70 50 40 1>0 (t) 35<30 a[j+dist]=key
(f) a[2]=35
i=2;j=2;key=25
2 2 30 35 25 70 50 40 2>0 (t) 25<35 a[j+dist]=a[j]
(t) a[3]=35
j=j-dist (j=1)
1 30 35 35 70 50 40 1>0 (t) 25<30 a[j+dist]=a[j]
(t) a[2]=30
j=j-dist (j=0)

0 30 30 35 70 50 40 0>0 (f) - a[j+dist]=key
a[1]=25
- 25 30 35 70 50 40 - - i=3;j=3;key=70
3 3 25 30 35 70 50 40 3>0 (t) 70<35 a[j+dist]=key
(f) a[4]=70
i=4;j=4;key=50
4 4 25 30 35 70 50 40 4>0 (t) 50<70 a[j+dist]=a[j]
(t) a[5]=50
j=j-dist (j=3)
3 25 30 35 70 70 40 3>0 (t) 50<35 a[j+dist]=key
(f) a[4]=50
- 25 30 35 50 70 40 - - i=5;j=5;key=40
5 5 25 30 35 50 70 40 5>0 (t) 40<70 a[j+dist]=a[j]
(t) a[6]=70
j=j-dist (j=4)
4 25 30 35 50 70 70 4>0 (t) 40<50 a[j+dist]=a[j]
(t) a[5]=50
j=j-dist (j=3)
3 25 30 35 50 50 70 3>0 (t) 40<35 a[j+dist]=key
(f) a[4]=40
- 25 30 35 40 50 70 - - i=6;
dist=dist/2 (=0)
0 - - 20 30 35 40 50 70 - - Sorted Order
4.9 Merge sort

Divide-and-Conquer
 It is Recursive in structure
 Divide the problem into several smaller sub problems that are similar to the original
but smaller in size.
 Conquer the sub-problems by solving them recursively. If they are small enough,
just solve them in a straightforward manner.
 Combine the solutions to create a solution to the original problem
Divide: Divide the n-element sequence to be sorted into two subsequences of n/2
elements each
Conquer: Sort the two subsequences recursively using merge sort.
Combine: Merge the two sorted subsequences to produce the sorted answer.
If n=1 terminate (every one-element list is already sorted)
Algorithm MergeSort(low,high) Algorithm Merge(low,mid,high)
{ {
if(low<high) h=low;
{ i=low;
mid=(low+high)/2; j=mid+1;
MergeSort(low,mid);
while((h<=mid)&&(j<=high))
MergeSort(mid+1,high); {
Merge(low,mid,high); if(a[h]<a[j])then
} {
} b[i]=a[h];
h=h+1;
}
else
{
b[i]=a[j];
j=j+1;
}
i=i+1;
}
if(h>mid)then
{
for(k=j to high)
{
b[i]=a[k];
i=i+1;
} }
else
{ for(k=h to mid)
{
b[i]=a[k];
i=i+1;
} }
for(k=low to high)
{
a[k]=b[k];
}
}

Example: Sort the elements a[0:6]={38,27,43,3,9,82,10}
Tree representation of Merge sort algorithm
Trace out of Merge Algorithm
3 27 38 43 9 10 82
i = 0; h = 0; j = 4;
Step 1:
 h<=mid && j <=high
0<=3(t) && 4<=6(t)
 a[h]<a[j]
3<9 (t)
 b[i]=a[h]
b[0]=3
 h=h+1(=1)
 i=i+1(=1)
3
Step 2:
1<=3(t) && 4<=6(t)
 a[h]<a[j]
27<9 (f)
 b[i]=a[j]
b[1]=9
 j=j+1(=5)
 i=i+1(=2)
3 9
Step 3:
1<=3(t) && 5<=6(t)
 a[h]<a[j]
27<10 (f)
 b[i]=a[j]
b[2]=10
 j=j+1(=6)
 i=i+1(=3)
3 9 10
Step 4:
1<=3(t) && 6<=6(t)
 a[h]<a[j]
27< 82(t)
 b[i]=a[h]
b[3]=27
 h=h+1(=2)
 i=i+1(=4)
3 9 10 27
Step 5:
2<=3(t) && 6<=6(t)
 a[h]<a[j]
38< 82(t)
 b[i]=a[h]
b[4]=38
 h=h+1(=3)
 i=i+1(=5)
3 9 10 27 38 Analysis (Efficiency)
Step 6:
 h<=mid && j <=high Best case: O (n log n)
3<=3(t) && 6<=6(t) Average case: O (n log n)
 a[h]<a[j] Worst case: O (n log n)
43< 82(t)
 b[i]=a[h]
b[5]=43
 h=h+1(=4)
 i=i+1(=6)
3 9 10 27 38 43
Step 7:
4<=3(f) && 6<=6(t)
 h>mid
4>3 (t)
 k=6
 b[i]=a[k]
 b[6]=82
 i=i+1 (=7)
3 9 10 27 38 43 82
4.10 Radix or Bucket sort

 It is generalization of BucketSort for large integer keys, Radix sort is a multiple pass
distribution sort.Radix = “The base of a number system”It distributes each item to a
bucket according to part of the item's key.
Basic Idea of radix sort:

 Bucket Sort on each digit least significant digit to most significant digit (lsd to msd)
 Set number of buckets B.B= radix.i.e the base of the number system ,if decimal
number it is 10. Insert the numbers into the buckets.
Algorithm RadixSort(a,n)
{
// To find th maximum element
max=a[1];
for i=2 to n
{
if(a[i]>max)
{
max=a[i];
}
}
// To find the maximum no.of digits in the given element
digit = 0;
while(max>0)
{
digit=digit+1;
max=max/10;
}
// To sort the element using modulo division
divisor = 1;
for(p=1 to digit)
{
for(i=0 to 9)
{
bsize[i]=0;
}
for(i=1 to n)
{
r=((a[i]/divisor)%10);
bucket[r][bsize[r]]=a[i];
bsize[r]++;
}

i=1;
for(k=0 to i)
{
for(j=o to bsize[k])
{
a[i]=bucket[k][j];
i=i+1;
} } } }
Example: Sort the list a[1:8]={70, 80, 5, 268, 322, 32, 100, 45} using radix sort.
Step 1: Find the maximum element in the given list of elements.
i max a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[i]>max
1 70 70 80 5 268 322 32 100 45 80>70 (t)
i++;
max=80;
2 80 70 80 5 268 322 32 100 45 5>80 (f)
i++;
3 80 70 80 5 268 322 32 100 45 268>80 (t)
i++;
max=268
4 268 70 80 5 268 322 32 100 45 322>268 (t)
i++;
max=322
5 322 70 80 5 268 322 32 100 45 32>322 (f)
i++
6 322 70 80 5 268 322 32 100 45 100>322 (f)
i++
7 322 70 80 5 268 322 32 100 45 45>322 (f)
Step 2: Find the no. of digits in the maximum element.
Here max=322.
Digit max>0 max Operation

0 322>0 (t) 32 digit++;
max=max/10;
1 32>0 (t) 3 digit++;
max=max/10;
2 3>0 (t) 0 digit++;
max=max/10;
3 0>0 (f) 0 -

Here, the no. of digits in the max .element is 3.
Since, digit=3
Step 3:
Sort the list of elements based on each least significant digit.
Change all the elements in the list into 3-digit number by adding required no of 0‟s
to its left.
a[1:8] = {070, 080, 005, 268, 322, 032, 100, 045}

Pass 1
1st LSD = ((element/1)%10)
Based on the first least significant digit in the list, the elements in the list are placed
in the corresponding buckets
100
080 032 045
070 322 005 268
0 1 2 3 4 5 6 7 8 9
After the Pass 1, move the elements from bucket into array using FIFO
a[1:8] = {070,080,100,322,032,005,045,268}
Pass 2
2nd LSD = ((element/10)%10)

Based on the second least significant digit in the list, the elements in the list are
placed in the corresponding buckets
005
100 322 032 045 268 070 080
0 1 2 3 4 5 6 7 8 9
After the Pass 2, move the elements from bucket into array using FIFO
a[1:8] = {100,005,322,032,045,268,070,080}
Pass 3
3rd LSD = ((element/100)%10)

Based on the third least significant digit in the list, the elements in the list are placed
in the corresponding buckets
080
070
045
032
005 100 268 332
0 1 2 3 4 5 6 7 8 9
After the Pass 3, move the elements from bucket into array using FIFO to get sorted order
of the array
a[1:8] = {005,032,045,070,080,100,268,332}.
Best case: O (kn)

Average case: O (kn)
Worst case: O (kn)
Time Complexity
Algorithm Data Structure
Best Average Worst
Quicksort Array O(n log(n)) O(n log(n)) O(n^2)
Mergesort Array O(n log(n)) O(n log(n)) O(n log(n))
Heapsort Array O(n log(n)) O(n log(n)) O(n log(n))
Bubble Sort Array O(n) O(n^2) O(n^2)
Insertion Sort Array O(n) O(n^2) O(n^2)
Select Sort Array O(n^2) O(n^2) O(n^2)
Bucket Sort Array O(n+k) O(n+k) O(n^2)
Radix Sort Array O(nk) O(nk) O(nk)

Two Marks
1. What is an Algorithm? What are the properties of an Algorithm?
An algorithm is clearly specified set of simple instructions to be followed to
solve a problem. The algorithm forms a base for program.
Properties of an Algorithm
Takes zero or more inputs
Results in one or more outputs
All operations are carried out in a finite time
Efficient and flexible
Should be concise and compact to facilitate verification of their correctness.
2. What is Complexity analysis?

It is the analysis of the amount of memory and time an algorithm requires to
completion. There are two types of Complexity
Space Complexity
Time Complexity
3. Explain the performance analysis of the algorithm?

The analysis of the performance of an algorithm based on specification is
called performance analysis. It is loosely divided into
i.Priori estimates
ii.Posterior Testing
4. Explain Space complexity?
Space complexity of an algorithm is the amount of memory it needs to run to
completion.
5. Explain Time complexity?
Time complexity is the amount of computer time an algorithm requires to run
to completion.
6. List out the components that are used for space complexity?
a. Instruction Space
b. Environment Stack
c. Data Space.
7. What do asymptotic notation means?
Asymptotic notations are terminology that is introduced to enable us to make
meaningful statements about the time and space complexity of an algorithm.
The different notations are
Big – Oh notation
Omega notation
Theta notation.
8. Define Efficiency of an algorithm?
It denotes the rate at which an algorithm solves a problem of size n. It is
measured by the amount of resources it uses, the time and the space.
9. Define Worst case of an algorithm?
It is the longest time that an algorithm will use over all instances of size n for a
given problem to produce the result.
10. Define Best case of an algorithm?
It is the shortest time that an algorithm will use over all instances of size n for
a given problem to produce the result.
11. Define average case an algorithm?

It is the average time that an algorithm will use over all instances of size n for
a given problem to produce the result.
12. Define Divide and Conquer algorithm?

Divide and Conquer algorithm is based on dividing the problem to be solved
into several, smaller sub instances, solving them independently and then combining
the sub instances solutions so as to yield a solution for the original instance.
13. Mention some application of Divide and Conquer algorithm?

a. Quick Sort
b. Merge Sort
c. Binary search
14. Define dynamic programming algorithm?

Dynamic programming algorithm is a general class of algorithms which solve
problems by solving smaller versions of the problem, saving the solutions to the small
problems and then combining them to solve the larger problems.

15. Mention application of dynamic programming algorithm?
a Efficient Fibonocci number computation
b. Chained matrix multiplication.
c. Longest common subsequence problem
16. Mention the various spaces utilized by a program?
A fixed amount of memory occupied by the space for the program code and
space occupied by the variables used in the program.
A variable amount of memory occupied by the variable whose size is dependent on
the problem being solved. This space increases or decreases depending upon whether
the program uses iterative or recursive procedures
17. What is meant by sorting?
Ordering the data in an increasing or decreasing fashion according to some

relationship among the data item is called sorting.
18. What are the two main classifications of sorting based on the source of data?
Internal sorting- Internal sorting is a process of sorting the data in the main memory.
External sorting- External sorting is a process of sorting in which large blocks of

data stored in storage devices are moved to the main memory and then sorted.
19. What are the various factors to be considered in deciding a sorting algorithm?
 Programming time
 Execution time of the program
 Memory needed for program environment
20. What is the main idea behind insertion sort? When can we use insertion sort?
The main idea of insertion sort is to insert in the i th pass the i th element in A (1) A
(2)...A (i) in its rightful place. Insertion sort is useful only for small files or very nearly sorted
files.
21. What is the main idea behind selection sort?

The main idea behind the selection sort is to find the smallest element among in A (I) A
(J+1)...A (n) and then interchange it with a (J). This process is then repeated for each
value of J.

22. What is the basic idea of shell sort (or Diminishing increment sort).?(November
2015)
Instead of sorting the entire array at once, it is first divide the array into smaller
segments, which are then separately sorted using the insertion sort.
23. What is the purpose of quick sort and list its advantages? (April 2015)
The purpose of the quick sort is to move a data item in the correct direction, just
enough for to reach its final place in the array.
Advantage :Quick sort reduces unnecessary swaps and moves an item to a greater
distance, in one move.
24. What is the average efficiency of heap sort? .
The average efficiency of heap sort is 0 (n(log2 n)) where, n is the number of elements
sorted.
25. What are the properties involved in heap?
1. structure property
2. heap order property
26. Define max and min heap?
A heap in which the parent has a larger key than the child's is called a max heap.
A heap in which the parent has a smaller key than the child's is called a min heap.

1. Sort the sequence 3, 1, 4, 1, 5, 9, 2, 6, 5 using insertion sort. What is the running

time of insertion sort if all elements are equal?
2. Show how heap sort processes the input 142, 543, 123, 65, 453, 879, 572, 434,
111, 242, 811, 102. What is the running time of heap sort for presorted input?
3. Sort 3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5 using quick sort with median-of-three partitioning.
Determine the running time of quick sort for a. sorted input b. reverse-ordered input
c. random input.
4. Show the result of running Shell sort on the input 9, 8, 7, 6, 5, 4, 3, 2, 1
5. Sort the following elements using radix sort 12,98,34,67,54,23,56,45

UNIT V
Hashing: Introduction – Hash function – methods - Hash table implementation - rehashing.
Graph: Directed and un directed graph – representation of graphs – graph traversals: Depth
first search – Breadth first search – transitive closure – spanning trees – application -
topological sorting.
Objective:
 This course is aimed to cover a variety of different problems in Graph Theory.
 To learn the concept and design graph, traversals and its different applications
Outcomes:
 The student will have a strong background of graph theory which has diverse
applications in the areas of computer science, biology, chemistry, physics, sociology,
and engineering.
5.1 Hashing:
Hashing is used for storing relatively large amounts of data in a table called a
hash table. Hashing is a technique used to perform insertions, deletions, and finds the
element in constant average time.
Hash table:
 Hash Table is a data structure in which keys are mapped to array positions by a
hash function.
 Hash table is usually fixed as M-size, which is larger than the amount of data that we
want to store.
Hash function:
Hash function is a mathematical formula, produces an integer which can be used as an
index for the key in the hash table.
 Perfect Hash Function- Each key is transformed into a unique storage location
 Imperfect hash Function- Maps more than one key to the same storage location
Methods of hash function:

 Division Method
 Multiplication Method
 Mid Square Method
 Folding Method
5.1.1 Division-method:
In this method we use modular arithmetic system to divide the key value by some
integer division m. It gives us the location value, where the element can be placed.
L=(k mod m)
L->Location in table
K->key value
m->table size

Eg: k=52, m=10 then
L=(52 mod 10)=2
The key whose value 52 is placed in 2nd location.
2=52%10
8=68%10
9=99%10
4=84%10
5.1.2 Mid square method:

In this we square the value of a key and take the number of digits required to form an
address, from the middle position of squared value
(eg) key =16
Square is 256. Then the address as 56(two digits starting form mid of 256).
5.1.3 Folding method:
In this the key is actually positioned into number of parts, each post having the same
length as their of the required address. Add the value of each parts, ignoring the final carry
to get the required address.
(eg) key is: 12345678
Partitioned:12,34,56,78
Add = 12 +34 + 56+ 78 = 180 (ignore 1 in 180) so the address is 80.
5.1.4 Digit analysis:
This hashing function is a distribution – dependent. Here we make a statistical

analysis of digits of the key, and select those digits which occur quite frequently. Then
reverse or shift the digits to get the address.
(eg) key = 6928661223642. If the statistical analysis 6 & 2 occur frequently.
Reverse 6 & 2 then the address is 26.

5.1.4 Multiplication Method
In multiplication method we compute the hash value in 3 steps
1. Fix a constant A from (0,1)

2. Multiply the key k with A and take the fractional part
3. Multiply the fractional part with m, and take the floor of the result
In summary : h(k) = m { kA }  where { x } denote the fractional part of x.
5.2 Collision Resolution Strategies
Collision : It is a situation in which the hash function returns the same hash key for
more than one record, it is called as collision. Sometimes when we are going to resolve
the collision it may lead to an overflow condition and this overflow and collision condition
makes the poor hash function.
Collision resolution technique:
If there is a problem of collision occurs then it can be handled by apply some technique.
These techniques are called as collision resolution techniques.
 Separate chaining – used with open hashing

 Open addressing – used with closed hashing
5.2.1 Separate chaining:

 In collision handling method chaining is a concept which introduces an additional
field with data i.e. chain.
 Form the Fig 5.1 ,A separate chain table is maintained for colliding data. When
collision occurs then a linked list (chain) is maintained at the home bucket.
For example: Consider the keys to be placed in their home buckets are
131, 3, 4, 21, 61, 24, 7, 97, 8, 9
Then we will apply a hash function as
H(key) = key mod D
where D is the size of table. The hash table will be: Here D = 10
Fig 5.1 Separate chaining hash table.
5.2.2 Open Addressing:

In open addressing, if a collision occurs, alternate cell are tried until an empty cell is
found. Because all the data elements are stored inside the table, a large memory space is
needed for open addressing.
There are three commonly used collision resolution strategy
 Linear probing
 Quadratic probing
 Double hashing
5.2.3 Linear Probing
Example: Consider a hash table with size = 10. Using linear probing insert the keys 72, 27,
36, 24, 63, 81 and 92 into the table.
Let h’(k) = k mod m, m = 10
Initially the hash table can be given as,
Step1: Key = 72
h(72, 0) = (72 mod 10 + 0) mod 10
= (2) mod 10
=2

Since, T[2] is vacant, insert key 72 at this location
Step2: Key = 27
h(27, 0) = (27 mod 10 + 0) mod 10
= (7) mod 10
=7
Step3: Key = 36
h(36, 0) = (36 mod 10 + 0) mod 10
= (6) mod 10
=6
Step4: Key = 24
h(24, 0) = (24 mod 10 + 0) mod 10
= (4) mod 10
=4
Step5: Key = 63
h(63, 0) = (63 mod 10 + 0) mod 10
= (3) mod 10
=3
Step6: Key = 81
h(81, 0) = (81 mod 10 + 0) mod 10= (1) mod 10 = 1
Step7: Key = 92
h(92, 0) = (92 mod 10 + 0) mod 10= (2) mod 10 = 2
Now, T[2] is occupied, so we cannot store the key 92 in T[2]. Therefore, try again for next
location. Thus probe, i = 1, this time.
Key = 92
h(92, 1) = (92 mod 10 + 1) mod 10= (2 + 1) mod 10 = 3
Key = 92
h(92, 2) = (92 mod 10 + 2) mod 10 = (2 + 2) mod 10 = 4
Key = 92
h(92, 3) = (92 mod 10 + 3) mod 10 = (2 + 3) mod 10= 5

Clustering: The main problem with linear probing is clustering, many consecutive elements
form groups and it starts taking time to find a free slot or to search an element.
5.2.2.2 Quadratic probing
• It eliminates the primary clustering problems of linear probing

H(key)=(H(key)+x*x)%table size.
• If quadratic probing is used and the table size is prime, then a new element can
always be inserted if the table is at least half empty.
• If the table is even one more than half full, the insertion could fail [prime].
Fig 5.2 Quadratic Probing

5.2.2.3 Double Hashing:
It is a technique in which two hash function are used when there is

an occurrence of collision. In this method 1 hash function is simple as same as division
method. But for the second hash function there are two important rules which are
 It must never evaluate to zero.

 Must sure about the buckets, that they are probed.
The double hashing is performed by

H1(key)=key % table size
H2(key)=R-(key mod R)
R is a prime smaller than table size
Example: Let us consider following key values 89, 18, 49, 58,69
For first value apply the normal hash function i.e key % table size
hash(89)=89%10=9
hash(18)=18%10=8
Now the key values 89 and 18 are stored at the corresponding location ,when for inserting
the 3rd element 49
hash(49)=49%10=9 , collision occurs
so apply double hashing technique and Choose “R” a prime number smaller than table size,
so we choose R=7 then
hash2(49)=7-(49%7)= 7 - 0 =7
hash2(58)=7-(58%7)= 7 – 2 =5
hash2(69)=7-(69%7)= 7 – 6 = 1
Fig 5.3 Double Hashing

5.3 Rehashing:
Rehashing is a technique in which the table is resized, i.e., the
size of table is doubled by creating a new table. It is preferable if the total size of table is
a prime number. There are situations in which the rehashing is required
 When table is completely full.

 With quadratic probing when the table is filled half.
 When insertions fail due to overflow.
Need of Rehashing:
Rehashing is done because whenever key value pairs are inserted into the map, the load
factor increases, which implies that the time complexity also increases. This might not give
the required time complexity of O(1).
 Hence, rehash must be done, increasing the size of the bucketArray so as to reduce
the load factor and the time complexity.
In such situations, we have to transfer entries from old table to the new table by re-
computing their positions using suitable hash functions.
Fig 5.4 Rehashing
Rehashing can be done as follows:
 For each addition of a new entry to the map, check the load factor.
 If it‟s greater than its pre-defined value (or default value of 0.75 if not given), then
Rehash.
 For Rehash, make a new array of double the previous size and make it the new
bucket array.
 Then traverse to each element in the old bucketArray and call the insert() for each so
as to insert it into the new larger bucket array.
Consider we have to insert the elements 37, 90, 55, 22, 17, 49 and 87. The table size is 10
and will use hash function,
H(key) = key mod table size

Fig 5.5 Collision in Hashing

 From Fig 5.5 Now this table is almost full and if we try to insert more elements
collisions will occur and eventually further insertions will fail. Hence we will rehash by
doubling the table size.
 The old table size is 10 then we should double this size for new table, that becomes
20. But 20 is not a prime number, we will prefer to make the table size as 23. And new
hash function will be
H(key) = key mod 23
Fig 5.6 Rehashing Example

Difference between Separate Chaining and Open Addressing
Separate Chaining Open Addressing
Keys are stored inside the hash table as well All the keys are stored only inside the hash
as outside the hash table. table. No key is present outside the hash
table.
The number of keys to be stored in the hash The number of keys to be stored in the
table can even exceed the size of the hash hash table can never exceed the size of
table. the hash table.
Deletion is easier. Deletion is difficult.
Extra space is required for the pointers to

No extra space is required.
store the keys outside the hash table.
Cache performance is poor. Cache performance is better.

This is because of linked lists which store the This is because here no linked lists are
keys outside the hash table. used.
Some buckets of the hash table are never Buckets may be used even if no key maps
used which leads to wastage of space. to those particular buckets.
5.3 Graph
• A data structure that consists of a set of nodes (vertices) and a set of edges that
relate the nodes to each other
• The set of edges describes relationships among the vertices
• Trees are special cases of graphs.
Definition of graph.
A graph G is defined as follows: G=(V,E)

V(G): a finite, nonempty set of vertices
E(G): a set of edges i.e pairs of vertices,(v,w) where v,w belongs to V
The edges are some time referred as arcs.
We have numbered the graph as 1,2,3,4.
Therefore,
1
V(G)=(1,2,3,4)
E(G) = {(1,2),(1,3),(1,4),(2,3),(2,4)}
2 3
Graph G
5.3.1 Types of graph

Undirected graph- When the edges in a graph have no direction, the graph is called
undirected
Directed graph- When the edges in a graph have a direction, the graph is called directed
(or digraph)
Undirected graph Directed graph
Fig 5.7 Undirected and Directed Graph

Terminologies used in Graph:
Adjacent nodes: two nodes are adjacent if they are connected by an edge
Path: a sequence of vertices that connect two nodes in a graph

Length of path of graph: The length of a path in a graph is the number of edges in the path
In-degree and Out-degree in graph:
Let G be a directed graph
– The in-degree of a node x in G is the number of edges coming to x
– The out-degree of x is the number of edges leaving x.
Degree and Neighbor: Let G be an undirected graph

– The degree of a node x is the number of edges that have x as one of their end
nodes
– The neighbors of x are the nodes adjacent to x
 
Sub Graph : A sub-graph of G is a graph G„ such that V(G‟) V(G ) and E(G „) E(G).
Some of the sub graphs are as follow,

Complete graph: a graph in which every vertex is directly connected to every other
vertex .The Complete graph can be directed or undirected.
Weighted graph: a graph in which each edge carries a cost for traveling between the
nodes.
Fig 5.8 Weighted Graph

Cyclic and acyclic graph:
• A cycle is a path that begins and ends at the same node.

• An acyclic graph is one that has no cycles.
• An acyclic, connected graph is also called an un-rooted tree
• Directed Acyclic Graph: A directed graph is acyclic if it has no cycles.

Graph Connectivity: An undirected graph is said to be connected if there is a path between
every pair of nodes. Otherwise, the graph is disconnected
Fig 5.9 Graph Connectivity
Strongly connected and weekly connected graph:
 In a directed or undirected graph if there is path from every vertex to other vertex
then it is called as strongly connected.
 If a directed graph is not strongly connected , but the underlying graph(without
direction to arcs) is connected then the graph is said to weakly connected
Forest in graph: A forest is an acyclic undirected graph (not necessarily connected), i.e.,
each connected component is a tree.
5.4 Representation of graphs
There are two representations of graphs:
 Adjacency matrix representation
 Adjacency lists representation
Representing the graph as adjacency matrix
In this representation, each graph of n nodes is represented by an n x n matrix A, that is,
a two-dimensional array A. The nodes are labeled 1,2,…,n.
• A[i][j] = 1 if (i,j) is an edge
• A[i][j] = 0 if (i,j) is not an edge
Data Structures for Graphs as Adjacency Matrix
• A two-dimensional matrix or array that has one row and one column for each node in
the graph
• For each edge of the graph (Vi, Vj), the location of the matrix at row i and column j is
1
• All other locations are 0
• For an undirected graph, the matrix will be symmetric along the diagonal
• For a weighted graph, the adjacency matrix would have the weight for edges in the
graph, zeros along the diagonal, and infinity (∞) every place else

Fig 5.10 Example for adjacency matrix – Undirected Graph:
Fig 5.11 Example for adjacency matrix – Directed Graph:
Advantage:
– Simple to implement
– Easy and fast to tell if a pair (i,j) is an edge: simply check if A[i][j] is 1 or 0
Disadvantage:
Even if there are few edges, the matrix takes O(n2) in memory
Representing the graph as adjacency list:

• A graph of n nodes is represented by a one-dimensional array L of linked lists, where
– A list of pointers, one for each node of the graph
– L[i] is the linked list containing all the nodes adjacent from node i.
– The nodes in the list L[i] are in no particular order
Data Structures for Graphs as Adjacency List:

• A list of pointers, one for each node of the graph
• These pointers are the start of a linked list of nodes that can be reached by one edge
of the graph
• For a weighted graph, this list would also include the weight for each edge

Fig 5.12 Example for adjacency list – Undirected Graph:
Fig 5.13 Example for adjacency matrix – Directed Graph:
5.4 Graph traversals

 Travel to every node in the graph
 During Traversals we will visit each node exactly once
 This can be used if we want to search for information held in the nodes or if we want
to distribute information to each node
Two types of Traversal:
• Depth first Search(or) Traversal (DFS)
• Breadth first search(or) Traversal (BFS)
5.4.1 Depth First Search

Depth-first search (DFS) is an recursive algorithm for traversing or searching
tree or graph data structures. One starts at the root by selecting any node as the root and
explores as far as possible along each branch before backtracking.

Backtracking is a general algorithm for finding all (or some) solutions to some
computational problem,. Here backtrack means that when you are moving forward and there
are no more nodes along the current path, you move backwards on the same path to find
nodes to traverse. All the nodes will be visited on the current path till all the unvisited nodes
have been traversed after which the next path will be selected.
This recursive nature of DFS can be implemented using stacks.
Steps involved in Depth-First Traversal:
Step1: Select an unvisited node x, visit it, and treat as the current node
Step2: Find an unvisited neighbor of the current node, visit it, and make it the new current
node;
Step 3: If the current node has no unvisited neighbors, backtrack to the its parent, and make
that parent the new current node;
Step 4: Repeat steps 3 and 4 until no more nodes can be visited.
Step 5: If there are still unvisited nodes, repeat from step 1.
Algorithm
// Given an undirected graph G = (V.E) with n vertices and an array visited (n) initially
set to zero
//This algorithm visits all vertices reachable from v .
//G and VISITED are global >
//VISITED (v)  1
procedure DFS(G,v):
label v as discovered
for all edges from v to w in G.adjacentEdges(v) do
if vertex w is not labeled as discovered then
recursively call DFS(G,w)
init() {
For each u ∈ G
u.visited = false
For each u ∈ G
DFS(G, u)
}

Computing time
 In case G is represented by adjacency lists then the vertices w adjacent to v can be
determined by following a chain of links. Since the algorithm DFS would examine
each node in the adjacency lists at most once and there are 2e list nodes. The time to
complete the search is O (e).
 If G is represented by its adjacency matrix, then the time to determine all vertices
adjacent to v is O(n). Since at most n vertices are visited. The total time is O(n 2).
Output of a depth-first search: The depth first search of a graph outputs a spanning tree
of the vertices reached during the search.
Fig 5.14 Example for DFS- Directed Graph:
Consider the following graph to perform DFS Traversal


5.4.2 Breadth First Search

Breadth-first search (BFS) is a strategy for searching in a graph when search is
limited to essentially two operations: (a) visit and inspect a node of a graph; (b) gain
access to visit the nodes that are neighbor to the currently visited node.
Note: The BFS algorithm uses a queue data structure to store intermediate results as it
traverses the graph
Steps involved in Breadth -First Traversal:

Step 1: Define a Queue of size total number of vertices in the graph.
Step 2: Select any vertex as starting point for traversal. Visit that vertex and insert it into the
Queue.
Step 3: Visit all the adjacent vertices of the vertex which is at front of the Queue which is not
visited and insert them into the Queue.
Step 4: When there is no new vertex to be visit from the vertex at front of the Queue then
delete that vertex from the Queue.
Step 5: Repeat step 3 and 4 until queue becomes empty.
Step 6: When queue becomes Empty, then produce final spanning tree by removing unused
edges from the graph
Procedure BFS(v)
//A breadth first search of G is carried out beginning at vertex v. All vertices visited are
marked as VISITED(I) = 1. The graph G and array VISITED are global and VISITED is
initialised to 0.//
VISITED(v)  1
Initialise Q to be empty //Q is a queue//
loop
for all vertices w adjacent to v do
if VISITED(w) = 0 //add w to queue//
then [call ADDQ(w, Q); VISITED(w)  1] //mark w as VISITED//
end
if Q is empty then return
call DELETEQ(v,Q)
forever
end BFS

Computing Time
 Each vertex visited gets into the queue exactly once, so the loop forever is iterated at
most n times.If an adjacency matrix is used, then the for loop takes O(n) time for each
vertex visited. The Total time is, therefore, O(n 2).
 In case adjacency lists are used the for loop as a total cost of d 1+……..+dn = O(e) where
di = degree(vi). Again, all vertices visited. Together with all edges incident to from a
connected component of G.
Fig 5.15 Example of the Breadth First Traversal
Consider the following graph to perform BFS Traversal

5.5 Transitive Closure- Checking connectivity of the graph by Warshall’s algorithm
Wars hall's algorithm is an efficient method for computing the transitive closure of a
relation. Wars hall's algorithm takes as input the matrix MR representing the relation and
outputs the matrix MR of the relation R*the transitive closure of R.
Warshall's algorithm determines whether there is a path between any two nodes in
the graph. It does not give the number of the paths between two nodes
Example of transitive closure:

Fig 5.16 Checking for Transitive Closure
Algorithm Warshall(a[1..n,1..n])
{
R(0) = A
for i = 1 to n
{
for j = 1 to n
{
for k = 1 to n
{
R(k) = R(k-1)[i,j] or R(k-1)[i,k] and R(k-1)[j,k]
}
}
}
}
Recurrence relating elements R(k) to elements of R(k-1) is:

R(k)[i,j] = R(k-1)[i,j] or (R(k-1)[i,k] and R(k-1)[k,j])
From Fig 5.17 It implies the following rules for generating R(k) from R(k-1):
Rule 1: If an element in row i and column j is 1 in R(k-1),it remains 1 in R(k)
Rule 2: If an element in row i and column j is 0 in R(k-1),it has to be changed to 1 in R(k) it
has to be changed to 1 in R if and only if (k) if and only ifthe element in its row i and column
k and the element in its column j and row k are both 1‟s in R(k-1)
Fig 5.17 Rules for changing Zeros in Warshall Algorithm

Example:
Fig 5.18 Application of Warshall’s Algorithm
From the Fig 5.18 Application of warshall‟s algorithm to the digraph is shaown. New ones
are in bold.
Time efficiency: O(n3)
Space efficiency: Matrices can be written over their predecessors

5.6 Spanning Tree:
A Minimum Spanning Tree (MST) is a sub-graph of an undirected graph such that the
sub-graph spans (includes) all nodes, is connected, is acyclic, and has minimum total
edge weight.
Characteristics of Minimum Spanning Tree (MST)

• A minimum spanning tree connects all nodes in a given graph
• A MST must be a connected and undirected graph
• A MST can have weighted edges
• Multiple MSTs can exist within a given undirected graph
Note: The minimum spanning tree may not be unique. However, if the weights of all the
edges are pair wise distinct, it is indeed unique
There are two popular techniques for constructing a minimum cost spanning tree.
 Prim’s algorithm
 Kruskal’s algorithm
5.6.1 Prim’s Algorithm
Prim’s Algorithm.
 Prim's algorithm for finding an MST is a greedy algorithm.
 Start by picking any vertex r to be the root of the tree. •
 While the tree does not contain all vertices in the graph find shortest edge leaving
the tree and add it to the tree.
Prim’s Selection rule

• Select the minimum weight edge between a tree-node and a non-tree node and
add to the tree
• A group of edges that connects two set of vertices in a graph is called cut in graph
theory

Prim()
S = new empty set
for i = 1 to n
d[i] = infinity
while S.size() < n
x = inf
v = -1
for each i in V - S // V is the set of vertices
if x >= d[v]
then x = d[v], v = i
d[v] = 0
S.insert(v)
for each u in adj[v]
do d[u] = min(d[u], w(v,u))
. Example for Prim’s Algorithm:
Fig 5.19 Prim’s Algorithm

Vertex v1 is known Vertex v4 is known

Initial Configuration table
vertex v7 known Vertex v5 & v6 visited

Vertex v2 & v3 known
The edges in the spanning tree can be read
from the table: (v2, v1), (v3, v4), (v4, v1), (v5, v7), (v6, v7), (v7, v4). The total cost is 16.
Algorithm Complexity:The running time is O(|V|2) without heaps, which is optimal for
dense graphs, and O(|E| log |V|) using binary heaps, which is good for sparse graphs.
5.6.2 Kruskal’s algorithm

Kruskal‟s algorithm uses a greedy technique to compute a minimum spanning tree.
A MST can be grown from a forest of spanning trees by adding the smallest edge
connecting two spanning trees.
 In general, kruskal‟s algorithm maintains a forest-a collection of trees. Initially, there
are |V| single node trees.
 Adding an edge merges two trees into one. When the algorithm terminates, there is
only one tree, which is called as minimum spanning tree.
Data Structures used in Kruskal’s Algorithm:
 Find (U) returns the root of the tree that contains the vertex U.
 Union (S,U,V) merge the two trees by making the root pointer of one node point to
the root node of the other tree.
Algorithm kruskal (E, cost, n, t)
//E – set of all the edges in a graph G
//G – Graph consist of n vertices
//cost[u,v] – minimum edge cost in a graph
{
Construct a heap out of the edge costs using heapify; // construct heap tree.
For i=1 to n do
{
Parent[i]=-1
}
i=0;
mincost = 0.0;
while ((i<n-1) and (heap not empty)) do
{
Delete a minimum cost edge (u,v) from the heap and reheapify using adjust;
j=find(u);
k=find(v);
if(j≠k) then // edge does not form a cycle
{
i=i+1;
t[i,1] =u;
t[i,2] =v;
mincost=mincost + cost[u,v]
union[j,k];
}
}
If(i≠n-1) then
write (“No spanning tree”);
Else return mincost;
}
Algorithm find(i) Algorithm Union(i,j)

{ {
While (P[i]≥0)do P[i]:=j
{
i=p[i] }
}
Return i;
}

Fig 5.20 Kruskal’s Algorithm
5.9 Topological sorting

Topological sort.(Application of Breadth first Search)
A topological sort or topological ordering of a directed graph is a linear ordering
of its vertices such that for every directed edge (v, w) from vertex v to vertex w, v comes
before w in the ordering.
Graphs in which topological sorting is performed:
A topological ordering is possible if and only if the graph has no directed cycles, that is, if it
is a directed acyclic graph (DAG)
Definition of Topological sort:
Given a digraph G = (V, E), find a linear ordering of its vertices such that:
for any edge (v, w) in E, v precedes w in the ordering

Example for Topological Sorting:The topological sort of a directed graph. Here F is
independent so it can be placed in any location .
• Topological sort is not unique.

• The following are all topological sort of the graph below:
A directed graph with cycle cannot be sorted. The below Figure show as an example where
topological sorting cannot be performed in cyclic graph
Condition for cycle in a graph:

• Given a digraph G = (V,E), a cycle is a sequence of vertices v1,v2, ...,vk such that
k < 1 and V1 = Vk als (Vi,Vi+1) in E for 1 < i < k.
• G is acyclic if it has no cycles
Steps followed in topological sorting algorithm:
Step 1: Identify vertices that have no incoming edges •
The "in-degree" of these vertices is zero
(a)If no such vertices, graph has only cycle(s) (cyclic graph) • Topological sort not
possible so stop.
(b) If such vertex available Select one such vertex

Step 2: Delete this vertex of in-degree 0 and all its outgoing edges from the graph.
Place it in the output.
Step 3: Repeat steps 1 and 2 until the graph is empty.
Fig 5.21 Topological Ordering Algorithm: Example

Step1: Step2: Step3:
Step 4: Step 5: Step 6:
Step 7 Final Topological Sorted List

Two Marks
1. Define Hashing.
Hashing is the transformation of string of characters into a usually shorterfixed length
value or key that represents the original string. Hashing is used toindex and retrieve items in
a database because it is faster to find the item using theshort hashed key than to find it
using the original value.
2. What do you mean by hash table? (November 2015)

The hash table data structure is merely an array of some fixed size,containing the
keys. A key is a string with an associated value. Each key ismapped into some number in
the range 0 to tablesize-1 and placed in theappropriate cell.
3. What do you mean by hash function? (May 2014)

A hash function is a key to address transformation which acts upon agiven key to
compute the relative position of the key in an array. The choice ofhash function should be
simple and it must distribute the data evenly. A simplehash function is hash_key=key mod
tablesize.
4. Write the importance of hashing.

• Maps key with the corresponding value using hash function.
• Hash tables support the efficient addition of new entries and the time spenton
searching for the required data is independent of the number of itemsstored.
5. What do you mean by collision in hashing?

When an element is inserted, it hashes to the same value as an already
inserted element, and then it produces collision.
6. What are the collision resolution methods? (December 2014)

• Separate chaining or External hashing
• Open addressing or Closed hashing
7. What do you mean by separate chaining?

Separate chaining is a collision resolution technique to keep the list of allelements that
hash to the same value. This is called separate chaining becauseeach hash table element is
a separate chain (linked list). Each linked list containsall the elements whose keys hash to
the same index.
8. Write the advantage of separate chaining.

• More number of elements can be inserted as it uses linked lists.
9. Write the disadvantages of separate chaining.

• The elements are evenly distributed. Some elements may have more
elements and some may not have anything.

• It requires pointers. This leads to slow the algorithm down a bit because of
the time required to allocate new cells, and also essentially requires the
implementation of a second data structure.
10. What do you mean by open addressing?

Open addressing is a collision resolving strategy in which, if collision occursalternative
cells are tried until an empty cell is found. The cells h0(x), h1(x), h2(x),….are tried in
succession, where hi(x)=(Hash(x)+F(i))mod Tablesize with F(0)=0. Thefunction F is the
collision resolution strategy.
11. What are the types of collision resolution strategies in open addressing?
• Linear probing
• Quadratic probing
• Double hashing
12. What do you mean by Probing?

Probing is the process of getting next available hash table array cell.
13. What do you mean by linear probing?

Linear probing is an open addressing collision resolution strategy in which F is alinear
function of i, F(i)=i. This amounts to trying sequentially in search of an emptycell. If the table
is big enough, a free cell can always be found, but the time to do socan get quite large.
14. What do you mean by primary clustering?

In linear probing collision resolution strategy, even if the table is relatively
empty, blocks of occupied cells start forming. This effect is known as primary
clustering means that any key hashes into the cluster will require several attempts
to resolve the collision and then it will add to the cluster.
15. What do you mean by quadratic probing?

Quadratic probing is an open addressing collision resolution strategy in whichF(i)=i2.
There is no guarantee of finding an empty cell once the table gets half full ifthe table size is
not prime. This is because at most half of the table can be used asalternative locations to
resolve collisions.
16. What do you mean by secondary clustering?

Although quadratic probing eliminates primary clustering, elements thathash to the
same position will probe the same alternative cells. This is known assecondary clustering.
17. What do you mean by double hashing?

Double hashing is an open addressing collision resolution strategy inwhich
F(i)=i.hash2(X). This formula says that we apply a second hash function toX and probe at a
distance hash2(X), 2hash2(X),….,and so on. A function such ashash2(X)=R-(XmodR), with
R a prime smaller than Tablesize.

18. What do you mean by rehashing? (April 2015)
If the table gets too full, the running time for the operations will start takingtoo long and
inserts might fail for open addressing with quadratic resolution. Asolution to this is to build
another table that is about twice as big with theassociated new hash function and scan
down the entire original hash table,computing the new hash value for each element and
inserting it in the new table.This entire operation is called rehashing.
.
19.Classify the Hashing Functions based on the various methods by which the key
value is found.
 Direct method,
 Subtraction method,
 Modulo-Division method,
 Digit-Extraction method,
 Mid-Square method,
 Folding method,
 Pseudo-random method.
20. Define Graph.

A graph G consist of a nonempty set V which is a set of nodes of the graph, a setE
which is the set of edges of the graph, and a mapping from the set for edge E to a set
ofpairs of elements of V. It can also be represented as G=(V, E).
21. Define adjacent nodes.

Any two nodes which are connected by an edge in a graph are called adjacentnodes.
For example, if an edge x ε E is associated with a pair of nodes (u,v) where u, vεV, then we
say that the edge x connects the nodes u and v.
22. What is a directed graph and undirected graph??

A graph in which every edge is directed is called a directed graph. A graph in which
every edge is undirected is called a undirected graph.
23. What is a simple graph and weighted graph?

A simple graph is a graph, which has not more than one edge between a pair of
nodes than such a graph is called a simple graph. A graph in which weights are assigned
to every edge is called a weighted graph.
24. Define outdegree and indegree of a graph?

In a directed graph, for any node v, the number of edges which have v as their initial
node is called the out degree of the node v.
In a directed graph, for any node v, the number of edges which have v as their
terminal node is called the indegree of the node v.

25. Define path in a graph?
The path in a graph is the route taken to reach terminal node from a starting node.
26. What is meant by strongly connected in a graph andweakly connected??

An undirected graph is connected, if there is a path from every vertex to every
other vertex. A directed graph with this property is called strongly connected.
When a directed graph is not strongly connected but the underlying graph is
connected, then the graph is said to be weakly connected.
27.Namethe different ways of representing a graph?(April 2015)

a.Adjacency matrix
b. Adjacency list
28.What are the two traversal strategies used in traversing a graph?
Traversing a graph is an efficient way to visit each vertex and edge exactly once.
The two graph traversal techniques are
a.Breadthfirstsearch
b. Depth first search
29. What is a minimum spanning tree and list two algorithms to find minimum
spanning tree?
A minimum spanning tree of an undirected graph G is a tree formed from
graph edges that connects all the vertices of G at the lowest total cost.
Two algorithms to find minimum spanning tree
Kruskal‟salgorithm
Prim‟s algorithm
30. List the two important key points of depth first search.
i) If path exists from one node to another node, walk across the edge – exploring
the edge.
ii) If path does not exist from one specific node to any other node, return to the
previous node where we have been before – backtracking.
31.DifferentiateBFSandDFS.(November2015)
No. DFS BFS

1. Backtracking is possible from a Backtracking is not possible
dead end
2. Vertices from which exploration is The vertices to be explored are
incomplete are processed in a organized as a
3. Search is done in one particular
LIFO order The
FIFOvertices
queue in the same level
direction are maintained
parallely

1. Given input {4371, 1323, 6173, 4199, 4344, 9679, 1989} and a hash function h(x) = x
(mod ( ) 10), show the resulting
a. separate chaining hash table
b. hash table using linear probing
c. hash table using quadratic probing
d. hash table with second hash function h2(x) = 7 − (x mod 7)
What are the advantages and disadvantages of the various collision resolution
strategies?
2. Find a minimum spanning tree for the graph in Figure using both Prim‟s and Kruskal‟s
algorithms. b. Is this minimum spanning tree unique? Why?
3. Find the strongly connected components in the graph
4. Perform the BFS and DFS graph traversal on the following graph

5. Consider a directed acyclic graph D given in Figure Sort the nodes of D; by applying
topological sort on D

University Questions
May 2019
Part-A
1. What is abstract data type?
2. State the difference between array and linked list.
3. Define a priority queue.
4. Define Circular queue.
5. What are the difference between a tree and a binary tree?
6. What is meant by binary tree traversal?
7. What are the two classification of sorting based on source of data?
8. What is the basic idea of shell sort?
9. What do you mean by hash function?
10. List the algorithms to find minimum spanning tree.
Part-B
11. What is a Stack? Explain its operation with example.

12. Write an algorithm to convert infix to postfix expression and explain it with example.
13. What are circular queues? Write down the routines for inserting and deleting
elements from a circular queue implemented using arrays.
14. Explain the operations of Priority queue.
15. Explain in detail insertion into AVL Trees.
16. Write a routine to perform insertion and deletion in B-Tree
17. Sort the following numbers using Quick Sort procedure and discuss the time
complexity and space complexity of this algorithm 42,12,-8,98,67,83,08,104,07
18. Difference between merge sort and radix sort with suitable example
19. Explain different types of Hash Function with example.
20. Explain in detail about Topological sort.
November 2018
Part-A
1. What is abstract data type? Give any two example.

2. State any four application of stack
3. Write down the few metrics of circular queue with real time applications
4. Mention some characterisitics of stack and queue.
5. Write in order traversal algorithm of a binary tree
6. How does AVL tree differ from binary search tree
7. Write the algorithm of bubble sort.
8. Compare and contrast the quick sort and heap sort
9. What are the techniques used for hash function?
10. Differentiate between the depth first search and breadth first search

Part-B
11. Explain the operation of inserting an element at front, middle and at the rear in a
double linked list with example
12. Illustrate the algorithm to display the content of a stack with example
13. Briefly explain the operation of queue with example
14. Explain the following concept with illustration.
a) Linked List
b) Priority queue
15. Explain the process of finding the minimum and maximum element of binary search
tree
16. a) Paraphrase Splay tree with example
b) Discuss the B+ tree and compare with B tree
17. Explain the insert and delete operation of heap with example
18. With a neat diagram explain about radix sort with example.
19. Describe about the application of hashing and explain about the rehashing.
20. Write short notes on the following:
a) Breadth first search with example
b) Spanning tre
May 2018
1. What do you understand by abstract data type?Give examples
2. What is recursion?
3. What do you understand by “front=rear” in a queue system?
4. What is a circular queue?
5. What do you mean by a complete binary tree?Give an example.
6. What is a splay tree?
7. What is meant by sorting? What are its types?
8. Write down the total number of comparisons performed by bubble sorting?
9. What is rehashing?
10. Define siblings and path length.
PART B (5 X 11=55)
11. (a)How to add two polynomials using singly linked list? Explain.
(b)Write a procedure to insert a node in to a doubly linked list.
12. (a)Write a procedure to convert an infix to postfix form. Give an example.
(b)Write a note on reverse polish notation.
13. (a)Write the procedure to manipulate the queue.
(b)List the applications of queue ADT.
14. (a)How to implement a queue using a linked list?
(b)What is a circular queue? How to manipulate the same?
15. What is meant by traversals? Explain the binary tree traversals with examples.
16. (a)Draw a binary tree for the following infix expression A/B**C*D+E
(b)Explain the concept of rotation in AVL trees with examples
17. (a)Write the recursive procedure for quick sort.

(b)Explain the working of shell sorting along with its efficiency measures.
18. (a)With an algorithm,explain the heap sort in detail.
(b)Write down the concept of radix sorting.
19. (a)How to overcome the collision during hashing?Explain
(b)Explain any two methods used to represent the graphs in detail.
20. (a)What are the three types of edges?
(b)How to traverse a graph using BFS method?
(c) Explain the Prim’s algorithm to find the minimum spanning tree.
November 2017
Part A(10 X 2 = 20)
Answer All Questions
1. What is a Stack?
2. List the applications of stack
3. Mention the use of priority queue.
4. Write the applications of queue.
5. What is a binary tree?
6. List the properties of AVL tree.
7. What is a bubble sort?
8. Mention the uses of radix sort?
9. Name the various hashing methods
10. What are the graph traversal methods?
PART B (5 X 11=55)
11. Explain in detail about the conversion of an expression from infix to postfix form.
12. Discuss on the linked implementation of stack
13. Write in detail about linked list implementation of queue
14. Discuss on double ended queue.
15. Explain the expression tree with examples.
16. Write about binary search trees.
17. Explain quick sort with example
18. Discuss about merge sort.
19. Explain hash table implementation and rehashing.
20. Write about representation of graphs and spanning trees.
December 2016
Part A(10 X 2 = 20)
1. What is the need for different data structures?

2. Write the prefix of a+b*c/d.
3. Specify the structure of multiple stacks.
4. Mention the difference between queue and double ended queue.
5. What is tries structure?
6. Mention the difference between B- tree and B+ tree.
7. Specify the time complexity of insertion sort and merge sort.
8. Sort the following data using radix sort 23,17,31
9. Mention any two hashing functions

10. What is topological sorting?
PART B (5 X 11=55)
11. Explain the storage representations and operations on stack with necessary
algorithms.
12. (a)Explain the algorithm for inserting an element in the linked list with an
example.(7)
(b)Explain the structure of doubly linked list.(4)
13. Explain the operations on circular queue with necessary algorithms
14. (a)Explain the structure and operations on priority queue
(b)Briefly explain any one application on queue
15. Explain the three tree traversal methods with necessary algorithms
16. (a)Explain the structure and operations of binary search tree
(b)Explain the structure of AVL tree.
17. Explain heap sort algorithm with an example.
18. (a)Write and explain bubble sort algorithm.(7)
(b)Sort the following data using quick sort 95,25,86,11,45
19. Explain the hashing methods with an example
20. Explain the graph traversals methods with an example
April 2016
Part A(10 X 2 = 20)

1. Write statements to declare integer pointer and float pointer .Also write the
statement to convert float pointer into integer pointer.
2. What is a stack?Mention the order followed to add or delete an element.
3. What is meant by underflow?
4. Distinguish ascending priority queue from descending priority queue.
5. Define the term “complete binary tree”
6. What is an AVL tree?Write its running time.
7. Write the difference between internal sorting and external sorting.
8. Define”maxheap”.Also write the complexity of heap sort.
9. What is meant by Hash collision?Name the methods that are used to detail the
crisis.
10. Write down the condition of a spanning forest for a given graph.
PART B (5 X 11=55)
11. Give a detail description on postfix operations illustrate with an expression.Also
write the program to evaluate it.
12. Summarize the concept of recursion with tower of Hanoi problem.Also write the
program for the problem
13. Give a detailed note on linked list.Also narrate the procedure of inserting and
deleting nodes from a list with suitable illustrations

14. With C programs , explain the various manipulations that can be applied to a
queue.
15. Compare and contrast B-tree with B+tree through suitable examples.
16. List the various tree traversal notations and explain with examples and program
segments.
17. With program coding,explain the procedure of doing bubble sort for a given set of n
numbers
18. Explain the concept of radix sort with suitable illustrations and program.
19. Describe the concept of hash function .Also explain any two hash methods in detail
20. Give a detailed note on depth first search traversal with suitable examples and
program.
November 2015
Part A (10 X 2 =20)
1. Define ADT.
2. List some application of stack.
3. What is circular queue?
4. What do you mean by priority queue?
5. Define binary search tree
6. Differentiate B tree and B+ tree
7. How will you measure the efficiency of sorting
8. What is the basic idea of shell sort
9. What is hash table?
10. Define the terms : BFS and DFS.
PART B (5 X 11 = 55)
11. Write an algorithm for converting infix expression to postfix expression with an
Example
12. Write an algorithm to perform the following operations on a singly linked list
i. Insert new node at beginning
ii. Insert new node at middle
iii. Delete a node from last
iv. Count the number of nodes.
13. Explain the operations of priority queue.
14. Write an algorithms for insertion and deletion operations in a circular queue.
15. Construct an expression tree for the expression A + ( B – C )* D + ( E * F )
16. Explain in detail about insertion in AVL trees
17. State and explain the algorithm to perform heap sort. Also analyze the time
complexity of the algorithm
18. State and explain the algorithm to perform Quick sort. Also analyze the time
complexity of the algorithm
19. Explain the minimum cost spanning Tree algorithms with an example.
20. Explain the various applications of Depth First Search
April 2015
Part A(10 X 2 = 20)
1. Define ADT.
2. What is circular linked list?
3. What do you mean by priority queues?
4. Define double ended queues.
5. Perform RR rotation in AVL tree with an example.
6. Give some of the applications of B-tree
7. List the advantages of quick sort
8. Write the worst case and best case analysis of merge sort.
9. Give the adjacency matrix for the following directed graph
V1 V2
V3 V4
10. Annotate the term rehashing
PART B –(5 X 11=55)
11. (a) What is stack and how is it implemented? Explain.

(b) List the application of stack.
12. What is linked list and how can we implement it using array? Explain.
13. (a) Describe about the array implementation of circular queue
(b) Give the limitation of queues.
14. Explain about the implementation of queue using linked list with example.
15. (a) Traverse the given tree using inorder, preorder and postorder t raversal
20
20 20
20 20 20 20
(b) Compare binary tree and binary search tree .
16. (a) Insert the numbers into binary search tree 8,5,10,15,20,18,3
(b) What is tries? Give some of the application of tries
17. Define quick sort. Explain its algorithm with an example
18. Write the procedure for heap sort and trace the given example.
18,13,10,8,5,15.
19. (a) Define hash function and explain its method in detail.
(b) Write the routine for performing breadth first search.

20. What do you mean by topological sorting? and write the routine to perform
topological sort with example.
December 2014
Part A (10 X 2 =20)
1. Is a relation a data structure or an abstract data type? What is a hash table?
2. Consider the following binary search tree
B F
A E G
Reconstruct the binary tree after deleting character D.

3. How is circular list implemented?
4. State any two applications of linked list
5. Write an equivalent postfix expression for the infix expression (a+b)*(c-d)/(e+f).
What data structure is to do the conversion?
6. State the operations performed using Stack and Queue
7. List the needs for non – linear data structures. Give the representation used for
graph data structures.
8. Give the merits and demerits of depth first search.
9. Differentiate between B-tree indexing and Trie indexing?
10. What is collision resolution? Give an example.
PART B (5 X 11 = 55)
Answer all questions
11. Explain the merge sort algorithm using the following set of data. Compare the result
by constructing heap sort for the same set of data:
45,32,71,27,53,33,12,67
12. What are primitive data structures and Linear data structures? Illustrate with
examples. Also explain the significance of Abstract data structures and its uses
13. State and explain the algorithm used to perform addition of two polynomials using
Linked list
14. Explain representation of polynomials and sparse matrices with an application of its
use
15. State the operations performed in a stack. How many times you will pop a stack of
10 elements to reach the sixth element from the top ? Discuss any two
applications of stack and queue.
16. Write an algorithm to perform the operation s for a queue data structure. Explain
priority queue with an example

17. Explain the different tree traversal algorithms. Illustrate the inorder, preorder and
postorder traversal with an example.
18. Compare them breadth first search and depth first search algorithm and illustrate
with an example
19. (a) Show the stages of growth of an order 4 B-Tree when the following keys are
inserted in the order given as 84,82,29,99,65,12,50,28,58,71,92,75,19,55.
(b) Show the change in the B-Tree constructed by Q.19 (a) when the following keys
are deleted in the given order 28,50,75
20. (a)Construct an AVL Tree for the following set of number
1,2,3,4,5,6,7,8,9,10,11,12,13
(b) Write the for algorithm for AVL tree construction and discuss a supplication of
AVL trees
May 2014
Part A (10 X 2 =20)
1. Define abstract data type.
2. What is radix sort?
3. How do you represent sparse matrices?
4. Mention the advantages of circular linked list over singly linked list
5. What are double ended queues?
6. Differentiate between stack and queue
7. Define binary tree
8. How do you implement linked representation of binary trees?
9. What is the uses of tree indexing?
10. What is hash function? Give an example.
PART B (5 X 11 = 55)
11. Briefly explain the types of indexed search techniques

12. What is quick sort? Explain the quick sort technique with suitable example
13. Discuss about the insertion and deletion operation in doubly linked list with suitable
diagrams and routine
14. Explain the various application of linked list.
15. Briefly explain about the array and linked implementation of queues.
16. Discuss any two application of stack with suitable example
17. Explain the different types of binary tree traversal with example.
18. What is graph traversal? Compare and contrast between breadth first search and
depth first search.
19. Explain about the insertion and deletion operation in binary search trees.
20. Discuss about the types of open addressing techniques with example.

November 2013
Part A (10 X 2 =20)

1. What is meant by shell sort?
2. Define the term “Data structures”.
3. What do you mean by array?
4. What are the characteristics of sparse matrices?
5. What do you mean by priority queues?
6. What do you mean by double ended queues?
7. State the properties of tree traversals.
8. What are the applications of graphs?
9. What do you mean by binary tree indexing?
10. What do you means by AVL trees?
PART B (5 X 11 = 55)
11. State and explain the classification of data structures.

12. Explain briefly about indexed search techniques.
13. Explain the array implementation of linked list with an example
14. Describe the detail about multi linked list.
15. List and explain any 2 application of queues.
16. Describe briefly about stack ADT. Write the procedure to perform the various
operation over it.
17. State and explain array and linked implementation of binary trees.
18. Explain the various tree traversal techniques with an example.
19. Explain the detail about B+ trees.
20. Describe in detail about the concepts of collision resolution and open addressing .

GATE QUESTIONS
UNIT-I
Stack
Gate 2016 - CSE
1. Let Q denote a queue containing sixteen numbers and S be an empty stack. Head(Q) returns
the element at the head of the queue Q without removing it from Q. Similarly Top(S) returns
the element at the top of S without removing it from S. Consider the algorithm given below.
The maximum possible number of iterations of the while loop in the algorithm is______
[This Question was originally a Fill-in-the-Blanks question]
(A) 16
(B) 32
(C) 256
(D) 64
Answer: (C)
Explanation: The worst case happens when the queue is sorted in decreasing order. In worst
case, loop runs n*n times.
Queue: 4 3 2 1
Stack: Empty
321
4
3214
Empty
214
3
2143
Empty
143
2
1432
Empty
432
1
32
14
324
1
24
13
243
1
43
12
3
124
34
12
4
123
Empty
1234
Gate 2014 - CSE

2. The result evaluating the postfix expression 10 5 + 60 6 / * 8 – is
(A) 284
(B) 213
(C) 142
(D) 71
Answer: (C)
Following is algorithm for evaluation postfix expressions.

1) Create a stack to store operands (or values).
2) Scan the given expression and do following for every scanned element.
…..a) If the element is a number, push it into the stack
…..b) If the element is a operator, pop operands for the operator from stack. Evaluate the
operator and push the result back to the stack
3) When the expression is ended, the number in the stack is the final answer
Linked List
Gate 2017-CSE
3. Consider the C code fragment given below.
typedefstruct node
{
int data;
node* next ;
} node;
void join(node* m, node* n)

{
node* p = n;
while (p->next != NULL)
{
p = p->next;
}
p–>next = m;
}
Assuming that m and n point to valid NULL- terminated linked lists, invocation of join will
(A) append list m to the end of list n for all inputs
(B) either cause a null pointer dereference or append list m to the end of list n
(C) cause a null pointer dereference for all inputs.
(D) append list n to the end of list m for all inputs.
Answer: (B)
Explanation: As it is stated in the question, that m and n are valid Lists but not explicitly
specified if the lists are empty or not. We can have two cases:
1. Case 1: If lists are not NULL : Invocation of join will append list m to the end of list n
if the lists are not NULL. For Example:Before join operation :
m =1->2->3->4->5->null
n =6->7->8->9->nullAfter join operation :
6->7->8->9->1->2->3->4->5->null
2. Case 2: If lists are NULL : If the list n is empty and itself NULL, then joining and
referencing would obviously create NULL pointer issue.
Gate 2017-CSE
4. Let A be an array of 31 numbers consisting of a sequence of 0’s followed by a sequence of
1’s. The problem is to find the smallest index i such that A[i] is 1 by probing the minimum
number of locations in A. The worst case number of probes performed by an optimal
algorithm is________.
Note: This questions appeared as Numerical Answer Type.
(A) 2
(B) 3
(C) 4
(D) 5
Answer: (D)
Explanation: The best way to solve such a problem is by using Binary Search. Search the sorted
array by repeatedly dividing the search interval in half. Begin with an interval covering the
whole array. If the value of the search key is less than the item in the middle of the interval,
narrow the interval to the lower half. Otherwise narrow it to the upper half.
Find mid element
 Is mid = 1 ?
 Is mid >1?(not possible here)
 Is mid <1 ?
Proceed accordingly, Worst case of this problem will be 1 at the end of the array i.e 00000…..1
OR 1…….0000. It will take log n time worst case.
n=31, Hence log 231 = 5.
Therefore, option D is correct.
Gate 2016-CSE
5. N items are stored in a sorted doubly linked list. For a delete operation, a pointer is provided
to the record to be deleted. For a decrease-key operation, a pointer is provided to the record
on which the operation is to be performed. An algorithm performs the following operations
on the list in this order:
Θ(N) delete, O(log N) insert, O(log N) find, and Θ(N) decrease-key
What is the time complexity of all these operations put together
(A) O(Log2N)
(B) O(N)
(C) O(N2)
(D) Θ(N2 Log N)
Answer: (C)
Explanation: The time complexity of decrease-key operation is Θ(1) since we have the pointer
to the record where we have to perform the operation. However, we must keep the doubly linked
list sorted and after the decrease-key operation we need to find the new location of the key. This
step will take Θ(N) time and since there are Θ(N) decrease-key operations, the time complexity
becomes O(N²).
Note that the other three operations have a lower bound than this one.
Gate 2015-CSE
6. An algorithm performs (logN)1/2 find operations, N insert operations, (logN)1/2 operations,

and (logN)1/2 decrease-key operations on a set of data items with keys drawn from a linearly
ordered set. For a delete operation, a pointer is provided to the record that must be deleted.
For the decrease-key operation, a pointer is provided to the record that has its key decreased.
Which one of the following data structures is the most suited for the algorithm to use, if the
goal is to achieve the best total asymptotic complexity considering all the operations?
(A) Unsorted array
(B) Min-heap
(C) Sorted array
(D) Sorted doubly linked list
Answer: (A)
Explanation: The time complexity of insert in unsorted array is O(1), O(Logn) in Min-Heap,
O(n) in sorted array and sorted DLL.
1. For unsorted array, we can always insert an element at end and do insert in O(1) time
2. For Min Heap, insertion takes O(Log n) time. Refer Binary Heap operations for details.
3. For sorted array, insert takes O(n) time as we may have to move all elements worst case.
4. For sorted doubly linked list, insert takes O(n) time to find position of element to be
inserted.
Since number of insertion operations is asymptotically higher, unsorted array is preferred.
Gate 2015-CSE
7. An unordered list contains n distinct elements. The number of comparisons to find an

element in this list that is neither maximum nor minimum is
(A) Θ(nlogn)
(B) Θ(n)
(C) Θ(logn)
(D) Θ(1)
Answer: (D)
Explanation: We only need to consider any 3 elements and compare them. So the number of
comparisons is constants, that makes time complexity as Θ(1)
The catch here is, we need to return any element that is neither maximum not minimum.
Let us take an array {10, 20, 15, 7, 90}. Output can be 10 or 15 or 20
Pick any three elements from given liar. Let the three elements be 10, 20 and 7.
Using 3 comparisons, we can find that the middle element is 10.
UNIT-II
Queue
Gate 2019 - CSE
1. A queue is implemented using a non-circular singly linked list. The queue has a head pointer
and a tail pointer, as shown in the figure. Let n denote the number of nodes in the queue. Let
'enqueue' be implemented by inserting a new node at the head, and 'dequeue' be implemented
by deletion of a node from the tail.
Which one of the following is the time complexity of the most time-efficient implementation of
'enqueue' and 'dequeue, respectively, for this data structure?
A.Θ(1), Θ(1)
B.Θ(1), Θ(n)
C.Θ(n), Θ(1)
D.Θ(n), Θ(n)
Answer : Option (B)
Solution:
For Enqueue operation, performs in constant amount of time (i.e., Θ(1)), because it modifies
only two pointers, i.e.,Create a Node P.
P-->Data = Data
P-->Next = Head
Head = P
For Dequeue operation, we need address of second last node of single linked list to make NULL
of its next pointer. Since we can not access its previous node in singly linked list, so need to
traverse entire linked list to get second last node of linked list, i.e.,temp = head;
while( temp-Next-->Next != NULL){
temp = temp-Next;
}
temp-->next = NULL;
Tail = temp;
Since, we are traversing entire linked for each Dequeue, so time complexity will be Θ(n). Option
(B) is correct.
Gate 2016 - CSE
2. A queue is implemented using an array such that ENQUEUE and DEQUEUE operations are
performed efficiently. Which one of the following statements is CORRECT (n refers to the
number of items in the queue)?
(A) Both operations can be performed in O(1) time
(B) At most one operation can be performed in O(1) time but the worst case time for the other
operation will be Ω(n)
(C) The worst case time complexity for both operations will be Ω(n)
(D) Worst case time complexity for both operations will be Ω(log n)
Answer: (A)
Explanation: We can use circular array to implement both in O(1) time. See below article for
details.
Gate 2014 - CSE
3. Suppose implementation supports an instruction REVERSE, which reverses the order of

elements on the stack, in addition to the PUSH and POP instructions. Which one of the
following statements is TRUE with respect to this modified stack?
(A) A queue cannot be implemented using this stack.
(B) A queue can be implemented where ENQUEUE takes a single instruction and DEQUEUE
takes a sequence of two instructions.
(C) A queue can be implemented where ENQUEUE takes a sequence of three instructions and
DEQUEUE takes a single instruction.
(D) A queue can be implemented where both ENQUEUE and DEQUEUE take a single
instruction each.
Answer: (C)
Explanation: To DEQUEUE an item, simply POP.

To ENQUEUE an item, we can do following 3 operations
1) REVERSE
2) PUSH
3) REVERSE
UNIT-III
Sorting
Gate 2019 - CSE
1. An array of 25 distinct elements is to be sorted using quicksort. Assume that the pivot
element is chosen uniformly at random. The probability that the pivot element gets placed in
the worst possible location in the first round of partitioning (rounded off to 2 decimal places)
is _________.
(A) 0.08
(B) 0.0016
(C) 0.04
(D) 0.0008
Answer: (A)
Explanation: Given an array of 25 distinct elements, and pivot element is chosen uniformly
randomly. So, there are only 2 worst case position in the pivot element is either first (or) last.
Therefore, required probability is,
= 2/25
= 0.08
So, option (A) is correct.
Gate 2019-CSE
2. There are n unsorted arrays: A1, A2, ….,An. Assume that n is odd. Each of A1, A2,
….,Ancontains n distinct elements. There are no common elements between any two arrays.
The worst-case time complexity of computing the median of the medians of A1, A2, ….,Anis
________ .
(A) Ο(n log n)
(B) Ο(n2)
(C) Ο(n)
(D) Ω(n2log n)
Answer: (B)
Explanation: Since given arrays are not sorted, so the time complexity to find median is O(n) in
an unsorted array. You need to apply this apgorithm n time to find all medians and again once to
find median of all these medians, so total time complexity is,
= O(n)*O(n) + O(n)
= O(n2) + O(n)
≈ O(n2)
So, option (B) is correct.
Gate 2017-CSE
3. Match the algorithms with their time complexities:
(A) P-> (iii), Q -> (iv), R -> (i), S -> (ii)

(B) P-> (iv), Q -> (iii), R -> (i), S -> (ii)
(C) P-> (iii), Q -> (iv), R -> (ii), S -> (i)
(D) P-> (iv), Q -> (iii), R -> (ii), S -> (i)
Answer: (C)
Explanation:
 Tower of Hanoi – Ɵ(2n)
 Heap sort worst case – Ɵ(n log n)
 Binary Search – Ɵ(log n)
 Addition of two nxn matrices – Ɵ (n2)
Therefore Option C is correct
Gate 2016-CSE
4. Assume that the algorithms considered here sort the input sequences in ascending order. If
the input is already in ascending order, which of the following are TRUE ?
I. Quicksort runs in Θ(n2) time
II. Bubblesort runs in Θ(n2) time
III. Mergesort runs in Θ(n) time
IV. Insertion sort runs in Θ(n) time
(A) I and II only
(B) I and III only
(C) II and IV only
(D) I and IV only
Answer: (D)
Explanation: I. Given an array in ascending order, Recurrence relation for total number of
comparisons for quicksort will be
T(n) = T(n-1)+O(n) //partition algo will take O(n) comparisons in any case.
= O(n^2)
II. Bubble Sort runs in Θ(n^2) time

If an array is in ascending order, we could make a small modification in Bubble Sort Inner for
loop which is responsible for bubbling the kth largest element to the end in kth iteration.
Whenever there is no swap after the completion of inner for loop of bubble sort in any iteration,
we can declare that array is sorted in case of Bubble Sort taking O(n) time in Best Case.
III. Merge Sort runs in Θ(n) time
Merge Sort relies on Divide and Conquer paradigm to sort an array and there is no such worst or
best case input for merge sort. For any sequence, Time complexity will be given by following
recurrence relation
T(n) = 2T(n/2) + Θ(n) // In-Place Merge algorithm will take Θ(n) due to copying an entire array.
= Θ(nlogn)
IV. Insertion sort runs in Θ(n) time
Whenever a new element which will be greater than all the elements of the intermediate sorted
sub-array ( because given array is sorted) is added, there won’t be any swap but a single
comparison. In n-1 passes we will be having 0 swaps and n-1 comparisons.
Total time complexity = O(n) // N-1 Comparisons
For an array already sorted in ascending order,

Quicksort has a complexity Θ(n2) [Worst Case]
Bubblesort has a complexity Θ(n) [Best Case]
Mergesort has a complexity Θ(n log n) [Any Case]
Insertsort has a complexity Θ(n) [Best Case]
Gate 2015-CSE
5. Which one of the following is the recurrence equation for the worst case time complexity of
the Quicksort algorithm for sorting n(≥ 2) numbers? In the recurrence equations given in the
options below, c is a constant.
(A) T(n) = 2T (n/2) + cn
(B) T(n) = T(n – 1) + T(0) + cn
(C) T(n) = 2T (n – 2) + cn
(D) T(n) = T(n/2) + cn
Answer: (B)
Explanation: In worst case, the chosen pivot is always placed at a corner position and recursive
call is made for following.
a) forsubarray on left of pivot which is of size n-1 in worst case.
b) forsubarray on right of pivot which is of size 0 in worst case.
Gate 2015-CSE
6. Which one of the following is the tightest upper bound that represents the number of swaps
required to sort n numbers using selection sort?
(A) O(log n)
(B) O(n)
(C) O(nLogn)
(D) O(n^2)
Answer: (B)
Explanation: To sort elements in increasing order, selection sort always picks the maximum
element from remaining unsorted array and swaps it with the last element in the remaining
array. So the number of swaps, it makes in n-1 which is O(n)
Gate 2014-CSE
7. Assume that a mergesort algorithm in the worst case takes 30 seconds for an input of size 64.
Which of the following most closely approximates the maximum input size of a problem that
can be solved in 6 minutes?
(A) 256
(B) 512
(C) 1024
(D) 2048
Answer: (B)
Explanation: Time complexity of merge sort is Θ(nLogn)
c*64Log64 is 30
c*64*6 is 30
c is 5/64
For time 6 minutes
5/64*nLogn = 6*60
nLogn = 72*64 = 512 * 9
n = 512.
UNIT-IV
Binary Search Tree
Gate 2019 CSE
1. Let T be a full binary tree with 8 leaves. (A full binary tree has every level full.) Suppose two
leaves a and b of T are chosen uniformly and independently at random. The expected value
of the distance between a and b in T (i.e., the number of edges in the unique path between a
and b) is (rounded off to 2 decimal places) ___________ .
Note: This was Numerical Type question.
(A) 5.71 to 5.73
(B) 4.85 to 4.86
(C) 2.71 to 2.73
(D) 4.24 to 4.26
Answer: (D)
Explanation: Full binary tree with 8 leaf nodes,
Two leaf nodes can be selected in 8*8 = 64 ways.

Where, X is length between two nodes selected.
The expected value of the length between a and b in T,

= E[X]
= X * P[X]
= 0*(8/64) + 2*(8/64) + 4*(16/64) + 6*(32/64)
= 272/64
= 4.25
So, answer is 4.25.
Alternative way:
Sum of distances from a particular leaf to the remaining 7 leaves is 34. The sum would remain
the same for each leaf node. Therefore total sum of distance of all the leaf nodes = 34*8.
Two leaf nodes can be selected in 8*8 = 64 ways.
Therefore, the expected value of the length between a and b in T,
= (34*8) / (8*8)
= 34 / 8
= 4.25
Gate 2019 CSE
2. Which one of the following statements is NOT correct about the B+ tree data structure used
for creating an index of a relational database table?
(A) B+ Tree is a height-balanced tree
(B) Non-leaf nodes have pointers to data records
(C) Key values in each node are kept in sorted order
(D) Each leaf node has a pointer to the next leaf node
Answer: (B)
Explanation: B+ tree is height balance search tree, where key values in each node are kept in
sorted order.
All leaf nodes are at same level and connected to next leaf node.
Each non-leaf (i.e., internal) node is of the form:
<P1, K1, P2, K2, ….., Pc-1, Kc-1, Pc>
where c <= a and each Pi is a tree pointer (i.e points to another node of the tree) and, each Ki is a
key value. That means each non-leaf (i.e., internal) nodes has only block (i.e., node or tree
pointers) and keys. These internal (i.e., non-leaf) node do not contain data record pointers. So,
option (B) is not correct.
Gate 2018 CSE
3. The post order traversal of a binary tree is 8, 9, 6, 7, 4, 5, 2, 3, 1. The inorder traversal of the
same tree is 8, 6, 9, 4, 7, 2, 5, 1, 3. The height of a tree is the length of the longest path from
the root to any leaf. The height of the binary tree above is ________
A.2
B.3
C.4
D.5
Answer: (C)
Solution:
Explanation: Given, post-order – 8, 9, 6, 7, 4, 5, 2, 3, 1
and in-order – 8, 6, 9, 4, 7, 2, 5, 1, 3
Construct a binary tree from postorder and inordertraversal :
The height of the binary tree above is 4.
Gate 2018-CSE
4. The number of possible min-heaps containing each value from {1, 2, 3, 4, 5, 6, 7} exactly
once is _______.
(A) 80
(B) 8
(C) 20
(D) 210
Answer: (A)
Solution:
Explanation: Set minimum element as root (i.e 1), now 6 are remaining and left subtree will have
3 elements, each left subtree combination can be permuted in 2! ways.
Total ways to design min-heap with 7-elements = 6C_3 *2! * 2! = 20*2*2 = 80
Alternative approach – Total number of min or max heap tree with 1 to N elements are using
recurrence relation:
T(N) =(N-1)Ck * T(k) * T(N-k-1), where k = number of nodes on left subtree
T(1) = 1
T(2) = 1
T(3) = 2
T(4) = 3C2 * T(2) * T(1) = 3
T(5) = 4C3 * T(3) * T(1) = 8
T(6) = 5C3 * T(3) * T(2) = 20
T(7) = 5C3 * T(3) * T(3) = 80
So, answer is 80.
Gate 2017-CSE
5. Let T be a binary search tree with 15 nodes. The minimum and maximum possible heights of
T are:
Note: The height of a tree with a single node is 0.
(A) 4 and 15 respectively
(B) 3 and 14 respectively
(C) 4 and 14 respectively
(D) 3 and 15 respectively
Answer: (B)
Explanation:
 The minimum height of a binary search tree will be when tree is full complete tree:
Now, let h be the height of the binary tree, then,

2^{0}+2^{1}+2^{2}+2^{3}+…+2^{h}=2^{h+1}-1 <= n
So, Min height of a binary search tree = log2(n+1) – 1 = log2(15+1) – 1 = 4 – 1 = 3
 The maximum height of a binary search tree will be when the tree is fully skewed: (like
below)
Max height of the binary search tree = n-1 = 15 – 1 = 14, where the tree is Skewed tree
Gate 2017-CSE
6. Let T be a tree with 10 vertices. The sum of the degrees of all the vertices in T is _____.
(A) 18
(B) 19
(C) 20
(D) 21
Answer: (A)
Explanation: Given, v= Total vertices = 10

e = v – 1 =9
Degree = 2 * e = 18
Therefore, option A is correct
Gate 2016-CSE
7. B+ Trees are considered BALANCED because
(A) the lengths of the paths from the root to all leaf nodes are all equal.
(B) the lengths of the paths from the root to all leaf nodes differ from each other by at most 1.
(C) the number of children of any two non-leaf sibling nodes differ by at most 1.
(D) the number of records in any two leaf nodes differ by at most 1.
Answer: (A)
Explanation: In both B Tree and B+ trees, depth (length of root to leaf paths) of all leaf nodes is
same. This is made sure by the insertion and deletion operations.
In these trees, we do insertions in a way that if we have increase height of tree after insertion, we
increase height from root. This is different from BST where height increases from leaf nodes.
Similarly, if we have to decrease height after deletion, we move the root one level down. This is
also different from BST which shrinks from bottom.
The above ways of insertion and deletion make sure that depth of every leaf node is same.
Gate 2016-CSE
8. A complete binary min-heap is made by including each integer in [1, 1023] exactly once. The
depth of a node in the heap is the length of the path from the root of the heap to that node.
Thus, the root is at depth 0. The maximum depth at which integer 9 can appear is
_____________
(A) 6
(B) 7
(C) 8
(D) 9
Answer: (C)
Explanation: here node with integer 1 has to be at root only. Now for maximum depth of the
tree the following arrangement can be taken. Take root as level 1.
make node 2 at level 2 as a child node of node 1.
make node 3 at level 3 as the child node of node 2.
..
.. and so on for nodes 4,5,6,7
..
Putting other nodes properly, this arrangement of the the complete binary tree will follow the
property of min heap.
So total levels are 9.node 9 is at level 9 and depth of node 9 is 8 from the root.
Gate 2016-CSE
9. Consider the following New-order strategy for traversing a binary tree:
Visit the root;
Visit the right subtree using New-order
Visit the left subtree using New-order
The New-order traversal of the expression tree corresponding to the reverse polish expression 3 4
* 5 – 2 ˆ 6 7 * 1 + – is given by:
(A) + – 1 6 7 * 2 ˆ 5 – 3 4 *
(B) – + 1 * 6 7 ˆ 2 – 5 * 3 4
(C) – + 1 * 7 6 ˆ 2 – 5 * 4 3
(D) 1 7 6 * + 2 5 4 3 * – ˆ –
Answer: (C)
Explanation:
Reverse Polish expression is derived through Post-Order i.e.
1) Visit Left Node
2) Visit Right Node (L R N)
3) Visit Root Node
— Acc. to Ques. New Order algorithm is :
1) Visit Root Node
2) Visit Right Node (N R L)
3) Visit Left Node
ie. New Order Expression will be a total reverse of the Post-Order algorithm
Post-Order Expression : 34*5–2ˆ67*1+–
Hence , New Order Expression : – + 1 * 7 6 ^ 2 – 5 * 4 3
Gate 2016-CSE
10. The number of ways in which the numbers 1, 2, 3, 4, 5, 6, 7 can be inserted in an empty
binary search tree, such that the resulting tree has height 6, is _____________
Note: The height of a tree with a single node is 0.
(A) 2
(B) 4
(C) 64
(D) 32
Answer: (C)
Explanation: To get height 6, we need to put either 1 or 7 at root.

So count can be written as T(n) = 2*T(n-1) with T(1) = 1
7
/
[1..6]
1
\
[2..7]
Therefore count is 26 = 64
Another Explanation:
Consider these cases,
1234567
1234576
1765432
1765423
7654321
7654312
7123456
7123465
For height 6, we have 2 choices. Either we select the root as 1 or 7.
Suppose we select 7.
Now, we have 6 nodes and remaining height = 5.
So, now we have 2 ways to select root for this sub-tree also.
Now, we keep on repeating the same procedure till remaining height = 1
For this last case also, we have 2 ways.
Therefore, total number of ways = 26= 64
Gate 2015-CSE
Which of the following is/are correct inorder traversal sequence(s) of binary search tree(s)?
1. 3, 5, 7, 8, 15, 19, 25
2. 5, 8, 9, 12, 10, 15, 25
3. 2, 7, 10, 8, 14, 16, 20
4. 4, 6, 7, 9, 18, 20, 25
(A) 1 and 4 only
(B) 2 and 3 only
(C) 2 and 4 only
(D) 2 only
Answer: (A)
Explanation: An Inorder traversal of a Binary Search Tree must be in increasing order.
Gate 2015-CSE
11. What are the worst-case complexities of insertion and deletion of a key in a binary search
tree?
(A) Θ(logn) for both insertion and deletion
(B) Θ(n) for both insertion and deletion
(C) Θ(n) for insertion and Θ(logn) for deletion
(D) Θ(logn) for insertion and Θ(n) for deletion
Answer: (B)
Explanation: The time taken by search, insert and delete on a BST is always proportional to
height of BST. Height may become O(n) in worst case.
Gate 2015-CSE
12. The height of a tree is the length of the longest root-to-leaf path in it. The maximum and
minimum number of nodes in a binary tree of height 5 are
(A) 63 and 6, respectively
(B) 64 and 5, respectively
(C) 32 and 6, respectively
(D) 31 and 5, respectively
Answer: (A)
Explanation:
Number of nodes is maximum for a perfect binary tree.
A perfect binary tree of height h has 2h+1 - 1 nodes
Number of nodes is minimum for a skewed binary tree.

A perfect binary tree of height h has h+1 nodes.
Gate 2015-CSE
13. Consider a max heap, represented by the array: 40, 30, 20, 10, 15, 16, 17, 8, 4. Now consider
that a value 35 is inserted into this heap. After insertion, the new heap is
(A) 40, 30, 20, 10, 15, 16, 17, 8, 4, 35
(B) 40, 35, 20, 10, 30, 16, 17, 8, 4, 15
(C) 40, 30, 20, 10, 35, 16, 17, 8, 4, 15
(D) 40, 35, 20, 10, 15, 16, 17, 8, 4, 30
Answer: (B)
Explanation: The array 40, 30, 20, 10, 15, 16, 17, 8, 4 represents following heap
40
/ \
30 20
/\ /\
10 15 16 17
/\
8 4
After insertion of 35, we get
40
/ \
30 20
/\ /\
10 15 16 17
/\ /
8 4 35
After swapping 35 with 15 and swapping 35 again
with 30, we get
40
/ \
35 20
/\ /\
10 30 16 17
/\ /
8 4 15
Gate 2015-CSE
14. A binary tree T has 20 leaves. The number of nodes in T having two children is
(A) 18
(B) 19
(C) 17
(D) Any number between 10 and 20
Answer: (B)
Explanation:
Sum of all degrees = 2 * |E|.
Here considering tree as a k-arytree :
Sum of degrees of leaves + Sum of degrees for Internal Node except root + Root's degree = 2 *
(No. of nodes - 1).
Putting values of above terms,
L + (I-1)*(k+1) + k = 2 * (L + I - 1)
L + k*I - k + I -1 + k = 2*L + 2I - 2
L + K*I + I - 1 = 2*L + 2*I - 2
K*I + 1 - I = L
(K-1)*I + 1 = L
Given k = 2, L=20
==> (2-1)*I + 1 = 20
==> I = 19
==> T has 19 internal nodes which are having two children.
Gate 2015-CSE
15. With reference to the B+ tree index of order 1 shown below, the minimum number of nodes
(including the root node) that must be fetched in order to satisfy the following query: ―Get all
records with a search key greater than or equal to 7 and less than 15‖ is ________
(A) 4
(B) 5
(C) 6
(D) 7
Answer: (B)
Explanation:
We can get all values in range from 7 to 59 by accessing 5 nodes.
1) First search 7 in a leaf node.
2) Once 7 is found, linearly traverse till 15 is found.
See following diagram

Gate 2014-CSE
16. While inserting the elements 71, 65, 84, 69, 67, 83 in an empty binary search tree (BST) in
the sequence shown, the element in the lowest level is
(A) 65
(B) 67
(C) 69
(D) 83
Answer: (B)
Explanation: Here is The Insertion Algorithm For a Binary Search Tree :

Insert(Root,key)
{
if(Root is NULL)
Create a Node with value as key and return
Else if(Root.key>= key)
Insert(Root.left,key)
Else
Insert(Root.right,key)
}
Creating the BST one by one using the above algorithm in the below given image :
Gate 2014-CSE
17. Consider the following array of elements. 〈89, 19, 50, 17, 12, 15, 2, 5, 7, 11, 6, 9, 100〉. The
minimum number of interchanges needed to convert it into a max-heap is
(A) 4
(B) 5
(C) 2
(D) 3
Answer: (D)
Explanation: 〈89, 19, 50, 17, 12, 15, 2, 5, 7, 11, 6, 9, 100〉
89
/ \
19 50
/ \ / \
17 12 15 2
/ \ /\ / \
5 7 11 6 9 100
Minimum number of swaps required to convert above tree

to Max heap is 3. Below are 3 swap operations.
Swap 100 with 15
Swap 100 with 50
Swap 100 with 89
100
/ \
19 89
/ \ / \
17 12 50 5
/ \ /\ / \
7 11 6 9 2 15
Gate 2014-CSE
18. Consider a binary tree T that has 200 leaf nodes. Then, the number of nodes in T that have
exactly two children are _________.
(A) 199
(B) 200
(C) Any number between 0 and 199
(D) Any number between 100 and 200
Answer: (A)
Gate 2014-CSE
19. Consider B+ tree in which the search key is 12 bytes long, block size is 1024 bytes, record
pointer is 10 bytes long and block pointer is 8 bytes long. The maximum number of keys that
can be accommodated in each non-leaf node of the tree is
(A) 49
(B) 50
(C) 51
(D) 52
Answer: (B)
Explanation:
Let m be the order of B+ tree
m(8)+(m-1)12 <= 1024

[Note that record pointer is not needed in non-leaf nodes]
m <= 51
Since maximum order is 51, maximum number of keys is 50.
Gate 2014-CSE
20. Consider a rooted Binary tree represented using pointers. The best upper bound on the time
required to determine the number of subtrees having having exactly 4 nodes O(naLogn b).
Then the value of a + 10b is ________
(A) 1
(B) 11
(C) 12
(D) 21
Answer: (A)
Explanation: We can find the subtree with 4 nodes in O(n) time. Following can be a simple
approach.
1) Traverse the tree in bottom up manner and find size of subtree rooted with current node
2) If size becomes 4, then print the current node.
Gate 2013-CSE
21. Which one of the following is the tightest upper bound that represents the time complexity of
inserting an object into a binary search tree of n nodes?
(A) O(1)
(B) O(Logn)
(C) O(n)
(D) O(nLogn)
Answer: (C)
Explanation: To insert an element, we need to search for its place first. The search operation
may take O(n) for a skewed tree like following.
To insert 50, we will have to traverse all nodes.
10
\
20
\
30
\
40
UNIT-V
Gate 2015: CSE

1. Which one of the following hash functions on integers will distribute keys most uniformly
over 10 buckets numbered 0 to 9 for i ranging from 0 to 2020?
(A) h(i) =i2 mod 10
(B) h(i) =i3 mod 10
(C) h(i) = (11 ∗ i2) mod 10
(D) h(i) = (12 ∗ i) mod 10
Answer: (B)
Explanation: Since mod 10 is used, the last digit matters.If you do cube all numbers from 0
to 9, you get following
Number Cube Last Digit in Cube
0 0 0
1 1 1
2 8 8
3 27 7
4 64 4
5 125 5
6 216 6
7 343 3
8 512 2
9 729 9
Therefore all numbers from 0 to 2020 are equally divided in 10 buckets. If we make a table for
square, we don‟t get equal distribution. In the following table. 1, 4, 6 and 9 are repeated, so
these buckets would have more entries and buckets 2, 3, 7 and 8 would be empty.
Number Square Last Digit in Cube
0 0 0
1 1 1
2 4 4
3 9 9
4 16 6
5 25 5
6 36 6
7 49 9
8 64 4
9 81 1
Alternative approach –
Using concept of power of cycle:
(a) (0,1,4,9,6,5,6,9,4,1,0) repeated
(b) (0,1,8,7,4,5,6,3,2,9) repeated
(c) (0,1,4,9,6,5,6,9,4,1,0) repeated
(d) (0,2,4,6,8) repeated
So, only h(i) =i3 mod 10 covers all the digits from 0 to 9.
Option (B) is correct.
Gate 2014: CSE

2. Given a hash table T with 25 slots that stores 2000 elements, the load factor α for T is
__________
(A) 80
(B) 0.0125
(C) 8000
(D) 1.25
Answer: (A)
Explanation: load factor = (no. of elements) / (no. of table slots) = 2000/25 = 80
GRAPH
Gate 2019-CSE
1. Consider the following undirected graph G:
Choose a value for x that will maximize the number of minimum weight spanning trees
(MWSTs) of G. The number of MWSTs of G for this value of x is _________ .
(A) 4
(B) 5
(C) 2
(D) 3
Option (A) is correct.
Explanation: To maximize the number of minimum weight spanning trees of G, the value of x
will be 5 because it will have two more choices for corner vertex which will maximize maximum
number of MSTs.
Now, according to kruskal algorithm for MST:
1. Edges with weights 1 and 3 will be selected first,
2. Now bottom edge with weight 4 will not be selected as will cause cycle on MST,
3. both corner vertices have two-two choices to select the vertices, so these corner edges
with weights 4 and 5 will resultant 2*2 = 4 MSTs.
Therefore, total number of MSTs are 2*2 = 4, which is answer.
Gate 2019-CSE
2. Consider the weights and values of items listed below. Note that there is only one unit of
each item.
The task is to pick a subset of these items such that their total weight is no more than 11
Kgs and their total value is maximized. Moreover, no item may be split. The total value of
items picked by an optimal algorithm is denoted by V opt. A greedy algorithm sorts the items
by their value-to-weight ratios in descending order and packs them greedily, starting from
the first item in the ordered list. The total value of items picked by the greedy algorithm is
denoted by Vgreedy.
The value of Vopt − Vgreedy is ______ .
Note –This was Numerical Type question.

(A) 16
(B) 8
(C) 44
(D) 60
Answer: (A)
Explanation:
First we will pick item_4 (Value weight ratio is highest). Second highest is item_1, but cannot be
picked because of its weight. Now item_3 shall be picked. item_2 cannot be included because
of its weight.
Therefore, overall profit by Vgreedy = 20+24 = 44
Hence, Vopt – Vgreedy = 60-44 = 16
So, answer is 16.
Gate 2019-CSE
3. Let G be a simple undirected graph. Let T D be a depth first search tree of G. Let TB be a
breadth first search tree of G. Consider the following statements.
(I) No edge of G is a cross edge with respect to T D. (A cross edge in G is between two nodes
neither of which is an ancestor of the other in T D).
(II) For every edge (u, v) of G, if u is at depth i and v is at depth j in T B, then ∣i − j∣ = 1.
Which of the statements above must necessarily be true?
(A) I only
(B) II only
(C) Both I and II
(D) Neither I nor II
Answer: (A)
Explanation: There are four types of edges can yield in DFS. These are tree, forward, back,
and cross edges. In undirected connected graph, forward and back egdes are the same thing. A
cross edge in a graph is an edge that goes from a vertex v to another vertex u such that u is
neither an ancestor nor descendant of v. Therefore, cross edge is not possible in undirected
graph.
So, statement (I) is correct.
For statement (II) take counterexample of complete graph of three vertices, i.e., K3 with XYZ,
where X is source and Y and Z are in same level. Also,there is an edge between vertices Y and
Z, i.e., |i-j| = 0 ≠ 1 in BFS. So, statement became false.
Gate 2017-CSE
4. Consider the following table
Match the algorithm to design paradigms they are based on:

(A) P-(ii), Q-(iii), R-(i)
(B) P-(iii), Q-(i), R-(ii)
(C) P-(ii), Q-(i), R-(iii)
(D) P-(i), Q-(ii), R-(iii)
Answer: (C)
Explanation:
 Kruskal‟s is a greedy technique of Minimum Spanning Tree Algorithm to find an edge of
the least possible weight that connects any two trees in the forest.
 QuickSort is a Divide and Conquer algorithm. It picks an element as pivot and partitions
the given array around the picked pivot.
 Floyd Warshall Algorithm is for solving the All Pairs Shortest Path problem using
Dynamic Programming. The problem is to find shortest distances between every pair of
vertices in a given edge weighted directed Graph.
Gate 2017-CSE
5. Let G = (V, E) be any connected undirected edge-weighted graph. The weights of the edges
in E are positive any distinct. Consider the following statements:
I. Minimum Spanning Tree of G is always unique.
II. Shortest path between any two vertices of G is always unique.
Which of the above statements is/are necessarily true?
(A) I only
(B) II only
(C) both I and II
(D) neither I and II
Answer: (A)
Explanation: I. Minimum Spanning Tree of G is always unique – MST will wlways be distinct if
the edges are unique so Correct
II. Shortest path between any two vertices of G is always unique – Shortest path between any
two vertices can be same so incorrect
Alternate solution:
We know that minimum spanning tree of a graph is always unique if all the weight are distinct,
so statement 1 is correct.
Now statement 2 , this might not be true in all cases. Consider the graph.
There are two shortest paths from a to b (one is direct and other via node c) So statement 2 is
false.
Gate 2017-CSE
6. Breath First Search(BFS) has been implemented using queue data structure.
Which one of the following is a possible order of visiting the nodes in the graph above.
(A) MNOPQR
(B) NQMPOR
(C) QMNROP
(D) POQNMR
Answer: (D)
Explanation: In BFS, we print a starting node, then its adjacent, then adjacent of adjacent, and
so on..
Option A : MNOPQR Wrong
We cannot visit "O" before "R" as we start from "M".
Note that "O" is adjacent of adjacent for "M" and
"R" is adjacent of "M".
Option B : NQMPOR Wrong

We cannot visit "P" before "O" as we start from "N".
Note that "P" is adjacent of adjacent for "N" and
"O" is adjacent.
Option C : QMNROP Wrong

We cannot visit "R" before "O" as we start from "Q".
Note that "R" is adjacent of adjacent for "Q" and
"O" is adjacent of "Q"
Option D : POQNMR Right

We visit "P", then its adjacent "O", "Q" and "N"
Finally we visit adjacent of adjacent "M" and "R"
Gate 2016-CSE
7. Consider the following directed graph.
The number of different topological orderings of the vertices of the graph is
Note : This question was asked as Numerical Answer Type.

(A) 1
(B) 2
(C) 4
(D) 6
Answer: (D)
Explanation: Following are different 6 Topological Sortings

a-b-c-d-e-f
a-d-e-b-c-f
a-b-d-c-e-f
a-d-b-c-e-f
a-b-d-e-c-f
a-d-b-e-c-f
Gate 2016-CSE
8. The worst case running times of Insertion sort, Merge sort and Quick sort, respectively, are:
(A) Θ(n log n), Θ(n log n) and Θ(n 2)
(B) Θ(n2), Θ(n2) and Θ(n Log n)
(C) Θ(n2), Θ(n log n) and Θ(n log n)
(D) Θ(n2), Θ(n log n) and Θ(n2)
Answer: (D)
Explanation:
 Insertion Sort takes Θ(n2) in worst case as we need to run two loops. The outer loop is
needed to one by one pick an element to be inserted at right position. Inner loop is used
for two things, to find position of the element to be inserted and moving all sorted greater
elements one position ahead. Therefore the worst case recursive formula is T(n) = T(n-1)
+ Θ(n).
 Merge Sort takes Θ(n Log n) time in all cases. We always divide array in two halves, sort
the two halves and merge them. The recursive formula is T(n) = 2T(n/2) + Θ(n).
 QuickSort takes Θ(n2) in worst case. In QuickSort, we take an element as pivot and
partition the array around it. In worst case, the picked element is always a corner element
and recursive formula becomes T(n) = T(n-1) + Θ(n). An example scenario when worst
case happens is, arrays is sorted and our code always picks a corner element as pivot.
Gate 2016-CSE
9. Let G be a weighted connected undirected graph with distinct positive edge weights. If every
edge weight is increased by the same value, then which of the following statements is/are
TRUE?
P: Minimum spanning tree of G does not change

Q: Shortest path between any pair of vertices does not change
(A) P only
(B) Q only
(C) Neither P nor Q
(D) Both P and Q
Answer: (A)
Explanation: The shortest path may change. The reason is, there may be different number of
edges in different paths from s to t. For example, let shortest path be of weight 15 and has 5
edges. Let there be another path with 2 edges and total weight 25. The weight of the shortest
path is increased by 5*10 and becomes 15 + 50. Weight of the other path is increased by 2*10
and becomes 25 + 20. So the shortest path changes to the other path with weight as 45.
The Minimum Spanning Tree doesn‟t change. Remember the Kruskal‟s algorithm where we sort
the edges first. IF we increase all weights, then order of edges won‟t change.
Gate 2016-CSE
10. An operator delete(i) for a binary heap data structure is to be designed to delete the item in
the i-th node. Assume that the heap is implemented in an array and i refers to the i-th index
of the array. If the heap tree has depth d (number of edges on the path from the root to the
farthest leaf), then what is the time complexity to re-fix the heap efficiently after the removal
of the element?
(A) O(1)
(B) O(d) but not O(1)
(C) O(2d) but not O(d)
(D) O(d2d) but not O(2d)
Answer: (B)
Explanation:
For this question, we have to slightly tweak the delete_min() operation of the heap data
structure to implement the delete(i) operation. The idea is to empty the spot in the array at the
index i (the position at which element is to be deleted) and replace it with the last leaf in the
heap (remember heap is implemented as complete binary tree so you know the location of the
last leaf), decrement the heap size and now starting from the current position i (position that
held the item we deleted), shift it up in case newly replaced item is greater than the parent of old
item (considering max-heap). If it‟s not greater than the parent, then percolate it down by
comparing with the child‟s value. The newly added item can percolate up/down a maximum of d
times which is the depth of the heap data structure.
Thus we can say that complexity of delete(i) would be O(d) but not O(1).
Gate 2016-CSE
11. Consider the weighted undirected graph with 4 vertices, where the weight of edge {i, j} g is
given by the entry
W ij in the matrix W
The largest possible integer value of x, for which at least one shortest path between some
pair of vertices will contain the edge with weight x is ________
Note : This question was asked as Numerical Answer Type.

(A) 8
(B) 12
(C) 10
(D) 11
Answer: (B)
Explanation: Let vertices be 0, 1, 2 and 3.

x directly connects 2 to 3. The shortest path (excluding x) from 2 to 3 is of weight 12 (2-1-0-3).
Gate 2016-CSE
12. Let G be a complete undirected graph on 4 vertices, having 6 edges with weights being 1, 2,
3, 4, 5, and 6. The maximum possible weight that a minimum weight spanning tree of G can
have is.
[This Question was originally a Fill-in-the-Blanks question]
(A) 6
(B) 7
(C) 8
(D) 9
Answer: (B)
Explanation: One graph that has maximum possible weight of spanning tree
Gate 2016-CSE
13. G = (V, E) is an undirected simple graph in which each edge has a distinct weight, and e is a
particular edge of G. Which of the following statements about the minimum spanning trees
(MSTs) of G is/are TRUE
I. If e is the lightest edge of some cycle in G, then every MST of G includes e
II. If e is the heaviest edge of some cycle in G, then every MST of G excludes e
(A) I only
(B) II only
(C) both I and II
(D) neither I nor II
Answer: (B)
Explanation:
I is NOT true.
Let G=(V, E) be a rectangular graph where V = {a, b, c, d} and E = {ab, bc, cd, da, ac}.
Let the edges have weights: ab = 1, bc = 2, cd = 4, da = 5, ac = 3. Then, clearly, ac is the
lightest edge of the cycle cdac, however, the MST abcd with cost 7 (= ab + bc + cd) does not
include it.
Let the edges have weights: ab = 6, bc – 7, cd = 4, da = 5, ac = 3. Then, again, ac is the lightest
edge of the cycle cdac, and, the MST bacd with cost 13 (= ba + ac + cd) includes it.
So, the MSTs of G may or may not include the lightest edge.
II is true
Let the heavies edge be e. Suppose the minimum spanning tree which contains e. If we add
one more edge to the spanning tree we will create a cycle. Suppose we add edge e‟ to the
spanning tree which generated cycle C. We can reduce the cost of the minimum spanning tree if
we choose an edge other than e from C for removal which implies that e must not be in
minimum spanning tree and we get a contradiction.
Gate: 2016-CSE
14. Breadth First Search (BFS) is started on a binary tree beginning from the root vertex. There
is a vertex t at a distance four from the root. If t is the n-th vertex in this BFS traversal, then
the maximum possible value of n is ________
(A) 15
(B) 16
(C) 31
(D) 32
Answer: (C)
Explanation: It would be node number 31 for given distance 4.

For example if we consider at distance 2, below highlighted node G can be the farthest node at
position 7.
A
/ \
B C
/\ /\
D E F G
Alternative Solution :
t is the n-th vertex in this BFS traversal at distance four from the root. So height of tree is 4.
Max number of nodes = 2^{h+1} − 1 = 2^{5} − 1 = 31
At distance four, last node is 31. option (C)
Gate: 2016-CSE
15. In an adjacency list representation of an undirected simple graph G = (V, E), each edge (u,
v) has two adjacency list entries: [v] in the adjacency list of u, and [u] in the adjacency list of
v. These are called twins of each other. A twin pointer is a pointer from an adjacency list
entry to its twin. If |E| = m and |V | = n, and the memory size is not a constraint, what is the
time complexity of the most efficient algorithm to set the twin pointer in each entry in each
adjacency list?
(A) Θ(n2)
(B) Θ(m+n)
(C) Θ(m2)
(D) Θ(n4)
Answer: (B)
Explanation: First you need to find twins of each node. You can do this using level order
traversal (i.e., BFS) once. Time complexity of BFS is Θ(m +n).
And you have to use linked list for representation which is extra space (but memory size is
not a constraint here).
Final, time complexity is Θ(m + n) to set twin pointer.
Option (B) is correct.
Gate 2015-CSE
16. Given below are some algorithms, and some algorithm design paradigms.
List-I
A. Dijkstra‟s Shortest Path
B. Floyd-Warshall algorithm to compute all pairs shortest path
C. Binary search on a sorted array
D. Backtracking search on a graph
List-II
1. Divide and Conquer
2. Dynamic Programming
3. Greedy design
4. Depth-first search
5. Breadth-first search
Match the above algorithms on the left to the corresponding design paradigm they follow
Codes:
ABCD
(a) 1 3 1 5
(b) 3 3 1 5
(c) 3 2 1 4
(d) 3 2 1 5
(A) a
(B) b
(C) c
(D) d
Answer: (C)
Explanation:
Dijkstra‟s Shortest Path is a Greedy Algorithm.
Floyd-Warshallalgorithm is Dynamic Programming.
Binary search is a Divide and Conquer.
Backtracking is Depth-first search
Gate 2015-CSE
17. Let G = (V, E) be a simple undirected graph, and s be a particular vertex in it called the
source. For x ∈ V, let d(x) denote the shortest distance in G from s to x. A breadth first
search (BFS) is performed starting at s. Let T be the resultant BFS tree. If (u, v) is an edge
of G that is not in T, then which one of the following CANNOT be the value of d(u) – d(v)?
(A) -1
(B) 0
(C) 1
(D) 2
Answer: (D)
Explanation: Note that the given graph is undirected, so an edge (u, v) also means (v, u) is
also an edge.
Since a shorter path can always be obtained by using edge (u, v) or (v, u), the difference
between d(u) and d(v) can not be more than 1.
Gate 2015-CSE
18. The graph shown below 8 edges with distinct integer edge weights. The minimum spanning
tree (MST) is of weight 36 and contains the edges: {(A, C), (B, C), (B, E), (E, F), (D, F)}. The
edge weights of only those edges which are in the MST are given in the figure shown below.
The minimum possible sum of weights of all 8 edges of this graph is ______________.
(A) 66
(B) 69
(C) 68
(D) 70
Answer: (B)
Explanation: In every cycle, the weight of an edge that is not part of MST must by greater than
or equal to weights of other edges which are part of MST.
Since all edge weights are distinct, the weight must be greater.
So the minimum possible weight of ED is 7, minimum possible weight of CD is 16 and minimum
possible weight of AB is 10.
Therefore minimum possible sum of weights is 69.
Gate 2014-CSE
19. The number of distinct minimum spanning trees for the weighted graph below is ____
(A) 4
(B) 5
(C) 6
(D) 7
Answer: (C)
Explanation: Below diagram shows a minimum spanning tree. Highlighted (in green) are
the edges picked to make the MST.
In the right side of MST, we could either pick edge „a‟ or „b‟. In the left side, we could either pick
„c‟ or „d‟ or „e‟ in MST.
There are 2 options for one edge to be picked and 3 options for another edge to be picked.
Therefore, total 2*3 possible MSTs.
Gate 2014-CSE
20. Consider the tree arcs of a BFS traversal from a source node W in an unweighted,
connected, undirected graph. The tree T formed by the tree arcs is a data structure for
computing.
(A) the shortest path between every pair of vertices.
(B) the shortest path from W to every vertex in the graph.
(C) the shortest paths from W to only those nodes that are leaves of T.
(D) the longest path in the graph
Answer: (B)
Explanation: BFS always produces shortest path from source to all other vertices in an
unweighted graph.
Question : 2014-CSE
21. Let G be connected undirected graph of 100 vertices and 300 edges. The weight of a
minimum spanning tree of G is 500. When the weight of each edge of G is increased by five,
the weight of a minimum spanning tree becomes ________.
(A) 1000
(B) 995
(C) 2000
(D) 1995
Answer: (B)
Explanation: Since there are 100 vertices, there must be 99 edges in Minimum Spanning
Tree (MST).
When weight of every edge is increased by 5, the increment in weight of MST is = 99 * 5 = 495
So new weight of MST is 500 + 495 which is 995
Gate 2014-CSE
22. Let G=(V,E) be a directed graph where V is the set of vertices and E the set of edges. Then
which one of the following graphs has the same strongly connected components as G ?
(A) A
(B) B
(C) C
(D) D
Answer: (B)
Explanation: If we reverse directions of all arcs in a graph, the new graph has same set of
strongly connected components as the original graph.
Gate 2014-CSE
23. Let G be a graph with n vertices and m edges. What is the tightest upper bound on the
running time on Depth First Search of G? Assume that the graph is represented using
adjacency matrix.
(A) O(n)
(B) O(m+n)
(C) O(n2)
(D) O(mn)
Answer: (C)
Explanation: Depth First Search of a graph takes O(m+n) time when the graph is
represented using adjacency list.
In adjacency matrix representation, graph is represented as an “n x n” matrix. To do DFS, for
every vertex, we traverse the row corresponding to that vertex to find all adjacent vertices (In
adjacency list representation we traverse only the adjacent vertices of the vertex). Therefore
time complexity becomes O(n2)
Question 1 : 2014-CSE
24. Consider the directed graph given below. Which one of the following is TRUE?
(A) The graph doesn‟t have any topological ordering

(B) Both PQRS and SRPQ are topological ordering
(C) Both PSRQ and SPRQ are topological ordering
(D) PSRQ is the only topological ordering
Answer: (C)
Explanation: The graph doesn‟t contain any cycle, so there exist topological ordering.
P and S must appear before R and Q because there are edges from P to R and Q, and from S
to R and Q.
Content beyond Syllabus
Advanced Data Structure - Dictionary
A dictionary is a general-purpose data structure for storing a group of objects. A dictionary has a
set of keys and each key has a single associated value. When presented with a key, the
dictionary will return the associated value.
For example, the results of a classroom test could be represented as a dictionary with pupil's
names as keys and their scores as the values:
results = {'Detra' : 17,

'Nova' : 84,
'Charley' : 22,
'Hwa' : 75,
'Roxann' : 92,
'Elsa' : 29}
Instead of using the numerical index of the data, we can use the dictionary names to return
values:
>>> results['Nova']
84
>>> results['Elsa']
29
A dictionary is also called a hash, a map, a hashmap in different programming languages (and
an Object in JavaScript). They're all the same thing: a key-value store.
The concept of a key-value store is widely used in various computing systems, such as caches
and high-performance databases.
Typically, the keys in a dictionary must be simple types (such as integers or strings) while the
values can be of any type. Different languages enforce different type restrictions on keys and
values in a dictionary. Dictionaries are often implemented as hash tables.
Keys in a dictionary must be unique; an attempt to create a duplicate key will typically overwrite
the existing value for that key.
Note that there is a difference (which may be important) between a key not existing in a
dictionary, and the key existing but with its corresponding value being null.
DIFFERENCES FROM SIMILAR DATA STRUCTURES

Arrays
arrays and dictionaries both store collections of data, but differ by how they are
accessed. Items in an array are accessed by position (often a number) and hence have
an order. Items in a dictionary are accessed by key and are unordered.
Sets
Sets are groups of items, unordered with duplicates removed. The keys of a dictionary
form a set, but each key has an associated value; these values could be duplicated
within a dictionary.
MAIN OPERATIONS ON DICTIONARIES

Dictionaries typically support several operations:
 Retrieve a value (depending on language, attempting to retrieve a missing key may

give a default value or throw an exception)
 Insert or update a value (typically, if the key does not exist in the dictionary, the key-
value pair is inserted; if the key already exists, its corresponding value is overwritten
with the new one)
 Remove a key-value pair
 Test for existence of a key
Most programming languages with dictionaries will also support iteration over the keys
or values in a dictionary. Note that items in a dictionary are unordered, so loops over
dictionaries will return items in an arbitrary order.
Given a dictionary results containing the class result above, these are examples of
these operations:
Operation Python 3
Retreive results['Nova']
Insert results['Nova'] = 99
Delete del results['Nova']
Key existence 'Nova' in results
for pupil in results:

Iterate over dictionary
print(pupil, results[pupil])
Implementation of Stack Data structure using Java:
import java.util.*;
class arrayStack
{
protected int arr[];
protected int top, size, len;
/* Constructor for arrayStack */
public arrayStack(int n)
{
size = n;
len = 0;
arr = new int[size];
top = -1;
}
/* Function to check if stack is empty */
public boolean isEmpty()
{
return top == -1;
}
/* Function to check if stack is full */
public boolean isFull()
{
return top == size -1 ;
}
/* Function to get the size of the stack */
public int getSize()
{
return len ;
}
/* Function to check the top element of the stack */
public int peek()
{
if( isEmpty( ) )
throw new NoSuchElementException("Underflow Exception");
return arr[top];
}
/* Function to add an element to the stack */
public void push(int i)
{
if(top + 1 >= size)
throw new IndexOutOfBoundsException("Overflow Exception");
if(top + 1 < size )
arr[++top] = i;
len++ ;
}
/* Function to delete an element from the stack */
public int pop()
{
if( isEmpty() )
throw new NoSuchElementException("Underflow Exception");
len-- ;
return arr[top--];
}
/* Function to display the status of the stack */
public void display()
{
System.out.print("\nStack = ");
if (len == 0)
{
System.out.print("Empty\n");
return ;
}
for (int i = top; i >= 0; i--)
System.out.print(arr[i]+" ");
System.out.println();
}
}
/* Class StackImplement */
public class StackImplement
{
public static void main(String[] args)
{
Scanner scan = new Scanner(System.in);
System.out.println("Stack Test\n");
System.out.println("Enter Size of Integer Stack ");
int n = scan.nextInt();
/* Creating object of class arrayStack */
arrayStack stk = new arrayStack(n);
/* Perform Stack Operations */
char ch;
do{
System.out.println("\nStack Operations");
System.out.println("1. push");
System.out.println("2. pop");
System.out.println("3. peek");
System.out.println("4. check empty");
System.out.println("5. check full");
System.out.println("6. size");
int choice = scan.nextInt();
switch (choice)
{
case 1 :
System.out.println("Enter integer element to push");
try
{
stk.push( scan.nextInt() );
}
catch (Exception e)
{
System.out.println("Error : " + e.getMessage());
}
break;
case 2 :
try
{
System.out.println("Popped Element = " + stk.pop());
}
catch (Exception e)
{
}
break;
case 3 :
try
{
System.out.println("Peek Element = " + stk.peek());
}
catch (Exception e)
{
}
break;
case 4 :
System.out.println("Empty status = " + stk.isEmpty());
break;
case 5 :
System.out.println("Full status = " + stk.isFull());
break;
case 6 :
System.out.println("Size = " + stk.getSize());
break;
default :
System.out.println("Wrong Entry \n ");
break;
}
/* display stack */
stk.display();
System.out.println("\nDo you want to continue (Type y or n) \n");
ch = scan.next().charAt(0);
} while (ch == 'Y'|| ch == 'y');

}
}

DS Notes

Uploaded by

Copyright:

Available Formats

DS Notes

Uploaded by

Document Information

Original Description:

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

DS Notes

Uploaded by

Copyright:

Available Formats

IT-T33 DATA STRUCTURES

Unit-II (10 Periods)

Unit-III (12 Periods)

Unit-IV (10 Periods)

Unit-V (12 Periods)

1.1 Introduction to Data Structures

Data - A collection of facts, concepts, figures, observations, occurrences in a formalized

1.1.1 Data Type

Types of data types

SMVEC- Department of Information Technology 1

1.1.2 Data Structures:

1.1.3 Classification of data structure

Fig 1.1 Types of Data Structures

Primary data structure

Secondary data structure

Secondary data structure can be classified as:

Static data structure (Finite Size Data Structure)

Example: array and structure

Dynamic data structure (Variable size Data Structure)

Dynamic data structure can be classified as:

1.1.4 Difference between static and dynamic implementation of data structures

Static implementation of list Dynamic implementation of list

SMVEC- Department of Information Technology 3

1.1.5 Applications of data structure :

1.2 Abstract Data Type (ADT)

ADT = Type + Function + Behavior of each function

„D‟ - Set of domains

Instances-Instances represent the element on which various operations can be

Operations- Operations represent basic operation that can be performed on those

1.2.1 Array ADT

Array is collection of similar data elements in contiguous memory location.

Store() This operation stores the desired element at each successive

Sort() This operation arranges the elements in ascending or

SMVEC- Department of Information Technology 4

Instance: List is an ordered set of elements.

A1, - First element of the list

1.3 Stack ADT

Two ways of implementation of Stack:

 Static implementation of stack using array

1.3.1 Static Implementation of Stack Using ARRAY

 The simplest way of representing a stack isby single dimensional array.

1.3.2 Basic Operations

Algorithm push(stack, top, stacksize)

SMVEC- Department of Information Technology 7

Fig 1.2 Example for Stack Operations

1.4 Dynamic Implementation of Stack Using Linked List

1.4.1 Problems with Array Implementation of Stack:

Structure for Linked Stack Basic operation

SMVEC- Department of Information Technology 8

SMVEC- Department of Information Technology 9

1.5 Applications of Stack

1.5.1 Balanced Parenthesis

Algorithm for balanced Parenthesis

Fig 1.3 Balanced Parenthesis

SMVEC- Department of Information Technology 10

Fig 1.4 Unbalanced Parenthesis

1.5.2 Conversion from infix to postfix expression

An expression is string of operators and operands.Operands- Numeric values

Rules which has to be followed while converting infix expression to postfixform :

Node insert(int start, int x, intloc)

Node delete (int head, int x, intloc)